Research map / Learning theory and algorithms / Clustering
Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm
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 explainable k-medians tree algorithm for any finite l_p norm with approximation Õ(p(log k)^{1+1/p-1/p^2}), plus a fully dynamic version with O(d log^3 k) amortized update time and O(log k) recourse.
Problem
Explainable k-medians clustering under l_p norms: build a threshold decision tree with k leaves minimizing the k-medians cost, with competitive ratio against unconstrained optimum, and maintain it under insertions/deletions of centers.
Approach
Generalize the randomized threshold-cut partitioning (Partition_Leaf) to all l_p norms using a cut distribution with CDF x^p/R^p over thresholds, analyzed via safe/unsafe and light/heavy cut decomposition; for dynamics, attach Poisson arrival times (exponential clocks) to pre-generated cuts so that inserted centers find the earliest separating cut.
Key results
- Static algorithm achieves Õ(p(log k)^{1+1/p-1/p^2}) competitive ratio for any finite p≥1, improving the l_2 bound from Õ(log^{1.5} k) to Õ(log^{1.25} k) and matching log k+O(1) for p=1 up to log log k.
- Dynamic algorithm has amortized update time O(d log^3 k) and O(log k) amortized recourse while keeping the same competitive ratio.
- Lower bound Ω(log k) for any p≥1 and an Ω(d^{1/4}) lower bound for any single distribution over trees that works uniformly across all p.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Generalize the explainable clustering algorithm to finite ℓp norms and use the analyzed threshold-cut distribution | Explainable k-medians · Explainable k-medians, ℓp (finite p ≥ 1) | competitive ratio: \tilde{O}(p (\log k)^{1 + 1/p - 1/p^2}) | Helped |
| Tighten the analysis for ℓ2 | Proposed explainable k-medians algorithm · Explainable k-medians, ℓ2 | competitive ratio: \tilde{O}(\log^{1.5} k) -> \tilde{O}(\log^{1.25} k) | Helped |
| Use a uniform threshold distribution instead of the proposed threshold distribution | Explainable k-medians threshold-cut algorithm · Constructed instance with k+1 centers | competitive ratio: \Theta(k^{1-1/p}) | Hurt |
| Maintain the explainable clustering tree dynamically under center insertions and deletions | Proposed explainable k-medians algorithm · Dynamic explainable k-medians, ℓp (finite p ≥ 1) | amortized update time: O(d\log^3k) | Helped |
| Maintain the explainable clustering tree dynamically under center insertions and deletions | Proposed explainable k-medians algorithm · Dynamic explainable k-medians | amortized recourse: O(\log k) | Helped |
Surprising findings
- No single explainable tree distribution can achieve a good competitive ratio simultaneously for all p≥1 without knowing p in advance.
Limitations
- Gap of Õ((log k)^{1/p-1/p^2}) between upper and lower bounds for p>1, maximized at p=2 (about log^{1/4} k)
- Analysis is for competitive ratio only; no empirical experiments reported
- Dynamic algorithm assumes centers in [-1,1]^d after rescaling and relies on pre-generated cut sequence
Experimental setup
Metrics: competitive ratio (approximation factor) amortized update time amortized recourse
Baselines: Dasgupta et al. 2020 l_1 tree Esfandiari et al. O(log^{1.5} k) l_2 algorithm uniform threshold cut variant
Builds on: Dasgupta et al. 2020 explainable k-medians Esfandiari et al. explainable clustering l_2 algorithm exponential clock technique for l_1 explainable clustering
Closest papers by meaning
- Near-Optimal Algorithms for Explainable k-Medians and k-Means (ICML 2021 · similarity 0.94)
- SpEx: A Spectral Approach to Explainable Clustering (NeurIPS 2025 · similarity 0.89)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.88)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.87)
- Explaining Kernel Clustering via Decision Trees (ICLR 2024 · similarity 0.86)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.