{"id":"b2ba38b6-76ec-4f57-a855-b298f08162c3","arxiv_id":"2507.11260","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New algorithms build robust k-medians coresets of size O(m)+O~(kd/epsilon^2) in VC or doubling metrics and O(m/epsilon)+O~(min{k^{4/3}/epsilon^2,k/epsilon^3}) in Euclidean space.","lead":"The paper constructs near-optimal coresets, small weighted samples that preserve clustering costs, for robust k-medians with outliers. In bounded-dimension metrics the size is O(m) plus near O(kd/epsilon^2), and in Euclidean space it improves prior bounds to O(m/epsilon) plus near O(min{k^{4/3}/epsilon^2, k/epsilon^3}).","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Indexed net-size bounds are the linchpin; the current proof has unaddressed gaps in the α-net construction and the doubling pairing, so the sample-size claim needs verification.","rationale":"The paper's overall structure is coherent and the technical overview is convincing: the uniform-radius (r,k)-instance decomposition, the capacity-respecting reweighting, and the three-way partition of clusters into A1/A2/A3 are natural and appear sound. The range-space approximation and the indexed-subset cost approximation are derived through standard chaining, and the reductions from robust to vanilla coresets (Lemmas 4.5 and 4.6) are carefully argued. The reader's weakest-assumption identification aligns with mine: the metric entropy bounds for the indexed distance-vector nets are the most load-bearing technical claims. However, I found specific unresolved points where the proof as written does not fully establish these bounds: the constructed nets are not shown to belong to the vector set required by the definition, and the doubling net's error analysis does not cover centers outside the chosen annuli. These are not necessarily fatal---standard chaining can often work with external nets, and the doubling issue may be fixable by enlarging the net slightly---but they are exactly the kind of gaps that a conditional acceptance should request the authors to close. I therefore recommend CONDITIONAL rather than unconditional ACCEPT, with the concrete verification described above. If the authors supply a clean re-derivation of Lemmas 6.12 and 7.9 addressing these points, the theorems follow from the rest of the paper.","tokens_in":64350,"tokens_out":47700,"duration_ms":545616,"concrete_test":"Independently re-derive Lemma 6.12 by explicitly constructing an alpha-net for V^S_i that is either proven to be a subset of V^S_i or is allowed as an external net in a reworked Lemma B.3; verify the log-size bound remains O(alpha^{-1} d k log k log|S|) including the J-subset factor. For the doubling case, test Lemma 7.9 on a concrete metric (e.g., a line or a tree metric) with k=2, i=0, alpha small: construct C with one center far from both a_j's and check whether the claimed error bound |dist(x,C)-dist(x,overline{C})| <= alpha_i holds for all x in S; if it does not, determine whether adding the far center to the net increases the size exponent beyond O(k d log(k/alpha)).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central sample-size guarantees for the indexed-subset cost approximation (Definition 6.2) rest on the metric entropy bounds for distance-vector nets: Lemma 6.12 (VC), Lemma 7.9 (doubling), and Lemmas C.1/E.5 (Euclidean). If any of these bounds fail, the chaining bound (Lemma B.3) would require a larger sample s, breaking the claimed O~(kd/epsilon^2) coreset size for VC/doubling and the O~(min{k^{4/3}epsilon^{-2}, k epsilon^{-3}}) Euclidean size. There are two concrete gaps in the write-up of these lemmas. First, in Lemma 6.12/B.2, the constructed net is the collection of coordinate-wise roundings ceil(dist(x,C)/beta)beta, but such rounded vectors are not shown to lie in V^S_i, the vector set over which the net is defined; the proof also appears to contain a typo writing X_{I_{i,C}} where X_{J cap I_{i,C}} is needed. The piecewise-constant refinement is defined per original center C and its cardinality is not independently bounded when several C map to the same rounding. Second, in Lemma 7.9, the error bound |dist(x,C) - dist(x,overline{C})| <= alpha_i assumes each center c in C can be paired with the annulus of some a_j and moved by at most alpha_i; centers that are not near any a_j in the chosen annuli are not handled, and for a point x whose nearest center in C is such a far center, the claimed bound is not justified. These gaps leave the metric entropy bounds, and hence the main theorems, not fully established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":64704,"tokens_out":31196,"duration_ms":371781,"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":[{"comment":"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":"Appendix B, Lemma B.2 (and Section 6.3)"},{"comment":"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.","section":"Section 7.2, Lemma 7.9"},{"comment":"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.","section":"Appendix C, Lemma C.1"},{"comment":"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.","section":"Appendix D, Lemma D.4"},{"comment":"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.","section":"Appendix E, Lemma E.5"}],"minor_comments":[{"comment":"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.","section":"Appendix B, Lemma B.2"},{"comment":"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.","section":"Lemma 5.1"},{"comment":"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.","section":"Lemma D.3"},{"comment":"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.","section":"Lemma 7.4"}],"recommendation":"major_revision","confidential_remarks":"The main results are likely correct and would be a strong contribution, but the manuscript currently relies on several net-construction lemmas that are either unproved or stated with quantifier/dependence errors. I would ask the authors to supply complete proofs of Lemmas B.2, 7.9, C.1, and E.5, and to fix the L-size issue in Lemma D.4, before sending the paper back to review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result is real: this is the first construction of robust k-medians coresets that matches vanilla sizes up to logs in VC and doubling spaces, plus a Euclidean improvement over Jiang–Lou. The uniform-radius (r,k)-instance decomposition and the adaptation of chaining to the robust setting are genuinely new and well-motivated. The paper is honest with the prior work and the lower bounds, and the bulk of the analysis is structurally credible.\n\nNow the soft spots. The VC net lemma (6.12/B.2) has a formal gap: the round-vectors are not shown to live in the set V_i^S, and there are typos in the set definitions (they write X_{I_{i,C}} where X_{J∩I_{i,C}} is needed). These look cosmetic, and the counting still goes through in the right order, so I wouldn't hang a rejection on that.\n\nThe doubling net lemma (7.9) is more serious. The proof pairs each cluster j with a point in an annulus around a_j, but the nearest center to a point in X_j need not lie in that annulus. The claimed bound |dist(x,C)-dist(x,\\bar C)| ≤ α_i is not justified as written. This is load-bearing: the chaining sample size and therefore the O~(kd/ε^2) coreset size for doubling spaces depend on it. I think it is fixable—cover full balls around each a_j rather than just annuli, and the net size stays (1/α)^{O(dk)}—but the current text does not prove it.\n\nSo: the paper deserves a serious referee, not a desk rejection. The right outcome is likely acceptance after a revision that repairs the doubling net lemma and cleans up the VC net statements. If you work on coresets, this is worth a careful read despite the gaps.","headline":"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.","tokens_in":65246,"tokens_out":8844,"would_cite":true,"duration_ms":102448,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["robust k-medians coresets","outliers","VC dimension","doubling dimension","chaining argument","(r, k)-instances","Euclidean clustering","range-space approximation"],"falsifier":"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.","tokens_in":64171,"feed_emoji":"🎯","tokens_out":11524,"duration_ms":125522,"temperature":0.7,"pith_summary":"This paper is about coresets for k-medians clustering when up to m points are outliers: a small weighted subsample of the data that preserves the optimal clustering cost for every set of k centers and every outlier budget up to m. The paper shows that robustness need not force a larger coreset than vanilla k-medians: in every metric space with bounded VC or doubling dimension d, an (ε, m)-robust coreset of size O(m) + Õ($kdε^{{−2}}$) exists, matching the known lower bound Ω(m + Q) up to logarithmic factors; in Euclidean space the size is O($mε^{{−1}}$) + Õ(min{$k^{{4/3}}$ $ε^{{−2}}$, k $ε^{{−3}}$}), improving on the recent Jiang–Lou bound. The enabling idea is a new decomposition of the dataset into (r, k)-instances, point sets covered by k balls of one common radius, which makes outlier-induced errors comparable across clusters so that chaining arguments—previously confined to vanilla coresets—can be applied to the robust objective.","feed_headline":"Coresets with m outliers shrink to O(m) plus vanilla size","feed_subtitle":"The outlier term drops to O(m) (or O(m/ε) in Euclidean space) while the k/ε term matches the best known bounds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the robust-coreset framework the paper builds on: the mergeability Fact 2.2, the Ω(m) lower bound, and the ring-decomposition analysis that the new (r, k)-instance grouping refines.","marker":"[HJL W23]"},{"why":"Gives the tight VC-dimension vanilla coreset of size Õ(kdε^{−2}) that the Q-term must match, plus the chaining and net-size technique adapted in Lemma 6.12.","marker":"[CADRS25]"},{"why":"Establishes the doubling-dimension coreset framework whose vanilla size Õ(kd_Dε^{−2}) the robust bound extends.","marker":"[CSS21]"},{"why":"Provides the Ω(kdε^{−2}) lower bound for vanilla coresets and the sampling concentration lemma (their Lemma 19) reused as Lemma 6.8.","marker":"[CLSS22]"},{"why":"Supplies the random ε-smoothed distance function (Lemma 7.6) that converts bounded doubling dimension into a usable probabilistic VC-type bound for the range-space argument.","marker":"[HJL W18]"},{"why":"The sensitivity-sampling coreset whose sampling scheme Algorithm 3 adapts with the capacity-respecting weight scaling in Line 10.","marker":"[BCAP+24]"},{"why":"The prior robust-to-vanilla reduction giving min{mε^{−2}, kmε^{−1}} plus the vanilla size, which Theorem 1.3 and Remark 8.4 improve.","marker":"[JL25]"},{"why":"Provides the Euclidean vanilla (k, z) bound and the net constructions (their Lemmas B.2 and B.11) adapted as Lemma E.5 for general z.","marker":"[HL W24]"}],"fun_headline_variants":["Robust k-medians coresets: tight O(m)+Õ(kd/ε²) size","Optimal outlier factor for robust k-medians coresets","Coresets for k-medians with outliers match vanilla size","Tight robust coresets for k-medians: O(m) outlier term","Euclidean robust coresets: O(m/ε) outlier term"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Robust k-medians coresets: tight O(m)+Õ(kd/ε²) size","Optimal outlier factor for robust k-medians coresets","Coresets for k-medians with outliers match vanilla size","Tight robust coresets for k-medians: O(m) outlier term","Euclidean robust coresets: O(m/ε) outlier term"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001751,"raw_usage":{"total_tokens":6981,"prompt_tokens":1080,"completion_tokens":5901,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":5803}},"tokens_in":696,"tokens_out":5901,"duration_ms":52863,"temperature":1.0,"reasoning_tokens":5803,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:12:16.109840+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}