{"id":"646070d1-80a7-40b4-8d65-250167ee23de","arxiv_id":"2502.07669","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A black-box reduction turns any vanilla clustering coreset into an epsilon-coreset for clustering with m outliers, with size N times polylog plus min{O(km/epsilon), O(m/epsilon^{2z})}.","lead":"This paper shows how to build small summaries, called coresets, for clustering with outliers by treating any good summary for ordinary clustering as a black box. The trick upgrades a generic clustering tool to handle noisy data with only a small size increase, and yields new streaming algorithms for k-median and k-means with outliers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Offline reductions appear sound; the dynamic-streaming claim depends on Lemma C.1, where the bucket-elimination step is only sketched.","rationale":"I read the paper in good faith. The main offline contribution—a black-box reduction from vanilla coresets to robust coresets—is well structured and the proofs of Lemmas 3.3, 4.3, and 4.6 appear coherent: the dense/sparse decomposition is valid, the additive-error composability works, and the size-preserving calibration is legitimate. The reader's weakest_assumption points to the tri-criteria approximation C* and the separated-duplication family; these are indeed conditional inputs, but they are standard and supported by cited prior work, so I do not see them as the most fragile point. The genuinely load-bearing spot is the streaming section: Lemma 5.4, whose proof is delegated to the proof sketch of Lemma C.1, is what makes Theorem 5.1 go through. The step from 'each sample is blue with probability at least 1/2' to 'after O(T log(T/δ)) samples, |φ(B\\G)| ≤ β' is not fully justified because bucket elimination requires removing every point in a blue bucket, and the without-replacement dynamics of the two-level sampler are not analyzed. This is an omission, not a demonstrated falsehood; if the proof can be completed, the conditional verdict should become an accept. My recommendation is therefore to keep the reader's CONDITIONAL verdict unchanged, since it already identifies this unresolved streaming lemma as the main condition.","tokens_in":48758,"tokens_out":26661,"duration_ms":243998,"concrete_test":"Complete the proof of Lemma C.1 by analyzing the sampling process at bucket granularity: prove that after s = C T log(T/δ) draws of the two-level sampler without replacement, with probability at least 1−δ, at most β blue buckets remain non-empty, accounting for buckets of size greater than one and for the changing blue probability. A concrete computational check: randomly generate adversarial configurations (X, φ, F) with |F| ≤ T and |φ(X)| ≫ |φ(X\\F)|, simulate the stated sampler, and test whether |φ(X\\G)| ≤ 2|φ(X\\F)| holds with the claimed probability; a violation would require increasing the sample size or revising Theorem 5.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central offline theorems (3.1 and 4.2) are internally consistent: the dense/sparse decomposition, the size-preserving calibration, and the bridge-center argument in Lemma 4.6 all check out, and the reliance on a tri-criteria approximation C* is a standard conditional assumption with cited constructions. The load-bearing gap is in the streaming implementation, specifically Lemma 5.4 and its proof-sketch Lemma C.1. The lemma promises that O(T log(T/δ)) two-level samples without replacement leave |φ(X\\G)| ≤ 2|φ(X\\F)| for every F with |F| ≤ T. The sketch colors buckets φ(X\\F) red and the rest blue, notes each sample is blue with probability at least 1/2, and then jumps to 'since |B|≤T, |φ(B\\G)|≤β'. This jump is not immediate: a blue bucket with several points is eliminated only when all its points are sampled, and the argument must show that the total number of blue samples suffices to empty all but β blue buckets despite the without-replacement depletion of blue probability. Theorem 5.1's space bounds W1/W2 and the claimed first dynamic streaming coreset algorithms for robust k-clustering rest on this lemma, which is presented only as a proof sketch. This is an omission in a load-bearing place, not a demonstrated error.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper gives black-box reductions that convert any epsilon-coreset construction for vanilla (k,z)-Clustering into an epsilon-coreset for (k,z,m)-Clustering with outliers. The first reduction (Theorem 3.1) uses a dense/sparse decomposition and adds O_z(km/epsilon) points to the vanilla coreset; the second (Theorem 4.2) uses separated duplications and sparse partitions to obtain an alternative additive bound O_z(m epsilon^{-2z} log^z(km/epsilon)). Plugging in known vanilla coresets yields the first robust coresets with size near-linear in k, and a dynamic streaming implementation (Theorem 5.1) is claimed to give the first dynamic streaming coreset algorithms for k-Median and k-Means with m outliers using space ~O(k+m) poly(d epsilon^{-1} log Delta). The streaming part depends critically on Lemma 5.4, whose proof (Appendix C.1) is only a sketch.","tokens_in":48884,"tokens_out":18778,"duration_ms":180210,"significance":"If the results are correct, Theorem 1.1 is a substantial advance: it gives a clean, black-box understanding of the price of robustness for coresets, obtains the first robust coresets near-linear in k in several metric families, preserves determinism when the base algorithm is deterministic, and provides the first dynamic streaming coresets for robust k-clustering. The explicit lemma structure and error bookkeeping are strengths, as is the composability treatment. The main caveats are that the streaming claims rest on an unproved bucket-elimination step (Lemma C.1) and that Theorem 4.2 uses Lemma 4.6 in a stronger form than the lemma states; these are local but load-bearing and currently block acceptance.","major_comments":[{"comment":"The proof of Lemma C.1, which underpins Lemma 5.4 and hence Theorem 5.1, is only a sketch and the bucket-elimination step does not follow from the stated argument. Coloring points red/blue and observing that each two-level sample is blue with probability at least 1/2 controls the number of samples that hit B, but a blue bucket is eliminated only when all of its points have been sampled; a bucket with r points requires r successful hits to that same bucket, and sampling without replacement decreases the per-bucket success probabilities over time. The conclusion 'since |B|<=T, |phi(B\\G)|<=beta' therefore needs a genuine coupon-collector-style analysis over buckets with arbitrary sizes, not just O(T log(T/delta)) samples. Because both the W1 and W2 streaming space bounds and the claimed first dynamic streaming algorithms rest on this lemma, a complete proof or a replacement argument is required.","section":"Appendix C.1, Lemma C.1"},{"comment":"Lemma 4.6 as stated proves only that the output S of Algorithm 2 is an epsilon-coreset for (k,z)-Clustering. Theorem 4.2, however, invokes the lemma to conclude that S is an epsilon-coreset for (k + beta k Lambda, z)-Clustering, and then for (k+|Q|,z)-Clustering, in order to apply Lemma 4.3. A coreset for k centers does not imply a coreset for a larger number of centers by padding, since the bridge-center bound in the proof of Lemma 4.6 grows with the number of centers. The gap is likely fixable by generalizing Lemma 4.6 to arbitrary k0 with the condition k' >= (k0+t)Lambda, which is exactly what the choice k'=(k+beta k Lambda+beta k)Lambda provides, but this generalization is not stated or proved. As written, the application in Theorem 4.2 and in Section 5.2 is unsupported.","section":"Section 4, Lemma 4.6 vs. Theorem 4.2"},{"comment":"In the proof of Lemma 3.3, inequality (7) is dismissed as 'similar' to inequality (6), but the tool used for (6), Lemma 3.5, applies only to a dataset whose parts are dense. The coreset S is a weighted set and is not shown to satisfy the dense-partition condition |P| >= (1+epsilon^{-1})m on any partition. Some additional argument is needed, for example showing from the vanilla coreset guarantee that w_S(S cap P) is close to |P| for every dense part P, or proving a weighted analogue of Lemma 3.5. This is load-bearing for Theorem 3.1, since (7) is used to bound the difference between robust and vanilla costs on S.","section":"Section 3.1, Lemma 3.3"}],"minor_comments":[{"comment":"The heading 'Seperated duplication of a metric space' contains a typo; it should be 'Separated duplication'.","section":"Definition 4.1"},{"comment":"The notation 'XS <- sum_{P in S} P' is informal; it should be written as 'XS <- union_{P in S} P' or with explicit set-builder notation.","section":"Algorithm 4, line 4"},{"comment":"The lemma title 'Indentify Sparse Subsets' contains a typo; it should be 'Identify Sparse Subsets'.","section":"Lemma 5.5"},{"comment":"The subsection heading 'Removing Assumption of Knowing dOPT' appears to have a typo: 'dOPT' should be '[OPT' or 'OPT'.","section":"Section 5.1"},{"comment":"The statement says the algorithm samples 'a random subset G' but the proof describes sampling without replacement via l0-samplers; the precise sense in which G is random should be clarified, since it is not uniform over subsets of X.","section":"Lemma 5.4"}],"recommendation":"major_revision","confidential_remarks":"Dear Editor, this is a promising and technically rich paper. The offline reduction framework is elegant and mostly well argued, and the claimed near-linear-in-k bounds, if established, would be a clear contribution. My concern is that the streaming theorem depends on a lemma whose proof is only a sketch (Lemma C.1), and Theorem 4.2 uses Lemma 4.6 in a stronger form than stated. These issues appear fixable, but they are not merely stylistic. I recommend major revision and ask that the authors supply a complete proof of the bucket-elimination lemma and correct or generalize Lemma 4.6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Offline, the paper is a genuinely new reduction framework: it turns any vanilla (k,z)-coreset into a robust one with polylog overhead and additive terms that are near-optimal in m. The two sufficient conditions (dense datasets, size-preserving property) and the almost-dense decomposition are new devices, and the separated-duplication construction is handled carefully for Euclidean, doubling, and graph metrics. Theorems 3.1 and 4.2 are argued with explicit lemmas, the error bookkeeping checks out, and composability is proved. The reliance on a tri-criteria approximation C* is standard and cited with constructions, so I don't see that as a soft spot.\n\nThe soft spot is the streaming section. Theorem 5.1, and hence the claimed first dynamic streaming algorithms for robust k-median/k-means, rest on Lemma 5.4, whose proof is only a sketch (Lemma C.1). The sketch colors buckets red/blue, notes each two-level sample is blue with probability at least 1/2, then jumps to the conclusion that after O(T log(T/δ)) samples, |φ(B\\G)| ≤ β. That jump is not immediate: a blue bucket is eliminated only when all of its points have been sampled, and the sketch only argues that at least one blue point is obtained. Coupon-collector intuition suggests the bound might be true with a larger sample size, but as written the lemma is unproven. Since both space bounds W1 and W2 in Theorem 5.1 depend on this lemma, this is a load-bearing gap, not a cosmetic one. It is an omission rather than a demonstrated error — the offline machinery suggests the approach could work — but the streaming claims need a complete proof or a weaker statement.\n\nFor a theory paper this is otherwise well put together; no code or data is expected. The audience is anyone working on coresets, robust clustering, or streaming clustering. The offline results alone are significant enough to deserve a serious referee, and the streaming part may be fixable. I'd send it to review with a request to fix Lemma C.1 before acceptance.","headline":"A strong black-box reduction framework for robust clustering coresets; offline part looks solid, but the streaming theorem rests on an unproven sampling lemma.","tokens_in":49568,"tokens_out":2906,"would_cite":true,"duration_ms":30917,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that any ε-coreset construction for ordinary (k,z)-Clustering can be turned into an ε-coreset for (k,z,m)-Clustering with outliers, with size near-linear in k and only polylogarithmic overhead.","keywords":["coresets","clustering with outliers","robust clustering","k-median","k-means","black-box reduction","dynamic streaming","size-preserving coresets"],"falsifier":"Find a metric from the paper's list where every $\\epsilon$-coreset for $(k,z,m)$-Clustering provably needs $\\Omega(k^2)$ points while vanilla coresets of size $O(k\\,\\mathrm{poly}(\\epsilon^{-1}))$ exist; Theorem 1.1 predicts near-linear dependence on $k$ in all listed metrics, so such a lower bound would refute the central claim.","tokens_in":48428,"feed_emoji":"🧮","tokens_out":11451,"duration_ms":99424,"temperature":0.7,"pith_summary":"This paper tries to establish that coresets for clustering with outliers can be built from any coreset construction for ordinary clustering, with only a small extra cost. Concretely, it claims that an $\\epsilon$-coreset for $(k,z,m)$-Clustering can be produced from an $\\epsilon$-coreset for $(k,z)$-Clustering of size $N$, with size $N\\cdot \\mathrm{poly}\\log(km\\epsilon^{-1}) + O_z(\\min\\{km\\epsilon^{-1}, m\\epsilon^{-2z}\\log^z(km\\epsilon^{-1})\\})$, where $O_z$ hides a $2^{O(z\\log z)}$ factor. If true, this gives the first robust clustering coresets whose size is near-linear in $k$, replacing previous bounds that grew at least quadratically in $k$, and it makes the 'price of robustness' a small additive term rather than a structural obstacle. A reader should care because coresets are the standard route to fast, streaming, and distributed clustering algorithms, and the robust-with-outliers variant has lagged behind the vanilla case.","feed_headline":"Outlier-robust clustering coresets reach near-linear size","feed_subtitle":"Black-box reductions turn any vanilla coreset into one for robust k-clustering with m outliers.","key_machinery":"The load-bearing mechanism is a pair of sufficient conditions plus black-box reductions that enforce them. Condition I says a vanilla coreset of a dense dataset—one that admits a $\\lambda$-bounded partition in which every part has at least $\\Omega(\\epsilon^{-1}m)$ points—is already an $O(\\epsilon)$-coreset for the robust objective, because each point's contribution is charged against many nearby points. Condition II says a vanilla coreset that is size-preserving with respect to a $\\lambda$-bounded partition—each part keeps exactly its original number of weighted points, so the coreset can be read as moving every point by at most $\\lambda$—is robust. To make Condition I hold, an almost-dense decomposition (Lemma 3.4) splits any dataset into a dense part and a sparse remainder of only $O_z(km\\epsilon^{-1})$ points. To make Condition II hold, Algorithm 2 maps the dataset into a $w$-separated duplication of the metric (each point is copied into one of $h$ layers placed far apart), computes a vanilla coreset there, and pulls it back; a sparse partition with $O(\\log n)$ overlap controls the number of centers that this construction requires.","core_discovery":"The central claim is Theorem 1.1: any $\\epsilon$-coreset construction for vanilla $(k,z)$-Clustering with size $N$ can be converted, in a black-box way, into an $\\epsilon$-coreset for $(k,z,m)$-Clustering of size $\\min\\{N(d,k,O(\\epsilon^{-1})) + O_z(km\\epsilon^{-1}), N(O(d), O(k\\log^2(km\\epsilon^{-1})), O(\\epsilon^{-1})) + O_z(m\\epsilon^{-2z}\\log^z(km\\epsilon^{-1}))\\}$. The conversion never inspects the vanilla coreset algorithm's internals. It rests on two sufficient conditions under which a vanilla coreset is automatically robust: (i) the dataset is 'dense', meaning it admits a partition into bounded-diameter parts each containing at least $\\Omega(\\epsilon^{-1}m)$ points, so deleting $m$ outliers changes the objective by only $O(\\epsilon)$; and (ii) the vanilla coreset is 'size-preserving', meaning it keeps the same number of weighted points in each part of a bounded-diameter partition, so it can be viewed as moving every data point by only a small distance. The paper shows how to force either condition by a black-box reduction: an almost-dense decomposition that leaves only $O_z(km\\epsilon^{-1})$ 'sparse' points outside the dense core, and a separated-duplication trick combined with a sparse partition that makes any vanilla coreset size-preserving at the cost of a polylogarithmic factor and a duplication of the metric whose complexity grows only by a constant in standard metric families.","pith_inferences":["We infer that the same two-condition recipe—density or size-preservation—can be exported to other constrained clustering variants such as capacity, fairness, or fault-tolerant clustering, because the reduction never uses the vanilla algorithm's internals and only needs a bounded-diameter decomposition plus a size-preserving coreset.","We infer that the streaming implementation, which uses data-oblivious consistent hashing rather than quadtrees, opens a route to dynamic streaming coresets for other clustering variants in high dimension whenever a sparse-recovery primitive is available.","We infer that the next natural target is a matching lower bound for the additive term itself: the paper's bound separates the price of robustness from the vanilla size, and the $\\Omega(m)$ lower bound for robust coresets already shows the linear dependence on $m$ is necessary.","We infer that any metric family whose complexity parameter is stable under separated duplication—as the paper shows for doubling dimension, treewidth, and excluded-minor graphs—would inherit the near-linear-in-$k$ bound without a new argument."],"forward_implications":["Plugging in known vanilla coresets gives the first coresets for $(k,z,m)$-Clustering with size near-linear in $k$ in Euclidean spaces, doubling metrics, general finite metrics, and bounded-treewidth or excluded-minor graph metrics.","Because the reduction is black-box, any future improvement to vanilla coreset size or construction time transfers automatically to the robust setting.","In the dynamic streaming model, the reductions yield the first streaming coreset algorithms for $k$-Median and $k$-Means with $m$ outliers, using space $\\tilde{O}(k+m)\\,\\mathrm{poly}(d\\epsilon^{-1}\\log\\Delta)$ on grid inputs.","The additive term becomes $O_z(k\\epsilon^{-1})$ when $m=O(1)$, giving a smooth asymptotic transition from the vanilla case $m=0$ to a single outlier.","If the supplied vanilla coreset construction is deterministic, the entire robust coreset construction is deterministic as well."],"supporting_citations":[{"why":"Supplies the vanilla coreset framework the paper plugs in to get the near-linear-in-k robust size bounds in Euclidean and doubling metrics.","marker":"[CSS21]"},{"why":"Provides the recent vanilla coreset bounds for minor-free and general metric spaces that the black-box reduction converts into robust coresets.","marker":"[CDR+25]"},{"why":"Gives the previous near-optimal robust coreset bound whose k^3 dependence the paper's near-linear bound improves.","marker":"[HJLW23]"},{"why":"Gives the latest robust coreset bound with k^2 dependence, the baseline against which the paper's first near-linear result is measured.","marker":"[HLLW25]"},{"why":"Supplies the near-tight lower bound for vanilla coresets used to argue the additive robust term is asymptotically dominated when m is constant.","marker":"[CLSS22]"},{"why":"Provides the sparse partition theorem used by Reduction II to group parts and keep the required number of centers down to O(k log n).","marker":"[JLN+05]"},{"why":"Supplies the consistent-hashing and two-level l0-sampler subroutines that make the streaming implementation space-efficient.","marker":"[CFJ+22]"},{"why":"Gives the constant-factor tri-criteria approximation to robust clustering that both reductions require as input C*.","marker":"[BVX19]"},{"why":"Dynamic streaming coreset construction for vanilla k-Median that, combined with Theorem 5.1, yields the first dynamic streaming robust k-Median algorithm.","marker":"[BFL+17]"},{"why":"Dynamic streaming coreset construction for vanilla k-Means that, combined with Theorem 5.1, yields a similar first result for robust k-Means.","marker":"[HSYZ18]"}],"fun_headline_variants":["Black-box trick shrinks robust clustering coresets to near-linear","Robust coresets go near-linear via vanilla black box","Outlier-robust clustering coresets now near-linear size","First streaming coresets for robust k-means and k-median","Black-box reduction yields near-linear robust coresets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Both reductions assume as input a constant-factor approximation to the robust clustering instance with a constant-factor violation on the number of outliers, and the second reduction also assumes the metric admits separated duplications whose coreset complexity is comparable to the original metric; if either assumption fails, the stated size bounds do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Black-box trick shrinks robust clustering coresets to near-linear","Robust coresets go near-linear via vanilla black box","Outlier-robust clustering coresets now near-linear size","First streaming coresets for robust k-means and k-median","Black-box reduction yields near-linear robust coresets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000981,"raw_usage":{"total_tokens":4363,"prompt_tokens":1340,"completion_tokens":3023,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":956,"completion_tokens_details":{"reasoning_tokens":2940}},"tokens_in":956,"tokens_out":3023,"duration_ms":20399,"temperature":1.0,"reasoning_tokens":2940,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:57:34.266778+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a metric from the paper's list where every $\\epsilon$-coreset for $(k,z,m)$-Clustering provably needs $\\Omega(k^2)$ points while vanilla coresets of size $O(k\\,\\mathrm{poly}(\\epsilon^{-1}))$ exist; Theorem 1.1 predicts near-linear dependence on $k$ in all listed metrics, so such a lower bound would refute the central claim.","supporting_citations":[],"review_version":1}