acceptodds
Under review as a conference paper at ICLR 2027

Sketching Faster than Dimension Times Update Time

Abstract

In many applications of sketching, such as distributed computation, the input is available as a fixed vector or matrix rather than as a stream of updates. Let denote the ambient input dimension. In this offline setting, applying a streaming sketch by simulating coordinate updates can introduce unnecessary overhead: larsen2015time prove update-time lower bounds for several natural turnstile streaming problems. In addition, achieving high success probability, say , is often done by repetitions that introduce logarithmic overheads. We ask whether, given full access to a vector or matrix, one can apply an optimal-size linear sketch in truly linear time while retaining this high-success-probability regime. We show that this is possible for a range of basic sketching problems by composing standard sketching primitives in new ways. For estimation and heavy hitters, we give sketches with optimal sketching dimension, success probability at least , and truly linear application time. We further combine this construction with ExpanderSketch to obtain fast decoding, and extend the same ideas to rank-one tensor sketches and sampling. We also obtain fast sketches for general estimation. For , we use our heavy-hitters primitive to obtain a linear-time moment sketch with near-optimal dependence on dimension. Finally, we apply the same composition-and-selection template to linear regression and low-rank approximation. In the natural tall and wide regimes, respectively, these sketches have optimal or near-optimal sketch size and can be applied in input-sparsity time. Since all of our sketches are linear, the results apply directly in the coordinator model for distributed computation.

Primary area:
optimization
Keywords:
sublinear algorithms, linear sketches

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_waqeOpenReview ↗
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
  1. See W1-W3
  2. The reported 18% and 20% speedups exclude vector construction and SRHT row sampling. Do they still hold when those costs are included?
3 comments

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.

W1/W2/Q1. The comparison should include competing offline methods.

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 AiA_i in memory and send linear sketches satisfying S(∑Ai)=∑S(Ai)S(\sum A_i)=\sum S(A_i). 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\min_\beta\\|SA\beta-Sb\\|_2^2 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.

W3/Q1. The synthetic input favors the method, and there is no real-data evaluation.

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 11\\% of the optimum. These results show that the useful accuracy-time trade-off is also observed on unmodified production data.

Q2. Do the speedups persist when vector construction and SRHT row selection are included?

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=107D=10^{7} synthetic input and kernel. At m=1536m=1536 and 20482048, 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.

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.

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

This paper studies the computational efficiency of applying linear sketches in offline settings, where the full input vector or matrix is available rather than arriving through coordinate-wise streaming updates. The authors propose a composition-based framework combining existing sketching primitives, including CountSketch, Johnson–Lindenstrauss transforms, and ExpanderSketch, to achieve optimal or near-optimal sketch size, high success probability, and truly linear sketch application time in specified parameter regimes. The results cover ℓ2\ell_{2} norm estimation, heavy hitters, ℓ2\ell_{2} sampling, tensor sketching, FpF_{p} moment estimation, linear regression, and low-rank approximation. A proof-of-concept experiment on synthetic vectors demonstrates moderate application-time improvements and reduced sketch dimensions compared with selected baselines.

Critical strengths
  1. The paper establishes a useful combination of optimal sketch dimension, high success probability, and truly linear application time for fundamental sketching problems in specified parameter regimes. In particular, the ℓ2\ell_{2} estimation and heavy-hitters results demonstrate how staged dimensionality reduction and probability amplification can avoid the additional computational overhead of simulating streaming updates. Achieving these guarantees simultaneously is a meaningful algorithmic contribution.

  2. The authors extend the core construction to several important sketching and numerical linear algebra problems, including fast heavy-hitter recovery, FpF_{p} moment estimation, tensor sketching, regression, and low-rank approximation. These extensions demonstrate that the approach is not restricted to norm estimation. The preservation of linearity also makes the constructions compatible with distributed aggregation, providing potentially useful building blocks for communication-efficient computation.

Critical weaknesses
  1. The principal approach relies on composing existing sketching primitives, including CountSketch, JL transforms, and ExpanderSketch, rather than developing fundamentally new sketching techniques. Although the resulting complexity guarantees are valuable, the conceptual novelty appears relatively incremental. Furthermore, despite motivating the work through distributed and federated learning, the paper primarily addresses classical sketching problems without developing or evaluating a corresponding distributed learning algorithm. Consequently, the broader contribution to machine learning, beyond improvements to general-purpose sketching primitives, remains insufficiently demonstrated.

  2. The experimental evaluation is restricted to a single synthetic ℓ2\ell_{2} norm estimation setting with fixed input dimension and accuracy, despite the paper presenting computational improvements across several distinct sketching problems. The reported application-time improvements over direct SRHT are approximately 18–20%, and the experiments do not systematically investigate scaling with input dimension, accuracy, or failure probability. Moreover, the implemented CountSketch–SRHT variant differs from the specific multi-stage CountSketch construction analyzed in the main proof. Without broader benchmarks, particularly for decoding, regression, and low-rank approximation, the practical significance of the theoretical speedups remains unclear.

Questions for authors
  1. Since the main constructions combine established primitives such as CountSketch, JL transforms, and ExpanderSketch, could the authors clarify which aspects of the proposed composition framework are fundamentally new relative to existing sketch-composition and offline/batched sketching approaches? In particular, which of the claimed complexity improvements cannot be obtained through relatively straightforward combinations of existing techniques?

  2. The paper motivates its results through distributed and federated learning, but the proposed algorithms primarily address standalone sketching tasks. Could the authors clarify which concrete ML workloads would benefit most from the improved sketch application complexity, beyond the general linearity property enabling distributed aggregation? Is there evidence that these improvements translate into meaningful computational or communication benefits in practical distributed learning settings?

  3. Could the authors provide a more systematic comparison of sketch application time, sketch size, and decoding time across varying input dimensions, accuracy requirements, and target failure probabilities? In particular, benchmarks for heavy-hitter recovery, FpF_{p} estimation, regression, or low-rank approximation would help establish whether the theoretical improvements translate into practical computational gains beyond the single ℓ2\ell_{2} estimation experiment.

  4. The central ℓ2\ell_{2} estimation theorem establishes linear application time and failure probability at most 1/d1/d under specific parameter conditions, while the experiments use a CountSketch–SRHT implementation and report substantially larger observed failure probabilities. Could the authors clarify how closely the implementation corresponds to the theoretically analyzed construction, and whether the claimed runtime advantages persist in configurations targeting the theorem's high-success-probability regime? Clarifying the influence of intermediate sketch dimensions and parameter restrictions would strengthen the practical interpretation of the results.

3 comments

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.

W1/Q1. What is new beyond existing sketch composition and offline/batched approaches?

Our contribution is to achieve high success probability without a logarithmic amplification overhead in the time needed to apply an optimal-size ℓ2\ell_2 sketch. Composing a constant-success dimension reduction with a high-probability JL transform does not by itself amplify the success probability of the first stage. Our key observation is that the first reduction can simultaneously produce an intermediate vector that is polynomially smaller than dd and achieve inverse-polynomial failure probability. Consequently, a constant number of copies suffices for amplification, while subsequent transforms operate on polynomially smaller vectors. Together, these properties yield optimal sketch size, failure probability at most 1/d1/d, and truly linear O(d)O(d) application time in the stated parameter regime.

Clarkson-Woodruff already combine sparse embeddings with fast JL transforms [9]; their corresponding high-probability input-processing bound depends on log⁡(1/δ)\log(1/\delta). Alman and Yu [10] use batches of updates to speed up maintenance as updates arrive. In our setting, the worker has the whole vector and only needs its final sketch, so later stages see a completed intermediate vector. The other applications require additional ideas: reshaping and rectangular matrix multiplication for 1<p<21 < p < 2. For heavy hitters, ExpanderSketch on a hashed vector returns heavy buckets. To recover the original coordinates without scanning all dd of them, we use linear hashes across a constant number of copies and recover common preimages by solving small linear systems.

W1/Q2. Which concrete ML workloads benefit, beyond linear aggregation?

Our contribution to distributed learning is to improve the sketching primitives used within learning algorithms. Developing a new learning algorithm is a separate contribution. For gradient compression, Sketched SGD estimates ∣g∣2\\|g\\|_2 and identifies coordinates with ∣gj∣≥ε∣g∣2|g_j|\ge\varepsilon\\|g\\|_2, where g=∑igig=\sum_i g_i, before requesting their exact values [11]. Our norm-estimation and heavy-hitter sketches provide these primitives with high success probability and truly linear application time. FetchSGD also maintains momentum and accumulated error in sketch space [12]; our sketches support these operations.

For distributed PCA in the sum model [13], the goal is a rank-kk projection Π\Pi satisfying ∣A−ΠA∣F2≤(1+ε)∣A−Ak∣F2\\|A-\Pi A\\|_F^2\le(1+\varepsilon)\\|A-A_k\\|_F^2. This is our low-rank approximation problem: workers form AiRjA_iR_j and AiQA_iQ, and the coordinator recovers candidate projections from ARjAR_j and selects one using AQAQ. These connections identify concrete learning procedures in which our primitives can reduce sketch application cost. The General response provides measured computational benefits on real-data distributed sketching tasks.

W2/Q3. Broader benchmarks and dependence on sketch size, accuracy, and failure probability.

Our General response reports equal-byte accuracy, application time, and Total time including recovery for norm estimation, low-rank approximation, and regression on real production data. We additionally fix ε=5\varepsilon=5\\% for norm estimation and 22\\% for the matrix tasks, then vary the target failure probability δ\delta. Each entry below is the smallest tested budget for which 4,096 sketch trials give a 95% upper confidence bound on failure below δ\delta. Sketch row counts follow a power-of-two grid. An asterisk denotes original-data upload because no tested compressed budget establishes the required success probability.

\text{Norm estimation, }\varepsilon=5\\%\text{: MB/worker} \\\\ \begin{array}{cccccc} \hline \text{Method} & \delta=0.04 & 0.02 & 0.01 & 0.005 & 0.0025 \\\\ \hline \mathbf{Ours} & 0.0082 & 0.0082 & 0.0082 & 0.0164 & 0.0164 \\\\ \text{Direct SRHT} & 0.0082 & 0.0082 & 0.0082 & 0.0164 & 0.0164 \\\\ \text{OSNAP}\\ (s=2) & 0.0082 & 0.0082 & 0.0328 & 0.0655 & 0.1311 \\\\ \hline \end{array} \end{gathered}$$

W2/Q3 (continued). Required communication for matrix tasks.

\text{Low-rank approximation, }\varepsilon=2\\%\text{: MB/worker} \\\\ \begin{array}{cccccc} \hline \text{Method} & \delta=0.04 & 0.02 & 0.01 & 0.005 & 0.0025 \\\\ \hline \mathbf{Ours} & 5.90 & 5.90 & 5.90 & 11.80 & 11.80 \\\\ \text{Direct SRHT} & 5.90 & 5.90 & 5.90 & 5.90 & 5.90 \\\\ \text{OSNAP}\\ (s=2) & 11.80 & 23.59 & 47.19 & 94.37 & 133.67^{*} \\\\ \substack{\text{Randomized SVD}\\\\\text{(2 rounds)}} & 23.59 & 23.59 & 23.59 & 23.59 & 23.59 \\\\ \hline \end{array} \end{gathered}$$ $$\begin{gathered} \text{Regression, }\varepsilon=2\\%\text{: MB/worker} \\\\ \begin{array}{cccccc} \hline \text{Method} & \delta=0.04 & 0.02 & 0.01 & 0.005 & 0.0025 \\\\ \hline \mathbf{Ours} & 0.8520 & 0.8520 & 0.8520 & 0.8520 & 1.70^{*} \\\\ \text{Direct SRHT} & 0.4260 & 0.8520 & 0.8520 & 0.8520 & 0.8520 \\\\ \text{OSNAP}\\ (s=2) & 0.8520 & 1.70 & 1.70 & 3.41 & 7.80^{*} \\\\ \substack{\text{Randomized SVD}\\\\\text{(2 rounds)}} & 7.80^{*} & 7.80^{*} & 7.80^{*} & 7.80^{*} & 7.80^{*} \\\\ \hline \end{array} \end{gathered}$$ Ours matches SRHT's communication throughout the norm-estimation range and stays within twice its communication for low-rank approximation, while using less than OSNAP at stricter failure targets. In regression, ours matches SRHT and uses less than OSNAP at $\delta=0.02$, while stricter targets favor SRHT. A timing check at $\delta=0.02$ finds similar norm-estimation times for ours and SRHT, with ours faster for low-rank approximation and regression. These comparisons vary sketch size and failure target on fixed real-data problems. > **W2/Q4. Implementation, intermediate dimensions, and the high-success-probability regime.** The synthetic experiment is intended to examine the computational and accuracy trade-off at large input dimension, $d=10^7$. Evaluating failures on the $1/d$ scale would require on the order of $d$ independent trials. Even with zero observed failures, establishing a constant-confidence upper bound of $1/d$ would require that order of trials. We therefore evaluate larger failure probabilities to demonstrate the intended trade-off within a practical experimental runtime. The larger observed failure rates do not contradict the theorem's guarantee for its analyzed construction. The number of copies and the intermediate width can be tuned to the intended use. Our one-copy experiments report a practical operating point of the basic CountSketch-SRHT composition. The proof uses a constant number of independent composed norm estimates and takes their median to obtain the worst-case high-success-probability guarantee. The intermediate width is $r=65{,}536$ in the original synthetic experiment and $32{,}768$ in the new norm experiment. Increasing $r$ improves the first-stage failure probability bound at a fixed accuracy, but increases the cost of applying the subsequent SRHT. This can reduce the number of copies needed for amplification. Conversely, a smaller intermediate width makes each copy cheaper but can require more copies to reach the same failure target. Additional copies also require additional application work. Thus the intermediate width and copy count are coupled parameters controlling the accuracy-failure probability-time trade-off. For $\varepsilon\ge d^{-1/2+c}$ with fixed $c > 0$, the proof allows a constant copy count while keeping the intermediate width polynomially smaller than $d$. The subsequent transforms then take sublinear time, so the total application time remains $O(d)$. Tuning within the theorem's conditions therefore retains high success probability, optimal sketch size, and linear application time simultaneously. Empirical application times still depend on the selected widths and copy count, and the measured speedups concern the practical configurations reported in the experiments. **Additional references** [9] K. L. Clarkson and D. P. Woodruff. Low-rank approximation and regression in input sparsity time. STOC, 2013. [10] J. Alman and H. Yu. Faster update time for turnstile streaming algorithms. SODA, 2020. [11] N. Ivkin et al. Communication-efficient distributed SGD with sketching. NeurIPS, 2019. [12] D. Rothchild et al. FetchSGD: Communication-efficient federated learning with sketching. ICML, 2020. [13] R. Kannan, S. Vempala, and D. Woodruff. Principal component analysis and higher correlations for distributed data. COLT, 2014.

Thank you for the detailed rebuttal and additional experimental results, which have addressed many of my original concerns. My remaining concerns are as follows:

  1. The connection to distributed learning remains indirect, without validation in an actual distributed training algorithm.

  2. The practical computational advantages over direct SRHT remain modest and depend on the accuracy and failure-probability requirements.

  3. The experiments still do not evaluate the full high-probability construction or fast heavy-hitter recovery, and systematic runtime scaling with input dimension and accuracy remains missing.

Despite these remaining concerns, I believe the additional experiments and clarifications have substantially strengthened the paper. I will raise my overall rating to 3.

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

The paper studies how to compute sketches of vectors (or matrices) in an offline setting where full vector (or matrix) is available. It argues that traditional sketching approaches designed for streaming setting are sub-optimal in the offline case, and algorithms with better speed-accuracy tradeoffs can be constructed by composing the streaming primitives in potentially iterative manner. Its central idea is to compose existing sketching methods — especially CountSketch with a fast Johnson–Lindenstrauss transform — and use a staged reduction in dimension to achieve both small sketch size and high success probability. Specific applications of this core idea are developed for sketching tasks of ℓp\ell_p-norm estimation, heavy hitter identification, tensor sketches, regression and low-rank approximation, specifying theoretical guarantees for (probabilistic) quality of estimation as a function of sketch sizes. Empirical results are presented for ℓ2\ell_2-norm estimation in a synthetic scenario with a 10-million dimensional vector.

Critical strengths
  • A novel sketching approach that specifically focuses on the offline setting where full vector or matrix to be sketched is available. It utilizes primitives of more traditional streaming-based sketching and combines them in a staged iterative approach -- possible in the offline scenario -- to achieve sketches which outperform streaming-based approaches.
  • Formal guarantees for several important scenarios: ℓ2\ell_2-norm estimation and heavy hitters identification, general FpF_p-moment estimation, approximate ℓ2\ell_2 sampling, rank-one tensor sketching, least-squares regression, and low-rank matrix approximation.
  • Practical relevance to distributed computation by focusing on linear sketches. This makes its results particularly relevant to distributed and federated computation. Because linear sketches can be computed locally and aggregated by a coordinator, the proposed algorithms can reduce both communication costs and local computation time.
  • Clear presentation
Critical weaknesses
  • Limited experimental validation. While the theoretical exposition covers a large set of tasks, the main experimental evaluation focuses on ℓ2\ell_2-norm estimation in one specific synthetic scenario with a vector with 10710^7 entries. There is no evidence in the presented experiments that the improvements carry over to real datasets, varied data distributions, or the other applications discussed in the paper.
  • The paper’s results are not uniformly applicable to all accuracy requirements and problem dimensions -- theoretical results place accuracy constraint such as ε≥d−1/2+c\varepsilon \ge d^{-1/2+c} for a constant c>0c>0, restricting the range of accuracy for a given dimension.
Questions for authors

Please see the weaknesses above

1 comment

We thank the reviewer for the careful reading and positive assessment of our offline sketching approach, theoretical guarantees, and relevance to distributed computation. 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.

W1. Experiments are limited to one synthetic norm-estimation setting (d=107d=10^7).

Please refer to our additional experiments in the above comment. We evaluate distributed norm estimation, rank-4 approximation, and regression on a real-world production workload dataset, comparing accuracy and time at the same communication budget. Our composition reduces the reported tail errors of a single CountSketch and the tested sparse and low-rank-based alternatives, while applying faster than direct SRHT. These results show that the useful accuracy-time trade-off extends beyond the original synthetic norm-estimation setting to real data and recovered low-rank and regression solutions.

W2. Accuracy constraints restrict the parameter range for a given dimension.

Some of our results explicitly specify a parameter regime, but these conditions should be interpreted together with the option of using the original vector itself as the sketch. For example, Lemma 3.3 and Theorem 3.8 give sketches of dimension O(ε−2log⁡d)O(\varepsilon^{-2}\log d) for norm estimation and heavy-hitter recovery. When ε=O(d−1/2)\varepsilon=O(d^{-1/2}), this sketch-size bound already exceeds the original dimension. In this regime, we can simply use the identity map, which is an exact linear sketch with exactly dd coordinates and O(d)O(d) application time. Therefore, there is no benefit in constructing a larger approximate sketch. The parameter conditions should be understood in this context.

Comments on the paper

2 comments

General response

We thank all reviewers for their thoughtful feedback. Several reviewers asked for broader real-world benchmarks beyond norm estimation. We therefore evaluate distributed norm estimation, rank-4 approximation, and regression on a production workload, comparing accuracy and time at the same communication budget. Our composition reduces the reported tail errors of a single CountSketch and the tested sparse and low-rank-based alternatives, while applying faster than direct SRHT. These practical results complement our main contribution, the worst-case guarantee: high success probability, optimal sketch size, and truly linear application time simultaneously, in the stated parameter regimes. We did not add heavy-hitter experiments because our construction uses ExpanderSketch, whose implementation complexity and expected computational overhead are too high.

Data and Distributed Model.

All problems use the sum model with four workers: the coordinator wants statistics of v=∑iviv=\sum_i v_i or A=∑iAiA=\sum_i A_i. Workers use a shared linear map SS, so ∑iSvi=Sv\sum_i Sv_i=Sv and ∑iSAi=SA\sum_i SA_i=SA. We use the original invocation counts from the Azure Functions 2019 production trace, studied in Serverless in the Wild (ATC 2020).

For norm estimation, four workers hold consecutive six-hour windows of day 1. Worker ii holds the invocation total vi,fv_{i,f} for each function ff in its window, and the target is ∣∑i=14vi∣2\\|\sum_{i=1}^4v_i\\|_2. This vector has D=46,412D=46{,}412 functions. For low-rank approximation, let A∈R46,412×1,440A\in\mathbb R^{46{,}412\times1{,}440} be day 1's function-by-minute count matrix. Each worker holds one six-hour block of columns, represented as AiA_i with zeros elsewhere, so A=∑iAiA=\sum_i A_i. We find four orthonormal columns UU approximately minimizing ∣A−AUU⊤∣F2\\|A-AUU^\top\\|_F^2.

For regression, one row is a function-day pair (f,t)(f,t), t=1,2,3t=1,2,3. Let cf,t,hc_{f,t,h} count function ff's invocations in hour hh of day tt. Define

b_{(f,t)}=\sum_{h=1}^{24}c_{f,t+1,h}.$$ We fit one shared $\beta\in\mathbb R^{25}$ by minimizing $\\|A\beta-b\\|_2^2$. $[A\\ b]$ adds the response as a 26th column. Including every function observed by each forecast day gives 153,255 rows. Worker $i$ holds six predictor columns and the corresponding six-hour next-day counts $b_i$; worker 1 holds the intercept. We evaluate approximation to the original-data least-squares optimum. **Methods and Measurements.** - **Norm estimation:** CountSketch [1], direct SRHT [2], sparse JL ($s=4$) [3], and the median of three independent CountSketch estimates. - **Matrix tasks:** CountSketch, direct SRHT, OSNAP ($s=2$) [4], generalized Nystrom [5], uniform CUR [6], randomized SVD [7], and covariance Nystrom [8]. Our method is the one-copy CountSketch-SRHT implementation. Our method first applies CountSketch to an intermediate width $r$, followed by SRHT to the final output width $m$. We use $r=8m$ for norm estimation, $r=32m$ for low-rank approximation, and $r=4m$ for regression. Randomized SVD and covariance Nystrom use two communication rounds; the other protocols use one. We measure sketch quality by an error $\varepsilon$. For norm estimation, let $\widehat\nu$ estimate $\\|v\\|_2$, where $v=\sum_i v_i$; the error is $$\varepsilon=\frac{|\widehat\nu-\\|v\\|_2|}{\\|v\\|_2}.$$ For low-rank approximation, let $\widehat U$ be the recovered orthonormal rank-4 basis and $A_4$ the best rank-4 approximation to $A$. For regression, let $\widehat\beta$ be the recovered coefficient vector. Their errors measure the excess squared residual relative to the optimum: $$\varepsilon_{\mathrm{LR}} =\frac{\\|A-A\widehat U\widehat U^\top\\|_F^2}{\\|A-A_4\\|_F^2}-1, \qquad \varepsilon_{\mathrm{reg}} =\frac{\\|A\widehat\beta-b\\|_2^2}{\min_\beta\\|A\beta-b\\|_2^2}-1.$$ We report empirical error percentiles: $\varepsilon_{99}$ is the 99th percentile of $\varepsilon$, and $\varepsilon_{99.9}$ is its 99.9th percentile. Each norm setting uses 32,000 realizations and reports $\varepsilon_{99.9}$, and each matrix setting uses 4,096 and reports $\varepsilon_{99}$. The cheaper norm experiment permits more realizations and hence examination of a deeper tail. We also report the sketch apply time and the total time. Total time includes selecting the map, forming and combining worker outputs, and computing the final answer. Workers are simulated; network latency is excluded. Each norm worker sends a 4,096-dimensional FP64 vector (0.0328 MB). The low-rank budget is the size of a $1{,}024\times1{,}440$ FP64 matrix (11.80 MB/worker); the regression budget is the size of a $32{,}768\times26$ FP64 matrix (6.82 MB/worker). All methods receive the same budget within each task.

Results.

\text{Norm estimation, }m=4{,}096 \\\\ \begin{array}{cccc} \hline \text{Method} & \varepsilon_{99.9}\\ (\\%) & \text{Apply (ms)} & \text{Total (ms)} \\\\ \hline \mathbf{Ours} & 3.501 & 0.173 & 0.299 \\\\ \text{CountSketch} & 10.445 & 0.090 & 0.094 \\\\ \text{Direct SRHT} & 2.773 & 0.191 & 0.317 \\\\ \text{Sparse JL}\\ (s=4) & 9.221 & 0.202 & 0.205 \\\\ \text{CountSketch (median of 3)} & 3.761 & 0.319 & 0.323 \\\\ \hline \end{array} \end{gathered}$$ At the same communication budget, our composition reduces the 99.9th-percentile error to about one-third of that of a single CountSketch. It also achieves comparable tail accuracy to median-of-three CountSketch with shorter application and total times. This demonstrates the practical benefit of composition. It improves CountSketch's tail accuracy while avoiding the full application cost of direct SRHT. $$\begin{array}{ccccccc} \hline & & \substack{\text{Low-rank approximation}\\\\\text{rank }4,\\ m=1{,}024} & & & \substack{\text{Regression}\\\m=32{,}768} & \\\\ \text{Method} & \varepsilon_{99}\\ (\\%) & \text{Apply (ms)} & \text{Total (ms)} & \varepsilon_{99}\\ (\\%) & \text{Apply (ms)} & \text{Total (ms)} \\\\ \hline \mathbf{Ours} & 0.761 & 23.35 & 26.25 & 0.263 & 3.18 & 14.03 \\\\ \text{CountSketch} & 6.627 & 2.87 & 5.75 & 0.878 & 0.46 & 10.16 \\\\ \text{Direct SRHT} & 0.672 & 29.03 & 31.99 & 0.115 & 4.25 & 15.05 \\\\ \text{OSNAP}\\ (s=2) & 3.013 & 5.72 & 8.63 & 0.793 & 0.99 & 10.70 \\\\ \text{Generalized Nyström} & 3.570 & 51.91 & 137.56 & 308.979 & 747.69 & 15070.82 \\\\ \text{Uniform CUR} & 1214.425 & 0.61 & 2.42 & 209.016 & 0.42 & 2.79 \\\\ \substack{\text{Randomized SVD}\\\\\text{(2 rounds)}} & 8.838 & 8.33 & 14.47 & 56.226 & 0.82 & 4.88 \\\\ \substack{\text{Covariance Nyström}\\\\\text{(2 rounds)}} & 3.701 & 5.84 & 6.56 & 756.915 & 0.56 & 0.84 \\\\ \hline \end{array}$$ Both matrix tasks show substantially smaller $\varepsilon_{99}$ errors than CountSketch, OSNAP, and the specified offline baselines. At this percentile, our squared residuals are within $1\\%$ of the optimum in both tasks. Compared with direct SRHT, our application times are about 20-25% lower, and the advantage remains in Total times. SRHT achieves smaller errors, while CountSketch and OSNAP offer faster application at the cost of larger errors. These results show that the useful accuracy-time trade-off of composition extends beyond norm estimation to recovering low-rank approximations and regression solutions. **References** [1] M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. ICALP, 2002. [2] J. A. Tropp. Improved analysis of the subsampled randomized Hadamard transform. Advances in Adaptive Data Analysis, 2011. [3] D. M. Kane and J. Nelson. Sparser Johnson-Lindenstrauss transforms. JACM, 2014. [4] J. Nelson and H. L. Nguyen. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. FOCS, 2013. [5] Y. Nakatsukasa. Fast and stable randomized low-rank matrix approximation. arXiv:2009.11392, 2020. [6] M. W. Mahoney and P. Drineas. CUR matrix decompositions for improved data analysis. PNAS, 2009. [7] N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 2011. [8] A. Gittens and M. W. Mahoney. Revisiting the Nystrom method for improved large-scale machine learning. JMLR, 2016.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.