- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies linear sketching in an offline setting, where the full input is available at once and the cost to optimize is the time needed to compute a sketch. It constructs sketches that keep the optimal sketch size and a high success probability while remaining linear-time to cover a set of computations such as frequent moment estimation, heavy hitters, tensors, sampling, and regression / low-rank approximation. The evaluation is a single synthetic experiment comparing the proposed sketch against several sketching baselines.
Critical strengths
S1. Within the setting they define, the paper exploits the offline condition to obtain a good theoretical result. S2. It covers a set of important computations, and the result goes beyond a single problem. S3. The key idea and the presentation are clear.
Critical weaknesses
W1. The paper presents itself as a solution for offline sketching, but the comparison stays entirely inside the Count-Min/CountSketch lineage — the baselines are the stages of its own construction plus a repetition baseline, not competing methods. Offline alternatives are never compared or even discussed: CoSaMP, OMP, IHT and iterative reweighting for norm estimation, moment estimation and heavy hitters; sketch-and-solve, CUR/Nyström and randomized SVD for regression and low-rank approximation. In a paper claiming the offline setting allows faster sketching, a comparison that never leaves the CountSketch family cannot establish that claim.
W2. The paper does not compare against offline algorithms. The offline algorithms mentioned in W1 should be evaluated in the experiments.
W3 The experimental design only tests the favourable case. The synthetic input plants a few large coordinates made to dominate the vector norm. No real data is used either.
Questions for authors
- See W1-W3
- The reported 18% and 20% speedups exclude vector construction and SRHT row sampling. Do they still hold when those costs are included?
3 comments
Thanks for your rebuttal. The new experiment is not in the paper's setting in which the communication budget is not considered. Authors need a thorough experiment evaluation, which is beyond a minor revision or clarification. I will maintain my score.
Thank you for the follow-up. As the sketch size has been the primary resource studied throughout the paper, our goal is to reduce application time while achieving optimal sketch size and high success probability. We respectfully believe the additional experiments directly reflect this objective.
Our method, CountSketch, Direct SRHT, and OSNAP are compared in application time and accuracy at the same sketch size. In particular, these methods all use linear sketches. Applying the same sketching map locally and summing the results produces exactly the same sketch as applying that map to the aggregate input offline. The distributed formulation makes the motivation for this work more explicit in the experiments: each worker performs the same offline sketch application, and the formulation does not change how the sketch is applied or its accuracy. Moreover, each worker sends only a single sketch, so the communication budget simply expresses sketch size in bytes. These comparisons consequently evaluate the paper’s application-time–sketch-size–accuracy trade-off on real-world datasets.
Finally, we would like to emphasize that our contribution is primarily theoretical: we establish worst-case guarantees that simultaneously achieve high success probability, optimal sketch size, and truly linear application time in the stated parameter regimes. The additional experiments serve as a simple proof of concept, providing supporting evidence of practical relevance.
We thank the reviewer for the careful reading and constructive feedback. We have also conducted additional real-data experiments in response to the reviewers' feedback. Please see our General response for the settings and results. We will add these production-trace experiments and distributed baseline comparisons to the revised paper. We address the specific concerns below.
The additional experiments in our General response explicitly include generalized Nystrom [5], uniform CUR [6], randomized SVD [7], and covariance Nystrom [8] for regression and low-rank approximation. All methods receive the same communication budget within each task; randomized SVD and covariance Nystrom use two communication rounds, with feedback charged. Workers hold local partitions Ai in memory and send linear sketches satisfying S(∑Ai)=∑S(Ai). We compare the offline baselines under this communication model, counting any additional rounds and feedback. Thus the new comparison includes competing offline methods beyond the stages of our construction. Our composition has smaller reported tail errors than these specified offline baselines at the tested budgets.
For CountSketch, direct SRHT, OSNAP, and our composition, regression uses sketch-and-solve: the coordinator solves minβ∣SAβ−Sb∣22 and we evaluate the returned coefficient against the original-data optimum. CoSaMP [14], OMP [15], IHT [16], and sparsity-promoting iterative reweighting [17] are methods for reconstructing sparse or compressible signals. Our norm-estimation task makes no sparsity assumption on the real-world input vectors and asks only for their norm. Using sparse recovery for this task would require choosing a measurement map and recovery parameters, such as the sparsity level or stopping rule, and tuning them for norm-estimation error. We treated this as a separate experimental setup and therefore focused our comparison on sketches that estimate the norm directly.
As mentioned in our General response, we conducted additional experiments on real-world data to address this concern. We compare accuracy and time across the baselines at the same communication budget. Our composition improves the reported tail errors over a single CountSketch and the tested sparse and low-rank-based alternatives, while applying faster than direct SRHT. For both matrix tasks, its 99th-percentile squared residual is within 1 of the optimum. These results show that the useful accuracy-time trade-off is also observed on unmodified production data.
The original 18-20% speedups refer to applying a preselected sketch to an available input. This is a relevant cost when the map is reused, since SRHT row selection need not be repeated for every application. To address the reviewer's question, we also measure the additional costs rather than treating them as part of application time.
We reran the original D=107 synthetic input and kernel. At m=1536 and 2048, the application-only reductions are 16.0% and 19.6%; including row selection gives 16.1% and 19.7%. Row selection takes less than 0.1 ms, so including it barely changes the comparison. Including synthetic-vector construction as well gives reductions of 3.3% (114.4 vs 118.3 ms) and 4.2% (114.0 vs 119.0 ms). The smaller percentages mainly reflect the common vector-construction cost of about 94 ms, but this is purely RNG data generation for the synthetic benchmark.
Additional references
[14] D. Needell and J. A. Tropp. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. arXiv:0803.2392, 2008.
[15] J. A. Tropp and A. C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 2007.
[16] T. Blumensath and M. E. Davies. Iterative hard thresholding for compressed sensing. arXiv:0805.0510, 2008.
[17] I. Daubechies, R. DeVore, M. Fornasier, and C. S. Gunturk. Iteratively re-weighted least squares minimization for sparse recovery. arXiv:0807.0575, 2008.