acceptodds
Under review as a conference paper at ICLR 2027

Approximation-Preserving Consistent Clustering with Optimal Deletion Guarantees

Abstract

Online clustering must adapt as new points arrive. Even a single insertion can trigger many center replacements. Consistent clustering seeks a good solution at every step while limiting center recourse, the total number of new centers introduced over time. For insertion-only -clustering, including -median and -means, Chan et al. (2025) convert an offline -approximation into an online algorithm, but the approximation factor becomes . We improve this factor to for arbitrarily small , preserving the quality of the offline solver while retaining controlled recourse. The central difficulty is freeing room for new centers before knowing which old centers a future solution can reuse. Our BudgetDelete routine frees capacity within a prescribed cost budget, without an additional clustering oracle, and provides a deletion guarantee that holds for every comparison solution. This guarantee is tight in its budget and geometric separation parameters, up to constants depending on . Local cost comparisons at multiple distance scales then certify when old centers can replace newly computed ones with little additional cost. On a common weighted-epoch interface, the exponent of in the proved recourse bound decreases from to for -median and from to for -means. To isolate the cost of accuracy, we consider a single center with points arriving at consecutive integer locations on the real line. Even in this elementary setting, maintaining near-optimal squared loss requires accuracy-dependent recourse, for which we establish matching upper and lower bounds. On three UCI datasets with , our practical variant uses one shared parameter setting and reduces accumulated smoothed coreset cost by to and center recourse by to relative to the released Chan et al. (2025) heuristic, with lower recorded update-loop computation.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
clustering, consistentcy clustering, online algorithm

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_3oegOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper presents an online algorithm for (k,z)-clustering, where z=1 indicates k-median and z=2 indicates k-means. Assuming an alpha-approximation algorithm for offline (k,z)-clustering, the proposed online algorithm claims a (1+epsilon)alpha approximation algorithm for the online (k,z)-clustering problem.

Critical strengths

(Online) clustering is a fundamental ML primitive, and the claimed result is a good improvement over the state-of-the-art.

Critical weaknesses

Unfortunately, the paper is not comprehensible. There is too much unconventional notation (for example, what does "positive records" stand for?). The development follows a non-logical sequence of steps, where claims are made and concepts are discussed without having been defined earlier. The precise streaming setting is not defined. The optimization objective for the online problem is not precisely defined. A lot of notation that is used is not defined. Math concepts are defined without proper discussion of what they mean. The claimed result sounds interesting, but unfortunately it is not possible to follow the logical flow.

Questions for authors

I do not have concrete questions, since the convoluted and non-conventional writtng does not allow understanding the paper.

2 comments

The review states that the streaming setting and optimization objective are not defined. These statements are contradicted by Section 3 of the original submission. All line references below refer to that version.

Specifically, lines 134–135 define the metric space and fixed feasible-center set. Lines 139–143 introduce the weighted input and explicitly display the clustering objective and optimum. Lines 145–150 specify the output cardinality constraint and define cumulative center-addition recourse. Theorem 3.1 then states the approximation guarantee at every prefix and the recourse bound. These definitions are in the main paper, before the algorithm and its analysis.

“Positive records” means points with positive weights, represented as pairs (p,w)(p,w) in line 139. We can make this wording more explicit, but a terminology clarification does not justify the assertion that the model and objective are undefined.

The review also assigns the lowest soundness score without identifying a specific incorrect claim, invalid proof step, or missing assumption. We ask the reviewer to correct the statements above and reassess the evaluation accordingly. Any remaining soundness concern should identify the mathematical claim or argument in question so that we can respond substantively.

Dear Reviewer 3oeg,

Thank you for your review.

The authors have responded to your concerns and revised the manuscript. Could you please check whether these revisions address your main concerns?

Your feedback would be appreciated.

Regards, AC

Reviewer_djBUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies insertion-only consistent clustering, where clustering quality must remain good at every prefix while limiting cumulative center-addition recourse. Its central result improves the offline-to-online conversion guarantee from $ (1+\varepsilon)\alpha^2$ to $(1+\varepsilon)\alpha, $ for an offline α\alpha-approximation oracle.

The approach combines budgeted center deletion, a deletion certificate that holds simultaneously for future comparison solutions, and multiscale witnesses for reusing existing centers. On a common weighted-epoch interface, it reduces the precision exponent in the recourse bound from six to three for kk-median and from fourteen to five for kk-means.

Critical strengths

S1. The main approximation improvement is clear and significant.

S2. The simultaneous deletion certificate is valuable. Deletions are selected before the future comparison solution is known, yet the guarantee remains valid against every such solution.

S3.The analysis covers several interacting sources of recourse.

Critical weaknesses
  1. The main experiments do not directly evaluate the complete theoretical algorithm. The practical method replaces BUDGETDELETE and multiscale witnesses with direct cost tests and uses a heuristic endpoint solver. Consequently, its empirical improvements do not establish the computational effectiveness of the central theoretical machinery. The fixed-snapshot deletion study helps, but does not replace an end-to-end evaluation of the converter.

  2. IN the empirical experiments, parameters are selected on the benchmark collection itself, and each dataset uses one fixed order and seed. Improvements across all nine settings are encouraging; but additional independent orders and initializations are not considered.

  3. The bound depends on the number mm of weighted records $ O_z!\left( kHL+\frac{\alpha mL}{\varepsilon^{2z+1}}+mL^2 \right). $ Its implications for raw streams therefore depend on the summary’s update and reset behavior.

Questions for authors
  1. Can a concrete coreset construction be instantiated to give complete recourse, space, and total-time bounds in terms of the original stream size and accuracy parameters?

  2. Can the full theoretical converter be evaluated on moderate-sized instances to quantify deletion and witness-maintenance overhead?

  3. Do the joint improvements persist with parameters fixed in advance and across multiple independent stream orders and random seeds?

2 comments

Thank you for recognizing the significance of the approximation improvement and the simultaneous deletion certificate. Several supporting analyses and detailed experimental results are provided in the appendices. All references below are to the revised manuscript.

1. Coreset composition and computational bounds. Appendix E explicitly accounts for the summary’s evolution. Theorem E.2 (p. 21) bounds recourse in terms of the total number of delivered weighted records and the optimum growth within each reset epoch. Equation (23) (p. 22) gives total time in terms of summary construction time, record count, reset count, and maximum intermediate support size. Thus, updates and resets are included in the composition, rather than treating coreset size alone as sufficient.

Appendix H also provides implementation and storage bounds. Outside the endpoint solver, working storage is O(N+f+k2+kL)O(N+f+k^2+kL), where NN is the maximum demand support size and ff is the number of feasible facilities. Corollary H.3 (p. 29) gives total-time bounds directly for nn original points. A specific coreset construction would instantiate the summary-dependent quantities in Appendix E. The current statement keeps these quantities explicit so that both summary updates and their computational costs remain visible.

2. Evaluation of the theoretical machinery. The main experiments follow the benchmark setting of Chan et al. (2025) and compare the practical methods under common evaluation. The original BudgetDelete routine is evaluated separately against exact maximum deletion capacity under the same cost budget. Appendix I.1 (pp. 30–31) reports 45 snapshots across five budgets, giving 225 settings. All satisfy the cost and reassignment-budget checks, and the mean fraction of exact deletion capacity attained is 0.6852 over the 162 positive-capacity settings.

For witness-maintenance overhead, Table 3 (p. 28) gives the operation-level costs. Constructing or validating one witness takes O(fNL)O(fNL), and a RESTORE call takes O(k2fNL+k3)O(k^2fNL+k^3), including unsuccessful validity checks. Proposition H.1 (p. 27) combines these costs with deletion and endpoint calls into a total-time bound. This supplies analytical accounting of the full converter alongside the empirical evaluation of deletion and the practical implementation.

3. Parameter selection and additional experimental evidence. The evaluation extends beyond the selected shared configuration. Figure 2 (p. 10) and Appendix I.2 report a common 7×77\times7 parameter sweep on each dataset, giving 147 configurations at k=10k=10. All configurations are retained, including dominated points. Across the sampled frontiers, moving from minimum cost to minimum recourse reduces recourse by 38.6%–43.6%, with a 4.0%–6.3% increase in cost AUC.

Table 5 (p. 32) provides the complete results for all nine dataset/kk combinations, and Figures 4–5 (p. 33) show cost and recourse trajectories at k=10k=10. These results document performance across parameter choices and throughout the streams. The shared configuration uses no separate tuning for individual dataset/kk combinations. Additional independent orders and initializations would complement this parameter-sensitivity analysis.

Thank you for the clarification. I now have a better understanding of the paper and will maintain my positive score.

Reviewer_tSYFOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The main contribution of the paper is to design a framework to convert an offline algorithm for (k,z)(k,z)-clustering with approximation factor α\alpha to an online algorithm for consistent clustering with approximation (1+ε)α(1+\varepsilon) \alpha and low recourse.

A consistent clustering instance consists of an (insertion-only) stream of (possibly weighted) data points, which are elements of a metric space, and the goal is to design online clustering algorithms that retain a good approximate solution after each step, while minimizing the center recourse, i.e. the total number of updates to the set of centers of the clustering throughout the processing of the input stream. The main result of the paper improves upon prior work by Chan et al. (ICLR 2025), who design an algorithm that gets an (1+\varespilon)α2(1+\varespilon)\alpha^2 approximation. The main ingredient of the algorithm (in this paper) is the BudgetDelete procedure that deletes centers from the current center set to free room for centers that serve future arrivals. The authors also test a practical "variant" of their algorithm with an algorithm from prior work.

Critical strengths
  • The main result improves the approximation ratio obtained in prior work (Chan et al. 2025) and the BudgetDelete procedure is interesting.
Critical weaknesses
  • The paper is very badly written and very hard to follow. Here are a few examples:
  1. Section 5 starts: "A phase starts from a robust snapshot U, which stores centers and their local reuse certificates, called witnesses." Here, neither "robust snapshot" nor "witnesses" are defined in the main paper. Witnesses are described vaguely in the next paragraph by: "witnesses store local one-center comparisons on balls whose radii double at each level. Low-cost balls use exact local optimization. On high-cost balls, the existing cost absorbs small displacement.", which is vague and does not capture the real definition (Definition B.1.). Robust snapshot is also not defined in the main paper, despite being used in Theorem 5.1. in the main paper. It is first defined in line 713 in the appendix, not even as a stand-alone definition.
  2. Algorithm 1, which is the main algorithm introduced in the paper, is not well defined and explained. Although the figure is in the main paper, the functions RESTORE and TERMINALUPDATE are only defined in the appendix. In particular, RESTORE is defined in line 713 in the running text of the appendix, which reads: "The procedure RESTORE(P, C) repeatedly selects an invalid center x, replaces it by the first point of BUILDWITNESS(P, x, tC (x)), and stores the generated sequence.". This means that RESTORE not only is defined in the running text and not in a separate figure for clarity, but it also depends on another algorithm BUILDWITNESS. Now, BUILDWITNESS is again introduced in a definition in the appendix (Definition B.1.) and not displayed as pseudocode for clarity. Moreover, TERMINALUPDATE uses RESTORE, making Algorithm 1 almost impossible to follow. These algorithms are not motivated in the main paper in an understandable way.
  3. Some phrases are used without ever being defined explicitly. For example, line 316: "influence balls" and "construction balls" seem to not have an explicit definition, not even in the appendix (definitely not in the main paper). Also, what is a "normal endpoint"?
  4. There are several sentences throughout the paper that are vague and dense, with no clear meaning. For example, line 315: "A lineage tracks a retained center’s versions" or line 156: "Oracle correctness is deterministic unless a simultaneous success event is stated."

All the above make the exposition extremely difficult to understand and a significant effort is required to make the paper presentable.

  • Section 7.1. starts as follows: "To reduce update overhead, OURS replaces the deletion and multiscale witness machinery of Theorem 3.1 with direct cost tests." The deletion and multiscale witness machinery seem to be vital parts of the algorithm and it is not clear whether the "practical variants" can even be considered variants and not different algorithms. Moreover, β\beta and η\eta defined in line 385 seem to play a different role than the β\beta and η\eta of the theoretical algorithm, which is missleading.
Questions for authors

There are no questions whose answers can affect my assessment.

3 comments

Thank you for recognizing the improvement in the approximation guarantee and the interest of BudgetDelete. Your examples identify concrete places where the presentation required too much movement between the main text and the appendices. We have substantially reorganized Section 5 and clarified the practical implementation. All page references below refer to the revised manuscript.

1. Witnesses and robust snapshots are now explicitly defined in the main text (Section 5, p. 5).

Under the original nine-page limit, we placed several definitions and subroutine details in the appendix. This made the main algorithm difficult to follow without consulting those details. We have used the additional page available for the rebuttal revision to bring the definitions needed to understand the algorithm into the main text.

Section 5 now gives the exact witness construction rule, including the local cost threshold, the one-center minimization step, and tie-breaking. It then defines a robust snapshot for a specified dataset and distinguishes the witness length required for validity from the longer length generated during restoration. BUILDWITNESS and RESTORE are described explicitly before Algorithm 1. The reader can therefore interpret the algorithm and Theorem 5.1 using definitions already available in the main text.

2. The complete update procedure now precedes its analysis (Section 5, pp. 5–7).

We now describe TERMINALUPDATE before Algorithm 1, including the growth-restart test, the normal-endpoint branch, clean and dirty clusters, center substitutions, witness preservation, and restoration on the updated dataset. “Normal endpoint” is explicitly the branch in which the growth-restart test does not hold.

We also distinguish the saved snapshot from the working center set and explain when internal deletions become visible in the reported solution. The exposition now proceeds from definitions to the complete algorithm, followed by the approximation guarantee and recourse analysis. This makes the roles and dependencies of the subroutines explicit without requiring the reader to reconstruct them from the proofs.

3. We have clarified the terminology and compressed sentences identified in the review.

Section 3 (p. 3) now explains the oracle condition directly: the guarantees are deterministic when every oracle call satisfies its approximation bound; for a randomized oracle, they are conditional on all calls satisfying that bound simultaneously.

Appendices B and C (pp. 14–16) now explicitly introduce construction balls, influence balls, lineages, descendants, and versions before their use. In particular, a lineage follows a center through successive replacements, while a version consists of a center and its stored witness. The main-text recourse discussion focuses on the sources of center additions, with the detailed maintenance accounting developed in the appendices.

4. We have clarified the relationship between the theoretical converter and the practical method (Section 7.1, p. 8).

The practical method uses direct cost tests to decide when to recompute centers and when to accept a candidate. It implements the quality–stability tradeoff without constructing the deletion sets or multiscale witnesses required by the theoretical converter. We now explain these operations directly and distinguish the internal method, OURS, from the output-stabilized method, OURS-H.

We also explicitly distinguish the parameter roles. In the practical implementation, β and η determine the refresh threshold, and β also determines the required cost improvement. In the theorem, they control deletion and witness-reuse budgets. The revised text makes this distinction explicit.

The empirical comparison concerns the practical method. The original BudgetDelete routine is evaluated separately against exact deletion capacity in Section 7.4 and Appendix I.1, while Appendix H accounts for the computational costs of the full theoretical converter. The practical experiments do not inherit Theorem 3.1’s approximation guarantee.

These revisions preserve the original algorithm, theoretical guarantees, and experimental results. We ask you to reassess the presentation and soundness evaluation in light of the explicit definitions and complete algorithm description, and would welcome any remaining concern tied to a specific mathematical statement or proof step.

Dear Reviewer tSYF,

Thank you for your review.

The authors have responded to your concerns and revised the manuscript. Could you please check whether these revisions address your main concerns?

Your feedback would be appreciated.

Regards, AC

I thank the authors for their response. However, I think that the original submission was not understandable (I discussed this in detail) and that a significant restructuring had to take place to address my concerns. I also think that the algorithm tested in the experiments still differs significantly from the theoretical algorithm. For these reasons, I retain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.