{"id":"68e2a464-4819-4c32-a3f6-dfe704495ae2","arxiv_id":"2607.04949","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Predicted centers from prior snapshots enable sensitivity-sampling coresets for k-means that match optimal size bounds under coarser approximations and deliver better cost-runtime tradeoffs on data sequences.","lead":"The paper shows that predicted centers from a past data snapshot can replace expensive bi-criteria approximations inside sensitivity sampling, still yielding near-optimal coresets for k-means. This cuts runtime on sequences of related datasets while matching state-of-the-art clustering quality.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper’s strongest claim is the combination of Theorem 2 (optimal coreset size under relaxed polylog bi-criteria quality) and the natural prediction mechanism of Corollary 1. The only soft spot is the i.i.d. assumption needed for the transfer guarantee, which the authors already surface, quantify via drift, and illustrate experimentally. Because Theorem 2 itself accounts for inaccurate predictions, the algorithmic contribution remains intact even when the transfer fails. The analysis is a careful but non-trivial adaptation of Bansal et al., the experiments are extensive and reproducible, and no internal contradiction or missing technical step was found. Consequently the reader’s ACCEPT verdict with high confidence stands; no adjustment is warranted.","tokens_in":42330,"tokens_out":536,"duration_ms":4895,"concrete_test":"Independently re-derive the coreset-size dependence on α and β in Theorem 2 (Appendix B) starting from the probability distribution of Alg. 1 and the event-E properties (Lemmas 1–6); verify that the factor eta·max(1,α^{2}) is necessary and that the final Õ(k ε^{-2} min(√k, ε^{-2})) bound continues to hold under the stated polylog regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption correctly flags the i.i.d. same-distribution model of Corollary 1 / Theorem 3, but this is already treated carefully by the paper itself: the authors explicitly discuss distribution drift (Section 4.1, \"Relaxing the Fixed Distribution Assumption\"), note that an additive discrepancy term appears, and show experimentally that the method degrades precisely when the predicted centers become a poor bi-criteria approximation (IntelLab, cost ratios 120\times–10 000\times). Theorem 2 already quantifies the price of inaccurate predictions (coreset size multiplies by eta·max(1,α^{2}) for α,β = O(polylog(k/ε))), so the formal guarantees remain internally consistent. The central algorithmic claim—that a prediction of polylog quality still yields the optimal coreset size of Bansal et al.—is supported by a careful adaptation of the sensitivity-sampling analysis and is not undermined by the transfer assumption. No hidden inconsistency or unstated bound appears to threaten the strongest claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces PreSenS, a sensitivity-sampling algorithm for Euclidean k-means coresets that replaces the usual bi-criteria approximation step with a predicted set of centers A. Theorem 2 shows that if cost(P,A) ≤ α OPT_k(P) and k ≤ |A| ≤ βk with α,β = O(polylog(k ε^{-1})), then m = Õ(k ε^{-2} min(√k, ε^{-2})) samples still yield an ε-coreset w.h.p., matching the optimal subset-coreset size of Bansal et al. Corollary 1 (via Ben-David’s statistical clustering framework) asserts that an (α,β)-bi-criteria solution computed on one large i.i.d. sample from an unknown distribution D remains an (O(α),β) solution on a later independent sample of comparable size. Experiments on five real snapshot sequences demonstrate that reusing centers from the first snapshot yields clustering costs competitive with recomputing k-means++ each time, while reducing total coreset-construction time by roughly 3.5–5×.","tokens_in":42470,"tokens_out":733,"duration_ms":10670,"significance":"If the claims hold, the work supplies a practical and theoretically justified way to amortize the dominant cost of sensitivity sampling across a sequence of related datasets—an increasingly common setting (sensor streams, daily/monthly aggregates). The extension of the Bansal et al. coreset-size bound from constant-factor to polylog-factor approximations is a clean technical contribution that immediately justifies the use of noisy predictors. The transfer theorem is a careful, non-circular application of existing statistical-clustering machinery, and the experimental suite (means + 95 % CIs, multiple coreset sizes, distortion estimates, unique-point counts, publicly released C++ code) is thorough and reproducible. These strengths make the paper a solid addition to both the coreset literature and the algorithms-with-predictions literature.","major_comments":[],"minor_comments":[{"comment":"Several typographical errors appear in the main text and appendix (e.g., “unkwown”, “distorsions”, “PreSenS” inconsistently capitalized, “eO” vs. Õ). A careful proof-reading pass would improve readability.","section":null},{"comment":"Figure 1 and Figure 2 use log-scale cost/distortion ratios; the absolute costs (or at least the absolute cost of the full-dataset baseline) would help readers judge practical relevance on the larger NYC TLC instances.","section":null},{"comment":"Section 4.1 briefly discusses distribution drift and an additive discrepancy term, but never states an explicit quantitative bound. Adding a short corollary that makes the additive term precise would strengthen the “Relaxing the Fixed Distribution Assumption” paragraph.","section":null},{"comment":"In Algorithm 1 the probability formula mixes four terms whose relative weights are fixed at 1/4; a one-sentence justification (or a pointer to the corresponding calculation in Bansal et al.) would help readers who have not memorized that paper.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean, well-executed contribution that sits comfortably at the intersection of coresets and algorithms-with-predictions. I see no reason to delay acceptance; the minor presentation issues can be fixed in camera-ready."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a practical algorithms-with-predictions paper that actually ships something usable. The new pieces are Theorem 2 (optimal coreset size still holds when the bi-criteria approximation is only polylog rather than constant) and the transfer result (Corollary 1) that centers good on one large i.i.d. snapshot remain good on the next. Both are carefully adapted from Bansal et al. (FOCS 2024) and Ben-David’s statistical clustering framework; the chaining/net/symmetrization argument tracks the extra α,β factors correctly and the proofs look solid.\n\nWhat they do well is keep the claim proportional. They never pretend the prediction is free or perfect: Theorem 2 already multiplies the sample size by β·max(1,α²), and they explicitly discuss distribution drift, noting that an additive discrepancy term appears and that guarantees degrade exactly when the predicted centers become a poor bi-criteria approximation. The IntelLab experiments show this cleanly (cost ratios 120×–10k×) while the other four sequences stay stable. Runtime gains of 3–5× versus recomputing k-means++ each time, with matching clustering cost and estimated distortion, are real and measured with means + 95 % CIs. Code is public.\n\nSoft spots are minor and already flagged by the authors. The i.i.d. same-distribution model is the weakest modeling assumption; under strong drift the formal transfer fails, though the method still degrades gracefully and Theorem 2 continues to apply. The experiments are confined to sequential snapshots, which is exactly the setting they target, so that is not a flaw. No circularity, no free parameters, citation pattern is appropriate.\n\nThis is for people who build large-scale or streaming clustering pipelines and already use sensitivity coresets. It is not a foundational breakthrough, but it is a clean, well-supported engineering-theory hybrid that deserves a serious referee. I would accept it for peer review and would cite the transfer + polylog-relaxation results if I were working on predicted coresets or sequential clustering.","headline":"Solid, usable speed-up for sensitivity coresets on sequential data; theory cleanly extends Bansal et al. to polylog-quality predictions and the experiments back it up.","tokens_in":43157,"tokens_out":526,"would_cite":true,"duration_ms":6339,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Predicted centers from one snapshot let sensitivity sampling build optimal-size k-means coresets on later snapshots without recomputing a bi-criteria approximation.","keywords":["k-means clustering","coresets","sensitivity sampling","algorithms with predictions","bi-criteria approximation","streaming snapshots"],"falsifier":"On a sequence of large i.i.d. samples from a fixed distribution with positive OPT, measure whether centers that are a constant-factor bi-criteria approximation on the first sample remain an O(1)-factor bi-criteria approximation on later samples and whether the resulting PreSenS coresets achieve the same clustering cost as full sensitivity sampling; a large, consistent gap on either measure falsifies the claim.","tokens_in":43156,"feed_emoji":"⚡","tokens_out":679,"duration_ms":5758,"temperature":0.7,"pith_summary":"Sensitivity sampling builds small weighted coresets for k-means by sampling points with probability proportional to their importance (sensitivity). Computing those importances requires a good approximate clustering, which is the dominant cost. This paper shows that a coarser approximation than previously required is still enough to obtain the best-known coreset size, and that centers already computed on an earlier large sample from the same distribution serve as such an approximation on later samples. The resulting algorithm, PreSenS, therefore reuses historical centers as predictions, skips the expensive re-approximation step, and still produces theoretically optimal coresets. Experiments on sequences of real data snapshots confirm that the method matches the clustering quality of full sensitivity sampling while running several times faster, and far outperforms uniform sampling on uneven data.","feed_headline":"Old centers speed up k-means coresets on new data","feed_subtitle":"Sensitivity sampling reuses past centers as predictions and still matches optimal coreset size","key_machinery":"PreSenS: a sensitivity-sampling coreset algorithm whose sampling probabilities are computed from a supplied set of predicted centers rather than from a bi-criteria approximation recomputed from scratch; the size guarantee holds under the relaxed polylogarithmic approximation regime of Theorem 2, and the predictions are justified by the distributional transfer result of Corollary 1.","core_discovery":"If a set of predicted centers A satisfies cost(P,A) ≤ α OPT_k(P) with k ≤ |A| ≤ βk and α,β only polylogarithmic in k/ε, then sensitivity sampling with the induced probabilities still yields an ε-coreset of the optimal size Õ(k ε^{-2} min(√k, ε^{-2})). Moreover, when successive point sets are large i.i.d. draws from the same unknown distribution, centers that form an (α,β) bi-criteria approximation on one set remain an (O(α),β) bi-criteria approximation on the next, with high probability.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Old centers predict sensitivities for faster k-means coresets","Reuse prior centers to accelerate sensitivity sampling","Predicted centers still yield optimal-size ε-coresets","Past bi-criteria centers cut coreset runtime on new draws","Noisy center predictions suffice for sensitivity sampling"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"Successive data sets must be large enough independent draws from essentially the same fixed distribution; if the distribution drifts substantially, the old centers stop being a good approximation and the coreset guarantees no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Old centers predict sensitivities for faster k-means coresets","Reuse prior centers to accelerate sensitivity sampling","Predicted centers still yield optimal-size ε-coresets","Past bi-criteria centers cut coreset runtime on new draws","Noisy center predictions suffice for sensitivity sampling"]},"model":"grok-4.5","effort":"low","cost_usd":0.007088,"raw_usage":{"total_tokens":1850,"prompt_tokens":907,"num_sources_used":0,"completion_tokens":77,"cost_in_usd_ticks":70880000,"prompt_tokens_details":{"text_tokens":907,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":866,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":907,"tokens_out":77,"duration_ms":6458,"temperature":1.0,"reasoning_tokens":866,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T11:02:21.899032+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a sequence of large i.i.d. samples from a fixed distribution with positive OPT, measure whether centers that are a constant-factor bi-criteria approximation on the first sample remain an O(1)-factor bi-criteria approximation on later samples and whether the resulting PreSenS coresets achieve the same clustering cost as full sensitivity sampling; a large, consistent gap on either measure falsifies the claim.","supporting_citations":[],"review_version":1}