Improved Frequency Estimation Algorithms with and without Predictions

Summary

This paper studied frequency estimation and learning-augmented frequency estimation. CountMin and CountSketch are the most popular algorithms for this task. With the addition of learning augmentation, an algorithm is given access to a learned prediction, in this case the prediction of the heavy hitters. This paper focuses on the stream being from a Zipfian distribution, which are well-studied, well-motivated distributions with heavy tails. In the learning-augmented algorithm, if an element is predicted to be heavy, it is given a unique bucket so that a more accurate frequency can be computed for it. If it isn’t predicted to be heavy, it is simply input into a sketching algorithm. They prove bounds on the weighted error of algorithms, including, CountSketch, CountMin, and a novel algorithm. For CountSketch and CountMin, the paper gives a tight analysis. The new algorithm is studied both with and without predictions, though predictions give the largest advantage in low space settings. Experiments justify the theory is predictive of performance.

Strengths

- Learning-augmented frequency estimation is itself a very nice question, I was looking forward to reading this paper in my pile. - The algorithm is clean, straight-forward. I believe the results are correct. - The paper is grammatically well-written.

Weaknesses

- I am confused about the prediction model. Normally, in learning-augmented algorithms, we measure an algorithm’s performance based on the error in the prediction. Here, as far as I could tell, all of the theoretical results only held when one assumed the predicted heavy hitters were correct. I expected to see some trade-off between the quality of prediction and the weighted error bounds. The experiments briefly mentioned that the prediction quality might be poor, thus leading to worse empirical performance (as expected), but there was no theory discussing the robustness of the predictions. Robustness in the prediction error is what differentiates learning-augmented algorithm from all these other BWCA frameworks (data-driven algorithms, algorithms with advice, etc). Perhaps because of the heavy tail distribution assumptions, it’s reasonable to assume that one learns the heavy hitters perfectly? Or can you offer another explanation for this choice in the model? - This paper does not clearly lay out its improvements on prior work. I would like to see a lot more comparison to the most relevant previous work [Hsu et al. 2019]. Can this be more clearly stated in the introduction? Concretely, it would help to have previously known results listed in a column in your table 1 for that we can see your improvement.

Questions

(see Weaknesses, please)

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

na

Summary

Summary of the Paper ================== * This work follows (Hsu Indyk Katabi Vakilian 2019) in trying to improve the performance of hashing-based frequency estimation algorithms (such as Count-Min, CountSketch) by making use of "advice" in the form of a learning model's predictions which classify the input elements as "heavy-hitters" or otherwise based on the input distribution. * Just as (HIKV2019), the theoretical analysis assumes a Zipfian (heavy-tail) property for the data distribution, and they provide guarantees for the expected weighted estimation error $\frac{1}{N} \sum_{i=1}^{n} f_i \cdot |f_i - \hat{f}_i|$. * They improve on the (HIKV2019) analysis of Count-Min and Learned-Count-Min algorithms to get tight bounds on the expected estimation error when there are multiple hash functions ($k \geq 2$). * They also provide tight bounds for the expected estimation error of CountSketch, with and without learning. * Finally, they propose a better frequency estimation algorithm --- both plain (Algorithm 1&2) and learning-augmented (Algorithm 3&4) --- and prove bounds on the expected estimation error in both cases, showing that the learning-augmented algorithm outperforms both Plain-CS and Learned-CS in all regimes, whereas the plain (no-learning) algorithm outperforms the Plain-CS algorithm in the low-space regime ($B = {\rm polylog}(n)$). * They also propose a parsimonious variant of the algorithm (limited number of queries) and do an experimental evaluation.

Strengths

* The problem setting is already studied in the literature and thus the improvements shown in this work are clearer. The Zipfian (heavy-tail) property for the data distribution is known to hold for many real world datasets (if approximately). * This work provides tight bounds for the expected estimation error of CountSketch and CountMin, both with and without learning. In the case of CountMin, it improves upon the existing bounds from (HIKV2019). * The proposed "better frequency estimation algorithm" provides tangible improvements over CS and CM, both wiith and without learning-augmentation. * They also consider a variation of the algorithm with worst-case guarantees, even when the data distribution is not Zipfian, and the variant nicely generalises from the Zipfian case. * The work includes the implementation of the algorithms and experimental evaluation. * A reasonable level of proof-sketches are provided in the main paper.

Weaknesses

* The experiments should ideally have also considered the worst-case variant of the algorithm (Algorithm 6 in the supplementary) in both the Zipfian and non-Zipfian cases.

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

Not applicable.

Summary

Authors study frequency estimation algorithms CountMin and CountSketch and propose their modifications tailored for heavy tailed distributions. They first analyze CountMin and CountSketch, showing that the second one achieves better theoretical bounds on such distributions which explains experimental results in previous work. They propose a different algorithm with significantly better performance bounds on heavy tailed distributions which also satisfies worst case guarantees (for the case when the input does come from a considered heavy-tailed distribution) which are comparable to CountSketch. They also propose an ML-augmented variant of their algorithm which assumes that there is an oracle which correctly identifies half of the heavy hitters. This algorithm also works in parsimonious setting where it is allowed to receive only a few predictions.

Strengths

* They consider problem important both in theory and practice in a setting which occurs often in practice * They show limitations of the existing algorithms and design new ones overcoming these limitations * the ML-augmented version of their algorithm can work in a parsimonious regime: only very few predictions are needed and I believe that this is a good sign of usability in practice

Weaknesses

* I did not see lower bounds for the problem in their setting. It is not clear whether better algorithms are possible * It is not clear how their algorithm's performance depend on precision of the predictor, e.g., what if it identifies too many or too few items as heavy hitters

Questions

* if your algorithm reports too many items as heavy hitters, what does your algorithm do? * requirement that the predictor perfectly identifies the top B/2 heavy hitters seems rather strict. Can it be made weaker, e.g. that it identifies 90% of the top B heavy hitters, or that it correctly identifies $i$th heavy hitters with some probability depending on $i$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

assumptions clearly stated in the theoretical results

Summary

The authors present a new error analysis for Count-Sketch (CS) and Count-Min Sketch (CMS) for heavy-tailed distributions. They propose a novel Count-Sketch-based algorithm and its learned variant to estimate the frequencies of items in a data stream. Empirically, they show that both algorithms outperform the standard CS and LCMS of Hsu et al. (ICLR 2019) in terms of weighted and unweighted estimation errors on various datasets. In addition, they introduce a parsimonious version of their learning-based algorithm which performs a limited number of queries to the oracle.

Strengths

The paper is concerned with the fundamental problem of estimating the frequencies of items in a data stream. It introduces tight error guarantees for Count-Min sketch and Count-Sketch algorithms as well as their learned variants for Zipfian distributions. The authors propose a novel Count-Sketch-based algorithm and its learning-augmented variant that significantly outperform the baseline algorithms on two real-world datasets and a synthetic Zipfian dataset.

Weaknesses

The results section of the paper mentions that the prediction quality for the CAIDA dataset was relatively poor, however, the work of Hsu et al. (ICLR 2019) states that the AUC score of identifying the top 1% heavy hitters for CAIDA was 0.1 higher than for the AOL dataset. Hence, it seems that the experimental results are not quite consistent with those of Hsu et al. as their LCMS offered more significant advantages than the basic CMS on the CAIDA dataset as compared to AOL. Furthermore, the experimental section does not include results for the parsimonious algorithm and less heavy-tailed distributions.

Questions

The learned models for the CAIDA and AOL datasets are very complex and rather expensive to train, and the space allocation of the learned variant in the given plots does not seem to include the space reserved for the oracle. Therefore, it is unclear whether the novel learning-based algorithm offers any advantages over using its non-learned counterpart. It would be great to have a comparison of these two algorithms with equal space allocations which includes the space for the learned model. In addition, it would be helpful if the accuracies of identifying top B/2 frequent items of the learned oracles for the AOL and CAIDA datasets were given in the paper as well as a comparison of the B/2 value to the thresholds used in LCMS of Hsu et al. (ICLR 2019) to investigate why the learning-based variant of the novel CS algorithm does not offer similar advantages for the CAIDA dataset as LCMS.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

It would be helpful if the limitation of the parsimonious algorithm due to having to estimate the length of the data stream was stated more clearly in the paper as well as that of Algorithm 2 for non-heavy-tailed distributions due to having to estimate the tail of the frequency vector.

Summary

The authors study frequency estimation in a streaming setting using CountMin and CountSketches, both their classic and learning augmented variants. They prove tight theoretical bounds for the expected error when the frequencies follow the Zipf distribution. They also introduce and analyze a new algorithm with lower error that returns 0 for low frequencies instead of the noisy estimates of classic CountSketch. Furthermore they also introduce a parsimonious version of their algorithm that avoids consulting the potentially much slower machine learned model for each item of the stream using Poisson sampling to provably invoke it a small number of times only. Several experiments with two real world and synthetic data sets support the claims, albeit the implemented algorithm is much simpler than the one analyzed and a simple modification of the classic CountSketch also yields substantial improvements.

Strengths

1) Problem and techniques studied are extremely well motivated and widely used. 2) Solid theoretical analysis and tight new lower and upper bounds. 3) Introduces multiple new algorithm variants. 4) Substantial error reduction in the experiments. 5) Paper is well written and structured.

Weaknesses

1) No experiments with the theoretically analyzed algorithm, no theory for the simpler variant in the experiments. 2) I would love to see some experiments with the parsimonious algorithm as well. 3) When its truncation threshold is properly tuned the experimentally evaluated simplified algorithm is more accurate than returning max {0, CountSketch's estimate}. However the best threshold is dataset dependent and the wrong threshold underperforms the non-negative CountSketch (i.e. threshold = 0). Section 3.2 proposes a theoretical construction based on the Alon-Matias-Szegedy sketch to adaptively tune and set the threshold, nevertheless this variant is not evaluated in the experiments either. It would be good to evaluate a hyper-parameter free variant that works (well) on any data out of the box or explicitly leave it as future work.

Questions

Alg 1: What's median of 4? The proof section carefully requires odd number of rows. Could you please clarify, or since it's only for the sake of theory make it 3 (or 5) to keep it simple? Alg 2: Could you discuss why it's essential (or not) to take median of medians instead of using a single CountSketch with O(T) rows as a filter? Could you also discuss whether your results hold (strengthen or weaken) for more general power laws where f_i ~ (1/i)^p (or log-normal) beyond f_i ~ 1/i Zipf similarly to Du, Elbert, Franklyn Wang, and Michael Mitzenmacher. "Putting the “Learning." ICML, 2021? Probably it's best worked out and discussed after lines 222-223. Could you also measure and disclose the power law exponent for the CAIDA and AOL datasets? Figures 2-5: Could you use the same color for best Our (C=..) line in the left and right sub-plots? Lines 249-250: three columns and varying number of rows -> 3 rows and varying number of columns (typo).

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes, it's absolutely forthcoming and adequate.