REVIEW 5 major objections 4 minor 7 references
Towards Tight Robust Coresets for $k$-Medians Clustering
T0 review · 5 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Tight coresets for k-medians with m outliers: O(m) + Õ(kd ε^{−2}) in bounded VC or doubling dimension, and O(m ε^{−1}) plus the vanilla Euclidean bound, also extending to robust (k,z)-clustering.
desk verdict The paper makes a strong, credible advance on robust coresets, but the doubling-dimension net lemma has a load-bearing gap that the current write-up does not close. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the (r, k)-instance (Definition 4.1): a point set contained in the union of k balls of one equal radius r, together with its regular subclass where cluster sizes are comparable. Uniform radii are what make outlier-induced errors comparable across clusters, which no prior decomposition supplied. Three constructions serve different regimes: Algorithm 1 samples Õ($kdε^{{−2}}$) points and realigns weights so that each cluster's sampled weight equals its original size (capacity-respecting, Definition 6.3), using the indexed-subset cost approximation (Definition 6.2) as the net-side control; Algorithm 2 reduces robust to vanilla coresets by reserving m surrogate points per cluster; Algorithm 3 performs capacity-respecting importance sampling for Euclidean instances with a strong indexed-subset approximation. The load-bearing identities are the cost-difference decomposition (Lemma 6.7), which separates the inlier-cluster cost difference from a single range-space integral over an interval of length O(r), and the metric-entropy bounds on the discretized distance-vector nets (Lemmas 6.12, 7.9, C.1, E.5) that let the chaining argument proceed with only an extra exp(k) factor in the net size.
What would settle it
The theorems would fail if any single metric-entropy bound is wrong, so the direct falsifier is a computational check of Lemma 6.12: in a metric space with small known VC dimension (e.g., the line, d = 2) with k = 2 clusters, sample s ≈ $Ckdε^{{−2}}$ points from an (r, k)-instance, quantize all centers on a grid of step α2^ir, and count the distinct rounded distance-vector values over all 2^k index subsets; if the count exceeds |S|^{O($α^{{−1}}$ dk log k)}, the chaining bound is violated and the claimed sample size is insufficient. On the Euclidean side, a similar enumeration over quantized centers with m outliers would test Definition 2.1 directly on small instances: any computed (ε, m)-robust coreset whose cost error exceeds ε·$cost^{{(t)}}$(X, C) + O(εnr) would contradict Lemma 4.6.
Extended reading notes
Core claim
The central claim is that robust k-medians coresets can be made tight in VC and doubling spaces: with VC or doubling dimension d, an (ε, m)-robust coreset of size O(m) + Õ($kdε^{{−2}}$) is constructible in O(nk) time, matching the vanilla coreset size plus the optimal linear dependence on the outlier count m. In Euclidean space the size is O($mε^{{−1}}$) + Õ(min{$k^{{4/3}}$ $ε^{{−2}}$, k $ε^{{−3}}$}), and for general robust (k, z)-clustering the size is O(m) + Õ($kdε^{{−2z}}$) with optimal linear dependence on both k and m. The discovery that makes these bounds possible is that clustering instances with a uniform radius r—(r, k)-instances—carry an intrinsic robustness property: a weighted sample that is capacity-respecting, an ε-range-space approximation, and an ε-indexed-subset cost approximation is automatically an (ε, m, εnr)-robust coreset. Because all balls have the same radius, the clusters can be partitioned into pure-inlier, pure-outlier, and mixed parts with respect to any center set, and the chaining argument is applied only to the pure-inlier part, whose discrete structure is mild; the mixed part is bounded through its integral representation over a single radius interval. Splitting the error into a relative part controlled by chaining and an additive εnr part controlled by range-space sampling is what makes the final size match the Ω(m + Q) lower bound to within logarithmic factors.
Load-bearing premise
The argument rests on the metric-entropy bounds for the discretized distance-vector nets (Lemma 6.12 for VC spaces, Lemma 7.9 for doubling spaces, and Lemmas C.1 and E.5 for Euclidean spaces): these say the nets have size roughly exponential in dk plus $α^{{−2}}$ factors, and every chaining step consumes that budget. If any of these bounds is wrong, the sample size would not control the indexed-subset cost error and the stated coreset sizes would collapse; the doubling case additionally requires the random ε-smoothed distance lemma (Lemma 7.6) to hold exactly as stated, since it is what turns doubling dimension into a usable probabilistic VC bound.
Editorial extensions
If this is right
- In VC and doubling metric spaces, robust k-medians coresets now have size O(m) + Õ(kdε^{−2}), so any algorithm that preprocesses through a coreset pays only the vanilla price plus the outlier count, matching the Ω(m + Q) lower bound up to log factors.
- The Euclidean bound O(mε^{−1}) + Õ(min{k^{4/3} ε^{−2}, k ε^{−3}}) strictly improves the previous outlier term min{mε^{−2}, kmε^{−1}}, and when m = 0 it reduces exactly to the current best vanilla Euclidean coreset size.
- For robust (k, z)-clustering, the size O(m) + Õ(kdε^{−2z}) has the optimal linear dependence on both k and m, improving the earlier quadratic-in-k bounds.
- All constructions run in O(nk) time given a distance oracle and a constant-factor approximation to the robust optimum, so the coresets are usable as a preprocessing front-end for the known fixed-parameter approximation algorithms.
Reading between the lines
- The capacity-respecting weight realignment looks portable: any constrained clustering variant whose feasible clusters partition the data into bounded-radius pieces (capacitated, fair, or fault-tolerant clustering) could inherit the same robust-coreset sizes by reusing Algorithm 1's realignment and the inlier-only chaining partition, since the outlier instability that blocked chaining is handled st
- The Euclidean gap between O(mε^{−1}) and the Ω(m) lower bound may be closable by iterating the decomposition: Lemma 5.2 uses the threshold r_in = ε·cost/m, and the lost ε^{−1} factor is exactly the cost of bounding the far-point set F; a two-level decomposition that first uses a larger threshold and then recurses on the inner (r, k)-instance could plausibly replace mε^{−1} by m at the price of an
- Remark D.11 indicates that for z > 1 the range-space approximation, not the chaining, is the bottleneck; if one could build an ε^z-range-space approximation with Õ(kdε^{−z−1}) samples, the general-z bound would match the vanilla one, giving a concrete and testable target for refinement.
- Because Fact 2.2 makes robust coresets mergeable with additive error, the new constructions should compose with the streaming and distributed frameworks that already use vanilla coresets, so the tight bounds may carry over to streaming robust clustering without additional loss.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies coresets for robust k-medians clustering with m outliers. It introduces a new decomposition of the dataset into (r,k)-instances, i.e., point sets covered by k balls of equal radius r, and presents three coreset constructions: a sampling-based construction with a chaining analysis for spaces of bounded VC or doubling dimension, a reduction from robust to vanilla coresets for small-radius instances, and a capacity-respecting importance-sampling construction for Euclidean spaces. The main theorems claim robust coresets of size O(m)+O~(kd ε^{-2}) for metric spaces of VC/doubling dimension d, matching the lower bound up to logarithmic factors, and O(mε^{-1})+O~(min{k^{4/3}ε^{-2},kε^{-3}}) in Euclidean space, improving a recent result of Jiang and Lou (ICALP 2025). Extensions to robust (k,z)-clustering are also claimed, including O(m)+O~(kd ε^{-2z}) in VC/doubling metrics and an analogous Euclidean bound.
Significance. If the main theorems hold, the paper essentially settles the robust coreset size for k-medians in VC and doubling metrics up to logarithmic factors and gives the first near-linear-in-m Euclidean bound that matches the vanilla coreset size up to the O(ε^{-1}) outlier factor. The (r,k)-instance decomposition and the idea of applying chaining only to clusters that are guaranteed to be inliers are genuinely novel and are likely to be reused in future work on robust and constrained clustering. The manuscript is unusually detailed: it provides explicit algorithms with stated running times, modular proof outlines, full appendices for the chaining arguments, and a lower-bound appendix. The overall structure is credible, but a few load-bearing metric-entropy lemmas are not proved as written, so I cannot currently recommend acceptance.
major comments (5)
- [Appendix B, Lemma B.2 (and Section 6.3)] The proof that the distance-vector set V_i^S has an α-net of the stated size is incomplete. The net is defined as the set of coordinate-wise roundings \bar v of vectors v^S_{i,J,C}, but these rounded functions are not shown to belong to V_i^S, although the net definition requires N⊆V_i^S and the chaining argument in Lemma B.3 uses the net points as elements of V_i^S. More seriously, when α≥2^{-i}, the 'piecewise constant' refinement \bar u(x)=ceil(dist(a_{π(x)},C)/β)β is defined using the original center set C of the vector being approximated, so \bar u is not determined by u alone and no independent cardinality bound is provided for the refined family. The piecewise-constant property is used in the bound of the second Gaussian term around Eq. (36), so the sample-size claim s=O~(kdε^{-2}) is not established. Please provide a construction of a fixed finite net of piecewise-constant functions, or amend the definition of net and prove the approximation and cardinality bounds directly.
- [Section 7.2, Lemma 7.9] The doubling net construction has a quantifier error and an undefined term. The proof chooses \bar c_j∈N_{i,j}, an α_i-net of the annulus B(a_j,2^{i+1}r)\B(a_j,2^ir), for every j∈J, but for j∉I_{i,C} the nearest center c_j of C to a_j is not guaranteed to lie in that annulus, so such an approximant may not exist. The approximation is only needed for j∈J∩I_{i,C}, because the distance vector v^S_{i,J,C} vanishes outside that set; the proof should quantify over J∩I_{i,C}. In the second part, the vector \bar u(x)=dist(a_{π(x)},\bar C) is defined using a center set \bar C that is not recovered from u, so the claimed fixed net of piecewise-constant vectors is not well defined. These issues must be fixed before Lemma B.3 can rely on the stated net-size bound.
- [Appendix C, Lemma C.1] Lemma C.1, which supplies the metric-entropy bound log|N_α|≲min(2^ψ+kα^{-2},2^{2l}kα^{-2})·log(kα^{-1}ε^{-1}) for the Euclidean distance-vector nets, is stated as an 'adaption' of [BCAP+24, Lemma G.3] and is then used in all three cases of Lemma C.4, including the k^{4/3}ε^{-2} regime. The adaptation is not immediate: the denominator in Eq. (29) is cost(X_J,C)+cost(X,A), which can be much smaller than the cost(X,C) used in [BCAP+24], and the vectors are restricted to arbitrary subsets J of clusters. A proof, or a detailed derivation from [BCAP+24, Lemma G.3], is required; as written the Euclidean bound in Theorem 1.3 depends on an unproved lemma.
- [Appendix D, Lemma D.4] The proof of Lemma D.4 for general z≥1 does not support the claimed radius of G. The set L is chosen to have size m+⌈ε^{-1}⌉, but the displayed chain ε^z cost^(m)_z(X,C*) ≥ cost^(m)_z(X,C*)/⌈ε^z⌉ ≥ 2^T ε r^z requires that at least ε^{-z} points of L survive after removing m outliers, not ε^{-1}; for z>1 the stated bound is off by a factor of ε^{-(z-1)}. Choosing L of size m+⌈ε^{-z}⌉ would repair the argument, and the extra O(ε^{-z}) is absorbed by the final coreset size, but as written the proof of Theorem D.1 for z>1 is incomplete.
- [Appendix E, Lemma E.5] Lemma E.5, the metric-entropy bound for the Euclidean (k,z)-clustering vectors, is justified only by a two-sentence sketch referencing [HLW24, Lemmata B.2 and B.11]. The second bullet of the sketch is not reproducible as written, because the construction must produce nets for the subset-restricted vectors v^J_C with the denominator cost(X_J,C)+cost(X,A), not for the vanilla vectors of [HLW24]. Since Lemma E.5 is the entropy input for the Euclidean (k,z) bound in Theorem E.1, a complete proof should be included.
minor comments (4)
- [Appendix B, Lemma B.2] In the proof, the threshold set B_i^S should be defined with X_{J∩I_{i,C}}, not X_{I_{i,C}}; as written the thresholds do not determine the rounded vector on the support J.
- [Lemma 5.1] The phrase 'outside the ball B_T' and the inequality ε·cost^(m)(X,C*) ≥ 2^T·εr are not justified as stated: the surviving points of L are only guaranteed to lie at distance beyond the previous annulus boundary. Replacing B_T by B_{T-1} and increasing s to ceil(2+log(mk)), or absorbing a constant factor, repairs the diameter bound for G without changing the final asymptotic size.
- [Lemma D.3] The statement says the guarantee is for 'robust k-Medians', but the proof is for robust (k,z)-clustering; please correct the statement to match the proof.
- [Lemma 7.4] The failure probability is written as 1-O(1/(log(k/ε) log(km))); use consistent notation, e.g., log(mk), and parenthesize the denominator unambiguously.
Circularity Check
No circular derivation: the robust-coreset sizes follow from proven chaining/net-size and range-space arguments, not from the claimed conclusions.
full rationale
The paper's central derivation is self-contained rather than circular. The main sizes (Theorem 1.1-1.3, Theorem D.1/E.1) are obtained from Algorithm 1-3 with sample sizes such as s = kd/eps^2 times polylog factors (Algorithm 1), and these sample sizes are justified by proved metric-entropy bounds for distance-vector nets (Lemma 6.12/B.2 for VC, Lemma 7.9 for doubling, Lemmata C.1/E.5 for Euclidean) together with chaining (Lemma B.3, Lemma C.4) and range-space approximation (Lemma 6.9, 7.8). These are not assumed instances of the target theorem; they are proved inside the paper. The additive O(m) outlier term enters through explicit dataset decompositions (Lemmata 5.1 and 5.2) and through the mergeability of robust coresets (Fact 2.2), not through fitting or renaming. Citations to the authors' prior work are used as external building blocks or benchmarks, e.g., Lemma 7.6 is quoted from [HJLW18] as a random smoothed-distance tool for doubling spaces, and lower bounds are quoted from [HJLW23, CLSS22] to establish optimality; these results do not contain the claimed robust-coreset theorem, so they are independent support rather than a self-citation chain forcing the result. No equation in the proof reduces by construction to its own input: for instance, the reduction from vanilla coresets to robust coresets in Lemma 4.5 is an explicit black-box transformation with a proved additive-error bound, not a definitional equivalence. Possible gaps in the write-up of the alpha-net construction or the doubling pairing (as noted by a skeptical reader) are correctness risks, not circularity, and do not affect the circularity score.
Assumptions & free parameters
assumptions (5)
- domain assumption The metric space has finite VC dimension d_VC or doubling dimension d_D
- domain assumption There is a constant-factor approximation C* for robust k-medians on the dataset
- standard math Standard VC theory, symmetrization, and chaining bounds (e.g., maximum of Gaussians, Fact 2.3)
- standard math Random epsilon-smoothed distance function for doubling spaces bounds the probabilistic VC dimension (Lemma 7.6)
- standard math Generalized triangle inequality for powers of distances (Lemma D.5)
Cite this review
Pith. "Pith review of Towards Tight Robust Coresets for $k$-Medians Clustering." pith.science (2026). https://pith.science/paper/JW6KMNEE
@misc{pith2026250711260,
author = {Pith},
title = {Pith review of: Towards Tight Robust Coresets for $k$-Medians Clustering},
year = {2026},
howpublished = {\url{https://pith.science/paper/JW6KMNEE}},
note = {Machine review of arXiv:2507.11260}
}
abstract
This paper considers coresets for the robust $k$-medians problem with $m$ outliers, and new constructions in various metric spaces are obtained. Specifically, for metric spaces with a bounded VC or doubling dimension $d$, the coreset size is $O(m) + \tilde{O}(kd\varepsilon^{-2})$, which is optimal up to logarithmic factors. For Euclidean spaces, the coreset size is $O(m\varepsilon^{-1}) + \tilde{O}(\min\{k^{4/3}\varepsilon^{-2}, k\varepsilon^{-3}\})$, improving upon a recent result by Jiang and Lou (ICALP 2025). These results also extend to robust $(k,z)$-clustering, yielding, for VC and doubling dimension, a coreset size of $O(m) + \tilde{O}(kd\varepsilon^{-2z})$ with the optimal linear dependence on $m$. This extended result improves upon the earlier work of Huang et al. (SODA 2025). The techniques introduce novel dataset decompositions, enabling chaining arguments to be applied jointly across multiple components.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[7]
Coresets for constrained clus- tering: General assignment constraints and improved size bounds
[HLL W25] Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clus- tering: General assignment constraints and improved size bounds. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4732–4782. SIAM,
work page 2025
-
[2007]
A unified framework for approximating and clustering data
[FL11] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. InSTOC, pages 569–578. ACM, 2011.https://arxiv.org/abs/ 1106.1379. [FMN16] Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis.Journal of the American Mathematical Society, 29(4):983–1049,
arXiv 2011
-
[2018]
Jiang, Jianing Lou, and Xuan Wu
[HJL W23] Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. InProceedings of ICLR 2023,
work page 2023
-
[2019]
Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. URL:https://drops.dagstuhl. de/entities/document/10.4230/LIPIcs.ICALP.2019.41,doi:10.4230/LIPIcs. ICALP.2019.41. [CDS20] Rachit Chhaya, Anirban Dasgupta, and Supratim Shit. On coresets for regularized re- gression. InInternational conference on machine learning, pages 1866–1876. PMLR,
-
[2020]
Improved algorithms for clustering with outliers
[FZH+19] Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. Improved algorithms for clustering with outliers. InProc. 30th International symposium on algorithms and computation (ISAAC 2019),
work page 2019
-
[2021]
[BJKW21b] Vladimir Braverman, Shaofeng H.-C
URL:https://proceedings.neurips.cc/paper/2021/file/ 90fd4f88f588ae64038134f1eeaa023f-Paper.pdf. [BJKW21b] Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2679–2696. SIAM,
work page 2021
-
[2022]
On the fixed-parameter tractability of ca- pacitated clustering
[CAL19] Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of ca- pacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors,46th International Colloquium on Automata, Lan- guages, and Programming (ICALP 2019), volume 132 ofLeibniz International Pro- ceedings in Informatics (LIPIcs),...
work page 2019
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.