Dynamic Algorithm for Explainable k-medians Clustering under lp Norm

AI summary

Overview

Research area: Theoretical machine learning and algorithms — specifically explainable clustering, approximation algorithms, and dynamic data structures.

Technical level: Advanced. The paper is primarily a theory contribution with formal theorems, recurrences, and proofs; it assumes familiarity with approximation algorithms, ℓ_p norms, and competitive-ratio analysis.

Scope: The paper presents the first approximation algorithm for explainable k-medians clustering under any finite ℓ_p norm (p ≥ 1) and a dynamic implementation that maintains the clustering under insertions and deletions.

What This Paper Is About

Standard k-medians clustering assigns each data point to its nearest center, which produces highly accurate clusters but assignments that are hard for a person to trace or justify. Explainable k-medians, introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020), instead forces assignments through a threshold decision tree: each internal node compares one coordinate of a point to a threshold, and each leaf represents a cluster. The central question is how much clustering quality is lost in exchange for this interpretability, measured by the competitive ratio — the worst-case ratio between the decision-tree cost and the optimal unconstrained k-medians cost. Prior to this work, algorithms were known only for p = 1 and p = 2, and no dynamic (updates-and-deletions) version existed.

Key Contributions

1. First explainable k-medians algorithm for general ℓ_p norm: The authors give the first algorithm for explainable k-medians under ℓ_p for every finite p ≥ 1, achieving an Õ(p (log k)^{1+1/p−1/p²}) approximation to the optimal k-medians cost.

2. Improved bounds for the previously studied cases: For p = 2, the algorithm improves on the prior Õ(log^{3/2} k) bound, achieving Õ(log^{1.25} k). For p = 1, it matches the tight bound of log k + O(1) up to a multiplicative O(log log k) factor.

3. First dynamic algorithm for explainable clustering: The paper gives a dynamic implementation that maintains the explainable tree under a sequence of insertions and deletions with amortized update time O(d log³ k) and O(log k) recourse, while preserving the same Õ(p (log k)^{1+1/p−1/p²}) competitive ratio.

4. A timestamped/Poisson-process cut framework: The dynamic algorithm integrates exponential timestamps directly into the algorithm design (rather than only into the analysis, as in prior work), assigning each random cut an arrival time so that the earliest cut separating a new center from the anchor can be found in O(d log k) time.

Main Findings

• Approximation guarantee: Theorem 3.1 states that for any p ≥ 1, the algorithm produces a threshold tree with k leaves satisfying E[cost_p(X, T)] ≤ O(p · (log k)^{1+1/p−1/p²} · log log k) · cost_p(X, C).

• Exponent range: The exponent 1 + 1/p − 1/p² always lies in the interval [1, 1.25], so the guarantee degrades gracefully as p moves away from 1.

• Competitive-ratio lower bound for naive sampling: If cuts were instead drawn uniformly rather than from the paper's distribution (CDF x^p / R_t^p), the algorithm would have competitive ratio at least Θ(k^{1−1/p}), demonstrated via a construction with k + 1 centers at e_1, …, e_k and 0 and a point x = (ε, …, ε) whose optimal cost is ε k^{1/p}.

• Recurrence bound (Lemma 3.3): The per-point expected cost satisfies a recurrence of the form 3 + 2A_k/k + β · p (log k)^{1+1/p−1/p²} · log(A_k log² k), which resolves to A_k ≤ O(p (log k)^{1+1/p−1/p²} log log k).

• Geometric decay of radius and diameter: Lemma 3.4 shows the radius halves every L = ⌈2^{p+3} d ln k⌉ steps with probability at least 1 − 1/k³, and Lemma 3.7 shows the diameter surrogate D̃ halves every L′ = ⌈2^{2p+6} d ln k⌉ steps with failure probability at most 4/k³.

• Good-event probability: The "good event" in which the radius and diameter shrink as claimed holds with probability at least 1 − 1/k across all iterations.

• Dynamic update costs: Inserts and deletes are handled with amortized O(d log³ k) update time and O(log k) recourse, modifying only O(log k) tree nodes per update.

• Obliviousness of the tree construction: The tree-construction step takes only the reference center set as input and does not access the data points directly, which is what allows it to be coupled with existing dynamic k-medians algorithms.

• Note on experimentation: The paper does not report empirical experiments, datasets, or benchmark comparisons; all results are theoretical.

Methodology in Plain English

The algorithm builds a decision tree recursively. For any node holding a set of centers, it picks an "anchor" point — a median, or an approximate median satisfying that at least 1/4 of the centers lie on either side of the anchor in each coordinate. It then samples random cuts, each defined by a random coordinate, a random sign, and a random threshold measured from the anchor. Crucially, the threshold is not drawn uniformly: if Z is drawn uniformly from [0, R_t^p] (where R_t is the radius of the current cell), the threshold is set to Z^{1/p}. This power-law distribution is exactly what produces the improved competitive ratio.

Whenever a sampled cut actually separates centers, the algorithm splits the cell into two children, keeps the child containing the anchor as the "main part," and repeats until a stopping rule fires. It then recurses on any leaf still holding more than one center. The authors define two abstractions — a Get_Anchor oracle and a Stopping_Oracle — so the same algorithm can be instantiated statically or dynamically.

The analysis tracks each data point's expected cost along the root-to-leaf path. It classifies each step as "light" or "heavy" based on whether the radius is small or large relative to the point's distance to the anchor, and each separating cut as "safe" or "unsafe" based on how much cost the fallback center would incur. These three cases — safe, light, heavy-and-unsafe — are bounded separately and summed.

For the dynamic version, the authors reinterpret each random cut as arriving at a timestamp drawn from a Poisson process. When a center is inserted, the algorithm finds the earliest-timestamped cut separating it from the anchor using data structures that support this in O(d log k) time; if no tree node for that cut exists, a new one is created. Because the anchor cannot be changed dynamically, the algorithm occasionally rebuilds a cell's subtree when enough updates accumulate, and it must terminate at a fixed time rather than on a center-count threshold as in the static version.

Why This Matters

Impact on research: The paper closes a gap in the explainable clustering literature by extending the analysis from ℓ_1 and ℓ_2 to all ℓ_p norms with finite p ≥ 1, and it opens an entirely new direction — dynamic explainable clustering — that connects explainability to the mature line of dynamic k-medians work (Lattanzi and Vassilvitskii 2017; Chan, Guerqin, and Sozio 2018; Cohen-Addad et al. 2019; Deng, Li, and Rabani 2022; Bhattacharya, Costa, Lattanzi, and Parotsidis 2023, 2024; Bhattacharya, Costa, and Farokhnejad 2025). The prior best dynamic unconstrained result referenced is Bhattacharya et al. (2025), with O(1)-approximation, O(log² Δ) recourse, and Õ(k) update time, where Δ is an aspect ratio of the metric space — the paper shows its explainable algorithm can be layered on top of such methods.

Real-world applications (framed by the paper's stated motivation of transparency and human oversight in AI decisions):

• Evolving, large-scale datasets where data arrives and departs continuously and reclustering from scratch is infeasible, which is precisely the setting the dynamic algorithm targets with O(d log³ k) update time.

• Selecting k interactively — for example, using the elbow method over a range of k values — by feeding centers produced incrementally (e.g., by k-means++-style routines) into the dynamic algorithm to update the tree on the fly.

• Decision systems that affect individuals, businesses, and society, where tracing why a point landed in a given cluster (via a sequence of single-feature threshold comparisons) matters for accountability.

• Settings where complex distance computations are undesirable, since the tree assigns points through simple threshold comparisons rather than explicit nearest-center computations.

Industry relevance: Because the tree construction depends only on the reference centers and not on the data points, it can be dropped into existing production clustering pipelines that already maintain centers dynamically. The low O(log k) recourse also means few tree edits per update, which limits downstream churn in systems that cache or log cluster assignments.

Future Directions

1. Closing the factor gap: The algorithm matches the tight ℓ_1 bound of log k + O(1) only up to an O(log log k) multiplicative factor, leaving open whether the log log k term can be removed.

2. Lower bounds for general p: The paper's own lower bound for the naive uniform-cut variant is Θ(k^{1−1/p}), but the gap between known upper and lower bounds for 2 < p < ∞ is not resolved here; the previously known lower bound for ℓ_2 is only Ω(log k).

3. Tighter dynamic guarantees: Whether the O(log k) recourse and O(d log³ k) update time can be improved, and whether the periodic subtree-rebuild strategy (forced by the anchor being fixed) can be eliminated, remain open.

4. Empirical validation: The paper reports no experiments on real or synthetic datasets, so practical behavior of the algorithm relative to existing explainable clustering heuristics is untested here.

Target Audience

This paper is aimed at theoretical computer scientists and algorithm researchers working on clustering, approximation algorithms, and interpretable machine learning, as well as graduate students familiar with competitive-ratio analysis. Practitioners building large-scale, continuously updated clustering systems with interpretability requirements may benefit from the dynamic formulation, though the paper provides no empirical evaluation to guide implementation choices.

Authors’ abstract

We study the problem of explainable k-medians clustering introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (2020). In this problem, the goal is to construct a threshold decision tree that partitions data into k clusters while minimizing the k-medians objective. These trees are interpretable because each internal node makes a simple decision by thresholding a single feature, allowing users to trace and understand how each point is assigned to a cluster. We present the first algorithm for explainable k-medians under lp norm for every finite p &gt;= 1. Our algorithm achieves an O(p(log k)^{1 + 1/p - 1/p^2}) approximation to the optimal k-medians cost for any p &gt;= 1. Previously, algorithms were known only for p = 1 and p = 2. For p = 2, our algorithm improves upon the existing bound of O(log^{3/2}k), and for p = 1, it matches the tight bound of log k + O(1) up to a multiplicative O(log log k) factor. We show how to implement our algorithm in a dynamic setting. The dynamic algorithm maintains an explainable clustering under a sequence of insertions and deletions, with amortized update time O(d log^3 k) and O(log k) recourse, making it suitable for large-scale and evolving datasets.