acceptodds
Under review as a conference paper at ICLR 2027

Clustering with Outliers on Sliding Windows

Abstract

We study sliding window algorithms for -clustering with outliers in Euclidean spaces, and focus on constructing -coresets, which is a powerful notion of data reduction for clustering. Our main result is an algorithm that maintains an -coreset of size , and this readily yields a -approximate solution center set. We evaluate our algorithm for -means with outliers on five real data sets with injected outliers, the experiment result shows that it has lower empirical cost than uniform sampling and coreset for vanilla -means at every tested coreset size.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
clustering with outliers, sliding window model

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_EY2rOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies sliding-window coresets for clustering with outliers in streaming data. Its main contribution is the first nontrivial sliding-window coreset for this problem. The key idea is to reduce sliding-window design to a mergeable prefix-query summary and to modify an existing reduction so that merges move points only from explicit storage to the compressed part. The algorithm uses isolation, sparse, and vanilla layers with compact histories to support prefix queries and merges. Theoretically, it returns a coreset after every update with high probability, with space and size comparable to the insertion-only setting.

Validation is experimental. On five real datasets with injected synthetic outliers, for robust mean clustering, the method outperforms uniform sampling and an online vanilla coreset, and is slightly worse than an offline robust coreset while supporting sliding-window queries. The main limitation is that experiments cover only low-dimensional, medium-scale data with synthetic outliers, so generalizability is not fully demonstrated.

Critical strengths

The authors do clearly articulate the core idea in the Technical overview and the “Our idea” paragraph: reduce sliding-window design to a mergeable prefix-query summary, and ensure merges move points only from explicit storage to the compressed part. I approve this idea , but the key sentence is not intuitive enough, is not friendly to readers of other domain.

Strength. The paper establishes the first nontrivial sliding-window coreset for (k,z,m)-clustering, with space and coreset-size bounds comparable to the insertion-only setting. It also conveys a key conceptual insight—reduce sliding-window clustering to a mergeable prefix-query summary, and enforce monotone movement of points from explicit storage to the compressed part—which explains why the summary is mergeable and why outliers can be handled safely.

Critical weaknesses

The authors do not clearly and centrally state the problem addressed by this paper in the abstract, introduction, or a standalone problem definition section; instead, the problem setup is scattered across the Main result, the Technical overview, and several definitions.

The paper does not sufficiently demonstrate applicability or generalizability. The concrete algorithm is tied to Euclidean consistent hashing, finite-z sum objectives, Reduction I, and a vanilla coreset black box, with experiments only on z=2, low-dimensional, medium-scale data and synthetic outliers. A scope and generalizability discussion is needed.

there is no framework figure to clearly and intuitively experss the process of the work.

Questions for authors

How generalizable is the algorithm beyond Euclidean consistent hashing, finite-z sum objectives, and the vanilla coreset black box? Which components are essential limitations versus replaceable, and what are the main obstacles for general metrics, high-dimensional data, larger z, and realistic outlier patterns?

2 comments

The authors do not clearly and centrally state the problem addressed by this paper in the abstract, introduction, or a standalone problem definition section; instead, the problem setup is scattered across the Main result, the Technical overview, and several definitions.

The opening of the Introduction defines clustering with outliers and describes the sliding-window setting. The Introduction is self-contained in this regard. We revisit these concepts later to formalize the definitions used in the analysis.

The paper does not sufficiently demonstrate applicability or generalizability. The concrete algorithm is tied to Euclidean consistent hashing, finite-z sum objectives, Reduction I, and a vanilla coreset black box, with experiments only on z=2, low-dimensional, medium-scale data and synthetic outliers. A scope and generalizability discussion is needed.

We will add a generalizability discussion in the next version. Specifically, we discuss the following aspects from the experiments.

The setting: Euclidean kk-means is arguably the most widely used clustering method, among all metric (k,z)(k, z)-clustering variants. This also covers a wide range of practical applications. Moreover, given the similar structure among (k,z)(k, z)-clustering, a good performance of kk-means (z=2)(z = 2) often translates to other general zz. More specifically, our analysis indicates that z=1z=1 and settings without synthetic outliers are easier than those in our original experiments, and that increasing the dataset size poses no additional difficulty for the approximation guarantee. We therefore focused our original experiments on the more challenging settings.

The planted outlier: We also designed our experiments to test whether our algorithm can still achieve good approximation ratios under extreme outlier conditions, where baselines such as uniform sampling perform poorly. This demonstrates our generalizability to the worst-case outliers.

There is no framework figure to clearly and intuitively experss the process of the work.

We will add a figure illustrating the framework in the revised version.

Thanks for your feedbacks, my conserns are addressed.

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

This study introduces a novel sliding-window algorithm for (k,z)(k, z)-clustering with mm outliers in Euclidean spaces. The authors construct an ϵ\epsilon-coreset that achieves a space complexity comparable to that of insertion-only streams. The methodology hinges on a "mergeable coreset summary" that adapts a sliding-window framework for vanilla clustering. By modifying a recent outlier reduction technique, the authors ensure that data points only ever transition from explicitly stored outer sets to compressed inner sets during merges, bypassing historical data-recovery issues. The proposed algorithm yields a coreset size bounded by O~(k/min⁡{ϵ4,ϵ2+z}+2O(zlog⁡(z+1))(dz+kd)m/ϵ)\tilde{O}(k/\min\{\epsilon^4, \epsilon^{2+z}\} + 2^{O(z \log(z+1))}(d^z + kd)m/\epsilon). Empirical evaluations on robust kk-means across five datasets demonstrate that this approach consistently outperforms uniform sampling and vanilla online coresets.

Critical strengths
  • The one-way transition mechanism that move points only from explicitly stored regions (outer/sparse) to the compressed vanilla coreset (inner/dense) is a concise solution to the mergeable summary challenge.
  • The first term of the space complexity (kmin⁡{ϵ4,ϵ2+z}\frac{k}{\min\{\epsilon^4, \epsilon^{2+z}\}}) nearly matches the theoretical lower bound for vanilla clustering coresets in the linear-kk regime, up to an ϵ\epsilon factor.
Critical weaknesses
  • This work lacks a comparison with fully dynamic coreset methods, as the sliding-window streaming model can be viewed as a special case of the fully dynamic one [1, 2]. Including such a comparison would provide a more comprehensive assessment of the proposed method’s performance and clarify its advantages in the sliding-window setting.
  • The coreset size bound suffers from a linear dependence on the outlier budget mm and a heavy polynomial/exponential dependence on dimensionality dd (scaling with dzmd^z m). This could bottleneck the algorithm on high-dimensional data with large outlier budgets.
  • The framework requires generating a family of LoptL_{opt} optimum guesses and running the fixed-guess construction in parallel for all of them. While the mathematical size bounds account for returning a single successful guess, the practical computational cost and memory overhead of maintaining this parallel architecture during real-time streaming is not addressed in the text.

[1] Fully-Dynamic Coresets

[2] Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems

Questions for authors
  • How does the necessity of maintaining parallel summaries for a family of LoptL_{opt} guesses impact real-time processing latency and actual memory usage in practice?
  • In the sliding window reduction, how sensitive is the algorithm's empirical performance and failure rate to the choice of the internal accuracy parameter ϵ0=c0ϵ/log⁡W\epsilon_0 = c_0 \epsilon / \log W
  • see the weakness part
2 comments

This work lacks a comparison with fully dynamic coreset methods, as the sliding-window streaming model can be viewed as a special case of the fully dynamic one [1, 2]. Including such a comparison would provide a more comprehensive assessment of the proposed method’s performance and clarify its advantages in the sliding-window setting.

We added experiments comparing our method with fully dynamic algorithms.

The coreset size bound suffers from a linear dependence on the outlier budget mm and a heavy polynomial/exponential dependence on dimensionality dd (scaling with dzd^z). This could bottleneck the algorithm on high-dimensional data with large outlier budgets.

In the new experiments, we add new datasets with d=45d=45 and 115115. The experiment result shows that our algorithm requires much smaller coreset size than the theoretical bound might suggest.The dzd^z factor in the theoretical bound comes from the choice of parameters for consistent hashing. In practice, smaller parameter values usually suffice. The linear dependence on mm is necessary.

The framework requires generating a family of LoptL_{\mathrm{opt}} optimum guesses and running the fixed-guess construction in parallel for all of them. While the mathematical size bounds account for returning a single successful guess, the practical computational cost and memory overhead of maintaining this parallel architecture during real-time streaming is not addressed in the text.

Regarding the guess for LoptL_{\mathrm{opt}}, the theoretical algorithm maintains multiple guesses in parallel. In our experiments, we used a single fixed guess throughout each run to make the comparison with the other algorithms fair, which means a single guess is sufficient to obtain good results. We will clarify this choice in the experimental section. The empirical approximation ratio increased only slightly over the range of deviations from OPT\mathrm{OPT} that we tested. In practice, when OPT\mathrm{OPT} changes gradually across windows, one could maintain a small number of guesses and adjust them up or down based on recent window costs.

Thank you for your additional work. My initial rating was positive, and I am happy to maintain it.

Reviewer_nzRyOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers constructing coresets for robust clustering in sliding window model. Using k-means with m outliers in d dimensional Euclidean space as an example, the result is a coreset of size O~(kϵ−4+ϵ−1(kmd+d2))\tilde{O}(k\epsilon^{-4}+\epsilon^{-1}(kmd+d^2)) up to polylogarithmic factors. This is the first robust coreset in sliding window model with size comparable to the offline setting, where all we have known is that prior offline robust coresets algorithm can be converted into an insertion-only streaming coreset algorithm in a standard way. The experimental results show the algorithm outperform vanilla and uniform sampling coreset but is a little bit worse than the SOTA offline coreset.

Technically, this paper builds on a recent sliding window coreset framework of (Woodruff et al., 2023) which reduces to the construction of online coresets. The mergablity of outlier parts in offline algorithm becomes a considerable issue in the framework, authors than adapt a framework of Jiang and Lou, 2025 to resolve it.

I think the theoretical results of this paper this interesting, as it provides the first robust coresets algorithm in sliding window model and the techniques are interesting adaptions of known frameworks. I believe the theoretical results fall within the scope of ICLR.

Critical strengths
  1. The first sliding window robust coreset. Strong and interesting theoretical contributions.
  2. Interesting adaption of recent techniques in sliding window model and robust corests.
Critical weaknesses
  1. The technical contribution seems not very strong as it only combines and adapts a few known techniques from literatures.
  2. In the experimental parts, the benchmarks are uniform sampling and a vanilla sliding window coreset algorithm. Such comparisons are not convicing, as those algorithm were not designed for robust clustering in the beginning. I suggest to also compare with an outlier-aware version as in (Huang et al., 2023). For example, still maining an outer part while using uniform sampling to construct the inner part.
Questions for authors
  1. There is an unusual factor d in the coreset size. Can you figure out the source of it. Moreover can it be elimated via standard techniques such as terminal embedding?
1 comment

The technical contribution seems not very strong as it only combines and adapts a few known techniques from literatures.

We agree that our result is based on several known techniques, especially Reduction I. However, the main challenge and novelty is to make the known constructions mergeable. This has been a non-issue in offline constructions of coresets, whereas it is crucially required by the sliding window framework which we use.

In the experimental parts, the benchmarks are uniform sampling and a vanilla sliding window coreset algorithm. Such comparisons are not convicing, as those algorithm were not designed for robust clustering in the beginning. I suggest to also compare with an outlier-aware version as in (Huang et al., 2023). For example, still maining an outer part while using uniform sampling to construct the inner part.

During the rebuttal phase, we added a new baseline called OAUS (Outlier Aware Uniform Sampling), originally proposed in Huang et al. 2023, according to your suggestion. Indeed, this OAUS is an augmented uniform sampling which is outlier-aware. The new evaluation result shows that our algorithm still outperforms this baseline consistently.

There is an unusual factor d in the coreset size. Can you figure out the source of it. Moreover can it be elimated via standard techniques such as terminal embedding?

The reviewer asked about the coreset size, but this is tricky in the streaming setting which we consider. One needs to sepearte the space complexity and coreset size as two issues.

Indeed, the real challenge is to reduce the space complexity, and coreset size alone can be reduced easily. For example, one can always run another ϵ\epsilon-coreset on top of our dzd^z size coreset, denoting its size as TT, to obtain an O(ϵ)O(\epsilon) coreset with size TT which avoids the dzd^z factor. However, this method does not reduce the space compelxity of streaming, because the initial dzd^z coreset is still stored.

Now, for reducing space complexity, the standard dimension reduction is not readily applicable. For example, if one uses a Johnson-Lindenstrauss technique, it is true that one can replace dzd^z with log⁡zn\log^z n, but the coreset guarantee only holds in the low dimensional target space, instead of in the original space.

The mentioned terminal embedding is a standard approach to argue that the coreset size needs not be dependent on d. However, this coreset technique is not easily adapted to (sliding-window) streaming: terminal embedding is often used in the analyais of sensitivity sampling framework (see e.g., [1]) which is not known to apply to outlier settings, and even if it does, it requires global sensitivity score computation and is not streaming-friendly.

[1] Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, Chris Schwiegelshohn. Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds. FOCS 2024.

Comments on the paper

3 comments

We thank the reviewers for their careful reading and constructive feedback. In response to their suggestions, we have expanded the experiments with higher-dimensional datasets and additional baselines. The new results and experimental settings are summarized below. The experiment figure is updated in the appendix of our paper due to the limitation of comment in the review system.

Additional experiments

Recall that our original experiments show that Ours-SW improves on uniform sampling and vanilla online coresets for clustering with outliers, while remaining competitive with an offline robust coreset built from the full window.

We add several new datasets (Athlete-45 [1], Kitsune [2]) and baselines (OAUS [5], HK-Dynamic [6], WGD-Dynamic [7]), described below, to extend this evaluation, particularly to examine how the dimension dependence in the theoretical coreset-size bound affects performance in practice.

We re-run all experiments including those already in our submitted version, and we report the results in our paper. Our conclusion does not change significantly from the submitted version.

Datasets

  • Athlete (d=45d=45, W=5,000W=5{,}000). We use all 45 motion-sensor channels from the UCI Daily and Sports Activities dataset. The original experiment used three accelerometer channels from the same dataset. [1]
  • Kitsune Mirai (d=115d=115, W=4,000W=4{,}000). We use 115-dimensional packet feature vectors from the Mirai botnet capture in the Kitsune Network Attack dataset. [2]

For both streams, we evaluate robust kk-means with k=15k=15, outlier budget m=70m=70, and injected synthetic outliers. We evaluate the centers returned by each method on the full active window and report their costs relative to the best cost found for that window.

Baselines

AlgorithmSourceSettingBrief description
UniformStandard baselineSliding windowSamples points uniformly with fixed probability, approximately matching the number of distinct points retained by Ours-SW.
Vanilla-OnlineWoodruff et al. [3]Sliding windowApplies the same RingSample backend as Ours-SW directly to the stream.
HJLW-OfflineHuang et al. [4]OfflineBuilds a robust coreset from the entire active window using importance sampling, matching the support size of Ours-SW.
OAUS (new)Huang et al. [5]OfflineFits reference centers on the active window, retains the mm farthest points at unit weight, and fills the remaining budget by weighted uniform sampling without replacement. Notice that this is a baseline from the experiment of [5] rather than its main result.
HK-Dynamic (new)Henzinger and Kale [6]Fully dynamicUses a hierarchical coreset structure that supports insertions and deletions. Requires Ω(Wd)\Omega(Wd) space to store the full window.
WGD-Dynamic (new)Wang et al. [7]Fully dynamicUses a robust dynamic coreset framework that supports insertions and deletions. Requires Ω(Wd)\Omega(Wd) space to store the full window.

References

  1. Barshan and Altun. Daily and Sports Activities. UCI Machine Learning Repository, 2010.
  2. Mirsky, Doitshman, Elovici, and Shabtai. Kitsune: An Ensemble of Autoencoders for Online Network Intrusion Detection. NDSS, 2018.
  3. Woodruff, Zhong, and Zhou. Near-Optimal kk-Clustering in the Sliding Window Model. NeurIPS, 2023.
  4. Huang, Jiang, Li, and Wu. Towards Tight Robust Coresets for kk-Medians Clustering. ICALP, 2026.
  5. Huang, Jiang, Lou, and Wu. Near-optimal Coresets for Robust Clustering. ICLR, 2023.
  6. Henzinger and Kale. Fully-Dynamic Coresets. ESA, 2020.
  7. Wang, Guo, and Ding. Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems. NeurIPS, 2021.

Dear Reviewers,

Thank you again for your reviews.

As the discussion period nears its end, could you please check whether the authors' responses address your main concerns? Also, would you consider updating your scores based on their responses? If not, what are your remaining concerns?

Your feedback would be appreciated.

Regards, AC

I am happy to keep my original score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.