acceptodds
Under review as a conference paper at ICLR 2027

Fast Streaming Algorithms for High-Dimensional Optimization

Abstract

A fundamental problem in machine learning is to design algorithms that extract essential structure in large, dynamically growing datasets with provable statistical guarantees. The streaming model captures this challenge by requiring algorithms to process data sequentially and irreversibly using memory sublinear in the input size. While prior work has achieved near-optimal space bounds for fundamental problems such as clustering and dimensionality reduction, these guarantees often rely on costly per-update computation, limiting their relevance for large datasets. We study whether both fast update time and optimal space can be achieved simultaneously for high-dimensional geometric problems in insertion-only streams. We present a general streaming framework that combines coarse and refined sampling schemes to accelerate the update time. Applying this framework, we obtain new streaming algorithms for Euclidean -clustering, subspace embeddings, and projection-cost preservation with near-linear update time and space independent of the stream length. In particular, we achieve an exponential improvement in in the update time for -clustering compared to previous state-of-the-art streaming algorithms. For subspace embedding and projection-cost preservation, we show that the total update time achieves input-sparsity time, demonstrating that there does not necessarily exist a separation between the runtime of streaming and offline algorithms. Moreover, we do not lose additional factors in space complexity compared to previous algorithms that give the best space.

Primary area:
optimization
Keywords:
streaming algorithms, clustering, numerical linear algebra

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_xoTiOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper speed up coreset construction for Euclidean (k,z)(k,z) clustering, subspace embedding and projection-cost preservation in insertion-only streams. The main idea is to down-sample the stream to O(nα)O(n^\alpha) elements using a coarse sampling scheme and then apply optimal sampling scheme. This allows to improve the update time (amortized analysis) while preserving the optimal space of the known methods.

The main improvement is to speed up the update time for the Euclidean (k,z)(k,z)-clustering problem improving the dependence on kk from poly(k) to poly(logk) and the dependence on nΔn\Delta from polylog(n\Delta) to polyloglog(n\Delta) - an exponential improvement. This further shows a separation between metric (k,z)(k,z) clustering which require Ω(k)\Omega(k) time per update and Euclidean (k,z)(k,z)-clustering.

Using similar framework, but independent analysis, they improve the update time for subspace embedding and projection-cost preservation, where in the streaming model the input matrix arrive sequentially row-by-row.

Critical strengths
  1. The paper improves state-of-the-art algorithms for classical problems in the insertion-only streaming model: (k,z)(k,z)-clustering and coreset construction, subspace embedding and projection-cost preserving sketches.
  2. While the technical idea seems simple (crude sampling first and then refined sampling), the analysis is intricate and the combination of techniques is non-trivial.
Critical weaknesses
  1. The technical parts in the appendix are not easy to follow, and I think a more extensive technical overview is needed in the final version.
  2. The results should be placed in better context with previous work, for example what is the update time by taking state-of-the-art coreset construction for the offline settings and apply it with merge-and-reduce framework of HM04? This is omitted from the introduction (appear only in the technical sections). I think a more comprehensive table(s) that compare previous results with the current improvements is necessary and more generally, the authors should consider including a related work section which covers each one of the problems.
Questions for authors
  1. Do you think that the technical overview and related work can be improved during the rebuttal period?
  2. what is At+A_t^+ in Theorem 1.3, this is undefined.
  3. can you specify the regime (n,d,k) for which the od,k(1)o_{d,k}(1) term is neglected?
Reviewer_3qEcOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a streaming framework in which inexpensive crude sampling filters incoming data before a more expensive, space-efficient refinement stage. It applies this framework to Euclidean clustering, �0��0� subspace embeddings for �1��1�, and projection-cost preservation, claiming improved processing time while retaining strong space guarantees. Experiments on MNIST clustering and Wave Energy subspace embedding report faster construction with comparable approximation quality against the selected baselines.

Critical strengths

In my opinion here are some strengths of the paper,

  • Combining rapid stream processing with compact summaries addresses a meaningful limitation of existing coreset methods; achieving the claimed guarantees would be a substantial contribution.
  • Filtering before expensive refinement offers a reusable approach across clustering, subspace embeddings and projection-cost preservation, with a clear explanation of the intended amortization.
  • The experiments demonstrate encouraging speed–quality trade-offs on two applications, including a worst-direction distortion metric for �0��0� embeddings.
Critical weaknesses

However, in my opinion, the paper has some flaws which I'll outline below,

  • The matrix-sampling guarantees are incorrect as written. More concretely, for �0��0�, it seems that Algorithm 3 typically estimates the last row’s Lewis weight within a factor �1��1�, contradicting its claimed �2��2� approximation with �3��3�. Further, Algorithms 9 & 11 also scale vectors by inverse probability, whereas literal row scaling requires �4��4� for �5��5� embeddings and �6��6� for PCP, unless separate objective weights were intended...
  • The clustering exchange rule can fail; this is due to the fact that Algorithms 1/5 compare �7��7� against the current score but update that score using the distance to the nearest remaining center, so they can skip much cheaper replacements. This mismatch admits unbounded approximation ratios on valid inputs, undermining the constrained-clustering guarantee used by the sensitivity estimator.
  • Theorems 3.2/4.2/5.2 critically omit parameter-dependent lower-order costs retained in the introduction, while the constant-height quadtree argument assumes �8��8�. However, explicit matrix-refresh costs and dependencies on �9��9� are needed for the reader to establish the claimed speedups beyond sufficiently long streams with fixed auxiliary parameter.
Questions for authors

My questions to the authors are as follows,

  • Can you provide a corrected Lewis-weight estimator and row-weighting convention, then re-establish correctness and sublinear coarse-stream size for every fixed �0��0�? Please also resolve the sensitivity inequalities in Lemmas F.9 and F.10.
  • Can you correct the comparison in Algorithms 1/5 and verify the resulting exchange and sensitivity bounds? Additionally, how does Lemma D.9 update cluster masses in constant time when changing centers can reassign points to retained centers?
  • What are the explicit total-runtime bounds, including sketch refreshes, preprocessing and accuracy dependence? Please state the necessary restrictions on �1��1� and reconcile the introductory bounds with their later restatements.
3 comments

Thank you again for the review. We would appreciate any further comments on our response and revised manuscript. We would also be happy to elaborate on any remaining concerns.

Reviewer_3qEcOpenReview ↗

read your rebuttal

Thanks for your clarifications. Taking into account the entire discussion including your comments, I am raising my score to 3.

Thank you for considering our clarifications and reconsidering your evaluation. We appreciate your constructive feedback.

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

This paper studies how to reduce both processing time and storage costs in insertion-only data streams. The authors propose a framework combining crude and refined sampling: the input is first filtered quickly, and the resulting shorter stream is then processed more carefully. The framework is applied to Euclidean (k,z)-clustering, Lp subspace embeddings, and projection-cost preservation. Experiments on clustering and L2 subspace embeddings demonstrate computational benefits.

Critical strengths

1.The paper addresses both update time and space usage, which are relevant to practical streaming applications. Crude sampling reduces the amount of data entering subsequent expensive processing steps. The overall approach is clear, and the source of the speedup is easy to understand.

2.The framework applies to several problems. The paper discusses clustering, subspace embeddings, and projection-cost preservation, suggesting that the approach has some generality.

3.The experiments compare both speed and approximation quality. In the MNIST experiments in Section 6, the method achieves approximately twofold and fourfold speedups over CWZ at coreset sizes of 256 and 512, respectively, while maintaining similar clustering costs.

Critical weaknesses

1.The update condition in Algorithm 1 on page 6 is inconsistent with the candidate cost. The quantity compared in line 3 differs from the value used in the update in line 4.

2.The connection between the approximation guarantee in Theorem 1.2 on page 3 and the cited result is not sufficiently clear. This paper defines the clustering cost as the sum of distances raised to the z-th power, whereas the O(z)-approximation of Gupta and Tangwongsan (2008) applies to the z-th root of that sum. The approximation ratios for these objectives differ, and the current explanation does not directly support the claimed (O)z-approximation for general z.

3.Several presentation details are inconsistent, including the description of memory usage on page 3, the meaning of X in Algorithm 2, and the time expressions in Framework B.3.

Questions for authors

1.Page 3, line 128, claims that memory usage is sublinear in k, but the space bound in Theorem 1.1 is O(dk/min{ε^4,ε^(2+z)}), which contains a linear factor in k. Could the authors check and reconcile these statements?

2.The update rule in Algorithm 1 on page 6 require clarification. The quantity compared in line 3 differs from the value assigned in line 4, potentially causing a smaller candidate value to be skipped. Could the authors explain whether the current rule is correct?

3.Theorem 1.2 on page 3 claims an O(z)-approximation. However, this paper defines the clustering cost as the sum of distances raised to the z-th power, while the cited O(z)-approximation of Gupta and Tangwongsan (2008) applies to the z-th root of that cost. Could the authors explain how the cited guarantee translates to the objective used in this paper?

4.Algorithm 2 on page 7 takes Z and a batch B as inputs, but lines 5–6 use X without specifying which data it represents. Could the authors clarify the meaning of X and the data used in these steps?

5.Framework B.3 on pages 15–16 defines the crude sampling time as T_1, but the proof uses T_2. The theorem also states the amortized refined sampling time as T_2/n^α, whereas the proof concludes with T_2/n^(1−α). Could the authors check and reconcile the notation and formulas?

1 comment

Thank you again for reviewing our paper. We would appreciate any further comments on our response and revised manuscript when you have a chance. We would also be happy to clarify any remaining concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.