Improved Frequency Estimation Algorithms with and without Predictions
Authors: Anders Aamand
Justin Y. Chen
Huy Nguyen
Sandeep Silwal
Ali Vakilian
Venue: NeurIPS 2023 spotlight (2023)
Keywords: learning-augmented algorithms
algorithms with predictions
data-driven algorithms
sublinear
streaming
frequency estimation
sketching
TL;DR: We give improved learning-augmented algorithms for frequency estimation.

Abstract: Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. Popular sketching approaches to this problem (e.g., CountMin and CountSketch) come with worst-case guarantees that probabilistically bound the error of the estimated frequencies for any possible input. The work of Hsu et al.~(2019) introduced the idea of using machine learning to tailor sketching algorithms to the specific data distribution they are being run on. In particular, their learning-augmented frequency estimation algorithm uses a learned heavy-hitter oracle which predicts which elements will appear many times in the stream. We give a novel algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al. *without* the use of any predictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance in all experiments compared to prior approaches.

Improved Frequency Estimation Algorithms with and without Predictions
Anders Aamand MIT aamandemit edu
Justin Y. Chen MIT justcmmit edu
Huy Lê Nguyēn
Northeastern University hu. wu..nggyennnnorrrhassterm.cme edu
Sandeep Silwal
Ali Vakilian TTIC vakilian@ttic.edi
MIT silwal teral@mit.ccm
Abstract
Estimating frequencies of elements appearing a data stream is key task in large- scale data analysis. Popular sketching approaches this problem (c.g.. CountMin and CountSketch) come with worst-case guarantees that probabilisticall bound the errоr of the estimated frequencies for any possible input. The work of Hsu et al. (2019) introduced the idea of using machine learning to tailor sketching algorithms the specific data distribution they are being on. In particular, their learning--uge augmented frequency estimation algorithm uses a learned heavy-hitter oracle which predicts which elements will appear many times in the stream. We give a novel algorithm, which in some parameter regimes, already theoretically outperforms the learning based algorithm of Hsu et al. withou the of any pre- dictions. Augmenting our algorithm with heavy-hitter predictions further reduces the error and improves upon the state of the art. Empirically, our algorithms achieve superior performance in all experiments compared to prior approaches.
Introduction
In frequency estimation, stream sequence of elements from [n]] := {1, .......7 n,), and the goal is to estimate fi. the frequency of the ith element, at the end of the stream using low-space. Frequency estimation is one of the central problems in data streaming with a wide range of applications from networking (gathering important monitoring statistics B1 62 466) to machine learning (NLP B3),
feature selection R semi supervised learning (58)). CountMin (CM) (0) and CountSketch (CS)
14] are arguably the most popular and versatile of the algorithms for frequency estimation, and are implemented in many popular packages such Spark 63 Twitter Algebird (TC) and Redis.
Standard approaches to frequency estimation are designed to perform well in the worst-case due to the multitudinous benefits of worst-case guarantees. However, algorithms designed to handle any possible input do not exploit special structure of the particular distribution of inputs they are used for. In practice, these patterns can be described by domain experts learned from historical data. Following the burgeoning trend of combining machine learning and classical algorithm design, [36] initiated the study of algorithms in a simple but effective manner via heavy-hitters oracle. During a training phase, they construct classifier (e.g. neural network) detect whether element is "heavy" (e.g., whether fa is among the most frequent items). After such a classifier is trained, they scan the input stream, and apply the classifier to each element i. If the element is predicted to be heavy, is allocated unique bucket, so that an exact value of f; is computed. Otherwise, the stream element is inputted into the standard sketching algorithms.
frequency estimation by extending the classical CM and CS
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

The advantage of their algorithm was analyzed under the assumption that the true frequencies follow heavy-tailed Zipfian distribution. This is a common and natural reoccurring pattern in real world data where there are few very frequent elements and many infrequent elements. Experimentally, [36 showed several real datasets where the Zipfian assumption (approximately) held and useful heavy-hitter oracles could be trained in practice. Our paper is motivated by the following natural questions and goals in light of prior works:
Can we design better frequency estimation algorithms (with and without predic- tions) for heavy-tailed distributions?
In particular, we consider the setting of 36 where the underlying data follow a heavy-tailes distri- bution and investigate whether sketching algorithms can be further tailored for such distributions. Before tackling this question, we must tightly characterize the benefits-and limitations-of these existing methods, which is another goal of our paper:
Give tight error guarantees for CountMin and CountSketch, as well as their crurning-augmentin variants, on Zipfian data.
Lastly, any algorithms we design must possess worst case bounds in the case that either the data does not match our Zipfian (or more generally, heavy-tailed) assumption or the learned predictions have high error, leading to the following 'best of both worlds' goal:
Design algorithms which exploit heavy tailed distributions and ML predictions but also maintain worst-case guarantees.
We addresses these challenges and goals and our contributions can be summarized follows:
We give tight upper and lower bounds for CM and CS, with and without predictions, for heavy tailed distributions. A surprising conclusion from our analysis that (for natural error metric) a constant number of rows is optimal for both CM and CS. In addition, our theoretical analysis shows that CS outperforms CM, both with and without predictions, validating the experimental results of (3)
We go beyond CM and CS based algorithms to give a better frequency estimation algorithm for heavy tailed distributions, with and without the use of predictions. We show that our algorithms can deliver to a logarithmic factor improvement in the error bound over CS and its learned variant. In addition, our algorithm has worst case guarantees.
Prior learned approaches require querying oracle for every element in the stream. In contrast, we obtain a parsimonious version of our algorithm which only requires a limited number of queries to the oracle. The number of queries use is approximately equal to the given space budget.
Lastly, we evaluate our algorithms on two real-world datasets with and without ML based predic- tions and show superior empirical performance compared to prior work in all cases.
1.1 Preliminaries
Notation and Estimation Error The stream updates an n dimensional frequency vector and every stream element is of the form (i, A) where [n] and A TR. denotes the update the coordinate. The final frequency vector is denoted as f E R.. Let N = Σig(n) fr denote the sum of all frequencies. To simplify notation, we assume that fi 2 fz 2 ... 2 fn- fr denotes the estimate of the frequency ft. Given estimates {.f hejn), the error of a particular frequency 1f: fil. We also consider the following notion of overall weighted error done in 36
Weighted Error:
1 N
Σ KE(M]
f
The weighted error can be interpreted as measuring the eлror with respect to query distribution which the same as the actual frequency distribution. As stated in (36], theoretical guarantees of frequency estimation algorithms are typically phrased in the traditional (s. -)-rrro formulations. However as argued there, the simple weighted objective | is more holistic measure and does not require tuning of two different parameters, and is thus more natural from an ML perspective.

---

Zipfian Stream We also work under the common assumption that the frequencies follow the Zipfian law, ie.. the ith largest frequency f; is equal to A/i for some parameter A. Note know A the end of the stream since the stream length is A H By rescaling, we may assume that A = without loss of generality. We will make this assumption throughout the paper.
CountMin (CM) For parameters k and B, which determine the total space used, CM uses independent and uniformly random hash functions h1...., hy : [n] + [B]. Letting be an array of size [k] x [B] we let Cle, bj = Σe my
[ = 6.ff. When querying E [xa] the algorithm returns
f = mi) Cle, he())] Note that we always have that f; 2 fi-
CountSketch (CS) In CS, again have the hash functions h; above as well as sign functions
$ [n] + (-1, The array C' of size [A] x [B] is now tracks Clé,, b] = E [he =
())(() When querying i E [n]] the algorithm returns the estimate ft median se(i) Cee))
Learning-Augnnn Augmented Sketches 33 Given a base sketching algorithm (either CM or CS) and space budget B, the corresponding Gaaming-uugmentn algorithm (learned CM learned CS) allocates a constant fraction of the space to the base sketching algorithm and the rest of the space store items identified heavy by learned predictor. These items predicted be heavy-hitters stored in a separate table which maintains their counts exactly, and their updates are not sent to the sketching algorithm.
1.2 Summary of Main Results and Paper Outline
Our analysis, both of CM and CS, our algorithm, and prior work, is summarized in Table
Algorithm
Weighted Error
Uses Predictions?
Reference
CountMin (CM)
log
No
Theorem B.
B
CountSketch (CS)
No
Theorem C.4
Learned CountMin
log(n/B)) BB
Yes
36
log
Learned CountSketch
logín/B)
Yes
Theorem D.1
B log
Our (Without predictions)
O log
log B B-poly (log lo)
No
Theorem 2.1
Our (Learned version)
Yes
Theorem 3.1
log
Table 1: Bounds are stated assuming that the total space is B words of memory. Weighted error
means that element queried with probability proportional to 1/1. Moreover, the table considers normalized frequencies, so that fi 1/i.
Summary of Theoretical Results We interpret Table [ B denotes the space bound, which is the total number of entries used in the CM CS tables. First that CS achieves lower weighted error compared to CM, proving the empirical advantage observed in [36] However, the learned version of CS only improves upon standard CS the regime = n 1-o(1) While this setting does
high-accuracy regime), for CS, learning gives no asymptotic advantage in the low space regime.
appear sometimes in practice 33 36 (referred
On the other hand, in the low space regime of B = poly (logn). our algorithm, without predictions, already archives close to logarithmic factor improvement over even learned CS. Furthermore, our learning- augmented algorithm achieves logarithmic factor improvement over classical CS across all space regimes, whereas the learned CS only achieves logarithmic factor improvement in the regime B n -==o(1), Furthermore, our learned version outperforms or matches learned CS in all space regimes.

---

Our learning-uugmentt augmented algorithm can also be made parsimonions in the sense that we only query the heavy-hitter oracle (B) times. This is desirable in large-scale streaming applications where evaluating even a small neural network on every single element would be prohibitive.
Remark 1.1. We remark that all bounds in this paper are proved by bounding the expected error when estimating the frequency of a single item, ElIf - fell, then using linearity of expectation. While specialized our bounds to query distribution which is proportional to the actual frequencies in ① our bounds can be easily generalized to any query distribution by simply weighing the expected ervors of different items according the given query distribution.
Summary of Empirical Results We compare our algorithm without prediction to CS and our algorithm with predictions to that of [36] on synthetic Zipfian data and on two real datasets corre- sponding network traffic and internet search queries. In all cases, our algorithms outperform the baselines and often by significant margin (up to 17x in one setting). The improvement is especially pronounced when the space budget small.
Outline of the Paper Our paper is divided into roughly two parts. One part covers novel and tight analysis of the classical algorithms CountMin (CM) and CountSketch (CS). The second part covers our novel algorithmic contributions which go beyond CM and CS. The main body of our paper focuses on our novel algorithmic components, i.e. the second part, and we defer our analysis of the performance of CountMin (CM) and CountSketch (CS), with and without predictions, to the appendix: in Section we give tight analysis of CM for Zipfian frequency distribution. In Section Cwe give the analogous bounds for CS. Lastly, Section gives tight bounds for CS with predictions. covers our better frequency estimation without predictions while Section 3 covers the leaming-auggennte augmented version of the algorithm, as well as its extentions.
Section 2
1.3 Related Works
Frequency Estimation While there exist other frequency estimation algorithms beyond CM and CS (such as [51
40
we study hashing based methods such as CM 20 and CS [4]
as they are widely employed in practice and have additional benefits, such as supporting insertions and deletions, and have applications beyond frequency estimation, such as in machine learning (feature selection
g compressed sending
1 2 and dimensionality reduction 61 etc.).
Beeriing-aummented algorithms The last few years have witnessed rapid growth in using machine learning methods to improve "classical" algorithmic problems. For example, they have been used to improve the performance of data structures 42 [52], online algorithms 4y [56 32]
5, 600
6
4
22
sz combinatorial optimization 4II / + 53
23 [6], similarity search and 57 Similar our work, sublinear constraints, such memory or sample
clustering 59
24
complexity, have also been studied under this framework
36
38
39 19
57
2 Improved Algorithm without Predictions
We first present our frequency estimation algorithm which does not use any predictions. Later, we build on top of it for our final learning-augmented frequency estimation algorithm.
The main guarantees of of the algorithm is the following:
log n updated over Zipfian stream. Theorem 2.1. Consider Algorithm 7 with space parameter
Let (f. denote the estimates computed by Algorithm log B pofy(lo log u)
The expected weighted error is
E
N fr Ai]] =
B Jogn
Algorithm and Proof intuition: B' = B/ log logn. At a high level, we show that for every i < B', we execute line 10 of Algorithm 2 and the error satisfies |1/i fi = 1/B' (recall in the Zipfian case, the ith largest frequency f. 1/i). On the other hand, for i 2 B', we show that (with sufficiently high probability) line 8 of Algorithm 2 will be executed, resulting in
|1/i ful |1/i 0 1/i.

---

Algorithm (Not augmented) Frequency update algorithm
1: Input: Stream of updates to an n. dimensional vector, space budget
2: procedure UPDATE
3: T f (log n)
4: for j to T T do
5:
S, + CountSketch table with 3 rows and B 67
columns
6: end for
7: ST < CountSketch table with 3 rows and B
columns
6
8: for stream element (i, A) do
9: Input (f, A) in each of the T' CountSketch tables Sj
end for
11: end procedure
Algorithm 2 (Not augmented) Frequency estimation algorithm
1: Input: Index E (n] for which we want to estimate f;
2: procedure QUERY
3: for j = to T 1 do
4:
f + estimate of the ith frequency given by table Sj
5: end for
6:
fo f (f.
7:
if f. O(log log n)) B then
8:
Return 0
9:
else
10:
Return ff, the estimate given by table Sr
11:
end if
12:
end procedure
It might be perplexing at first sight why we wish to set the estimate to be 0, but this idea has solid intuition: it turns out the additive error of standard CountSketch with B' columns is actually of the order 1/BB. Thus, it does not make sense to estimate elements whose true frequencies are much smaller than 1/B' using CountSketch. challenge that we do not know priori which elements these are. We circumvent this via the following reasoning: if CountSketch itself outputs = 1/B' B' as the estimate, then either one of the following must hold:
The element has frequency 1/i < 1/B', in which case we should set the estimate to 0 to obtain error 1/i, opposed error 1/B' 1/i 1/B'.
The true element has frequency 1/B' which case either using the output of the CountSketch table or setting the estimate to 0 both obtain error approximately O B'), so our choice is inconsequential.
In summary, the output of CountSketch itself suggests whether we should output an estimated frequency as We slightly modify the above approach with Oloog log n) repetitions to obtain sufficiently strong concentration, leading to a robust method to identify small frequencies. The proof formalizes the above plan and is given full detail in Section
By combining our algorithm with predictions, we obtain improved guarantees.
3 Improved Learning-Augmented Algorithm
Theorem 3.1. Consider Algorithm 3 with space parameter B 2 log updated over Zipfian stream. Suppose we have access to a heavy-hitter oracle which correctly identifies the top B/2 heavy-hittrs in the stream. Let [fe] denote the estimates computed by Algorithm 4
The expected weighted
N Eh So 1se fa]] =0
error
is
log
5

---

Algorithm 3
Frequency update algorithm
1: Input: Stream of updates to an n dimensional vector, space budget B, access to a heavy-hitter
oracle which correctly identifies the top B/2 heavy-hitters
2: procedure UPDATE
3: T f (log logn)
4: for j = 1 to -
5:
5 f- CountSketch table with rows and
12T columns
6: end for
7:
ST CountSketch table with rows and
12 columns
8:
for stream element (i, A) do i a top B/2 heavy-hitter then Maintain the frequency of exactly
9:
10:
else
12:
Input (i, A) in each of the T CountSketch tables Sj end
13:
14: end for
15:
end procedure
Algorithm 4 (Learning-augmenttl) Frequency estimation algorithm
Input: Index E (n]] for which we want estimate f:
2: procedure QUERY
3: if i a top B/2 heavy-hitter then
4:
Output the exact maintained frequency of
5: else
6: Return f. + output of Alg. ussing the CountSkech tables created in Alg
7: end
8:
end procedure
Algorithm and Proof Intuition: Our final algorithm follows similar high-level design pattern used in the learned CM algorithm of [36]: given an oracle prediction, we either store the frequency of heavy element directly, or input the element into our algorithm from the prior section which does use any predictions.
The workhorse of our analysis is the proof of Theorem 2.1 First note that obtain error for i < B/2, Thus, all error comes from indices 2 B/2. Recall the intuition for this case from Theorem 2.1 want output from CS. The same analysis as in the proof of Theorem 2. shows that we are able to detect small frequencies and appropriately output an estimate from either the 7 th CS table output 0.
estimates this results in lower error than the additive
3.1 Parsimonious Learning
In Theorem we assumed access to heavy-hitter oracle which we can use every single stream element to predict it is heavy. In practical streaming applications, this will likely be infeasible. Indeed, even if the oracle is small neural network, it is unlikely that can query it for every single element in a large-scale streaming application. We therefore consider the so called parsimonious setting with the goal of obtaining the same eтror bounds the expected error but with algorithm that makes limited queries to the heavy-hitter oracle. This setting has recently been explored for other problems in the lcarning-augenn augmented literature
37
26
Our algorithm works similarly to Algorithm 3 except that when an element (i, A) arrives, we only query the heavy-hitter oracle with some probability (proportional to A). We will choose p so that we in expectation only query ((B) elements, rather than querying the entire stream. To be precise, whenever an item arrives, we first check it already classified as one the top B/2 heavy-hitters in which case, update its exact count (from the point in time where was classified as heavy). Otherwise, we query the heavy-hitter oracle with probability p. case the item is queried and indeed one of the top B/2 heavy-hitters, start an exact count of that item. An arriving item which

---

is not used as query for the heavy-hitter oracle and was not earlier classified as a heavy-hitter is processed as in Algorithm
Querying for an element, we first check if it is classified as a heavy-hitter and if so, we use the estimate from the separate lookup table. If not, we estimate its frequency using Algorithm R With this algorithm, the count of a heavy-hitter will be underestimated since it may appear several times in the stream before is used as a query for the oracle and we start counting it exactly. However, with our choice of sampling probability, with high probability it will be sampled sufficiently early to not affect its final count too much. We present the pseudocode of the algorithm as well as the precise result and its proof in Appendix
3.2 Algorithm variant with worst case guarantees
In this section we discuss variant of our algorithm with worst case guarantees. To be more precise, we consider the case where the actual frequency distribution is not Zipfian. The algorithm we discuss actually a more general case of Algorithm 2 and in fact, it completely recovers the asymptotic error (as well as Theorem Tit if we use predictions).
guarantees of Theorem 1
Recall that Algorithm outputs 0 when the estimated frequency is below T/B for T O log n). This parameter has been tuned to the Zipfian case. As stated in Section 2 the main intuition for this parameter is that it is of the same order the additive error inherent in CountSketch, which discuss now. Denote by fr the frequency vector where we zero out the largest P coordinates. For every frequency, the expected additive error incurred by CountSketch table with B' columns is l22 B'). In the Zipfian case, this is equal to O [| O B which is exactly the threshold we se Thus, our robust variant simply replaces this tuned parameter O(T/B) with an estimate of (Illl/l////B where B' = B/T.. We given an algorithm which efficiently estimates this quantity in a stream. Note this quantity is only needed for the query phase.
Lemma 3.2. With probability at least exp (1 (B)), Algorithm 6 outputs an estimate V satisfying Ω [1 1B)) SVSO (I B'
The algorithm and analysis are given in Section Replacing the threshold in Line 7 of Algorithm with the output of Algorithm (more precisely the square root of the value) readily gives us the following worst case guarantees. Lemma 3.3 states that the expected error of the estimates outputted by Algorithm 2
2
using B, regardless of the true frequency distribution, no worse than that of a standard CountSketch table using slightly smaller OBB log log n) space.
Lemma 3.3. Suppose B 2 log n. Let (f./z= denote the estimates of Algorithum 2 using B/2 space and with Line 7 replaced by the square root of the estimate of Algorithm D also using B/2 space. Suppose the condition of Lemma holds. Let (!:); denote the estates computed by a CountSketch log logn columns for sufficiently small constant Then, El]f+ fell s ElI fil].
table with cB
Remark 3.1. The learned version of the algorithm automatically inherits any worst case guarantees from the unlearned (without predictions) version. This is because only set aside half the space to explicitly track the frequency of some elements, which has worst case guarantees, while the other half used for the unlearned version, also with worst case guarantees.
4 Experiments
We experimentally evaluate our algorithms with and without predictions on real and synthetic datasets and demonstrate that the improvements predicted by theory hold in practice. Comprehensive additional figures are given in Appendix]] J
Algorithm Implementations In the setting without predictions, we compare our algorithm to CountSketch (CS) (which was shown to have favorable empirical performance compared to CountMin (CM) 3d and better theoretical performance due to our work). the setting with predictions, we compare the algorithm of (36), using CS as the base sketch and dedicated half of the space for items
Recall B' = B/T in Algorithm
2
7

---

CAIDA Log-Log Frequencies
AOL Log-Log Frequencies
10
107
Frequercy
107
307
101
10
10a
16
20t
30a
10'
30
10a
101
10"
10"
20
Sorted Elements
Sorted Elementss
Figure I: Log-log plots of the sorted frequencies of the first day/minute of the CAIDA/AOL datasets. Both data distributions are heavy-tailed with few items accounting for much of the total stream.
CAIDA Day #20
1+11
Space: 750.0
4.5
(nonneg!
(nonneg) Ourz (C+5)
Ours (C+1.0)
(C=2.0)
Weighted Eiter
33.5
Ours (C=5.0)
weighted
3.0
2.5
2.0
1.5
500
1000
1500
2000
2500
3000
10
20
30
40
Space
Minute
Figure 2: Comparison of weighted error without predictions on the CAIDA dataset. The left plot compares the performance of various algorithms (including algorithm with different choices of C) for a fixed dataset and varying space. The right plot compares algorithms over time across separate streams for each minute of data for specific choice of space being 750.
which are predicted to be heavy by the learned oracle. For all implementations, use three rows in the CS table and vary the number of columns. We additionally augment each of these baselines with a version that truncates all negative estimated frequencies zero as none of our datasets include stream deletions. This simple change does not change the asymptotic (e, 8) classic sketching guarantees but does make big difference when measuring empirical weighted error.
We implement a simplified and practical version of our algorithm which uses a single CS table. If the median estimate of an element is below threshold of Cn/w for domain size n, sketch width (a third of the total space), and a tunable constant C, the estimate is instead set to 0. As all algorithms use single CS table as the basic building block with different estimation functions, for each trial we randomly sample hash functions for single CS table and only vary the estimation procedure used.
We evaluate algorithms according the weighted еттоr as in Equation U but also according to unweighted eиror which simply the sum over all elements of the absolute estimation error, given by Σ. lf+ fil. Space is measured by the size of the sketch table, and errors are averaged over 10 independent trials with standard deviations shown shaded in.
Datasets We compare our algorithm with prior work on three datasets. We use the same two real- world datasets and predictions from [ the CAIDA and AOL datasets. The CAIDA dataset [12] contains 50 minutes of internet traffic data. For each minute of data, the stream is formed of the IP addresses associated with packets going through Tierl ISP. A typical minute of data contains 30 million packets accounted for by million IPs. The AOL dataset [55] contains 80 days of internet search queries with typical day containing
10 total queries and Rs 10 unique queries. As shown Figure [] both datasets approximately follow a power law distribution. For both datasets, we the predictions from prior work 3d formed using recurrent neural networks. We also generate synthetic data following a Zipfian distribution with n 10" elements and where the ith element has frequency n/i.
Results Across the board, our algorithm outperforms the baselines. On the CAIDA and AOL datasets without predictions, our algorithm consistently outperforms the standard CS with up to 4x smaller error with space 300. This gap widens when we compare algorithm with predictions
8

---

1+12
CAIDA Day #20
1el1
Space: 750.0
1.4
Hau et al.
7
Hsu (nonneg)
Hau et (nonneg)
Ours (C=1.0)
Ours (C+5)
Ours (C-2 0)
Wenghtoe Error
WW
(C+5.0)
0.6
0.4
0.2
2000
2500
Space
Figure 3: Comparison of weighted error with predictions on the CAIDA dataset.
127
ADL Day
1n7
Space: 750,0
3.0
3.5
C5 (nonneg)
2.5
CS (nonneg) (Cm3)
(C=1.0)
2.5
Ours (C=2.0)
2.0
2.0
Ours (C=5.0)
Weighodd
1.5
1.0
1.0
0.0
500
1000
1500
2000
2500
3000
10
20
30
40
50
60
70
80
Space
Day
Figure 4: Comparison of weighted error without predictions on the AOL dataset.
to that of 36 with a gap of up to 17x with space 300. In all cases, the performance of CS and 36 is significantly improved by the simple trick of truncating negative estimates to zero. However, our algorithm still outperforms these "nonneg" baselines. The longitudinal plots which compare algorithms over time show that algorithm consistently outperforms the state-of- off-the-art art with and without predictions.
In the case of the CAIDA dataset, predictions do not generally improve the performance of any of the algorithms. This is consistent with the findings of (36 where the prediction quality for the CAIDA dataset was relatively poor. However, for the AOL which has a more accurate learned oracle, our algorithm in particular is significantly improved when augmented with predictions. Intuitively, the benefit of our algorithm comes from removing error due to noise for low frequency elements. Conversely, good predictions help to obtain very good estimates of high frequency elements. In combination, this yields very small total weighted error.
In Appendix D we display comprehensive experiments the performance of the algorithms across the CAIDA and AOL datasets with varying space and for both weighted and unweighted error as well as results for synthetic Zipfian data. all cases, our algorithm outperforms the baselines. On synthetic Zipfian, the gap between our algorithm and the non-negative CS for weighted error is relatively small compared to that for the real datasets. While we mainly focus on weighted error in this work, the benefits of our algorithm estimates below the noise floor to zero is especially impactful for this error measure. general, we see the trend, matching our theoretical results, that space increases, the gap between the different algorithms shrinks as the estimates the base CS become more accurate.
even more significant for unweighted error setting
Acknowledgements
Anders Aamand supported by DFF-International Postdoc Grant 0164-00022B from the Independent Research Fund Denmark and a Simons Investigator Award. Justin Chen is supported by an NSF Graduate Research Fellowship under Grant No. 174530. Huy Nguyen supported by NSF Grants
2311669 and 1750716.

---

le7
ADL Day #50
3.0
Space: 750.0
3.5
Hau et al.
Hsu (nonneg)
Hau et (nonneg)
2.5-
Ours (C=1.0)
Ours (C-1)
2.5
Ours (C-2 0)
2.0
(C=5.0)
Weightd
1.5
1.5
1.0-
1.0
0.0
0.0
2000
2500
70
80
Space
Day
Figure 5: Comparison of weighted error with predictions on the AOL dataset.
References
[1] Anders Aamand, Justin Y. Chen, and Piotr Indyk. (Optimal) Online Bipartite Matching with Degree Information, In Advances Neural Information Processing Systems, volume 35, 2022.
[2] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20-29, 1996.
[3] Amirali Aghazadeh and Ryan Spring and Daniel LeJeune and Gautam Dasarathy and Anshumali Shrivastava and Richard G. Baraniuk. Mission: Ultra large-scale feature selection using count- sketches. In International Conference on Machine Learning, pages 80-88. PMIR, 201 8.
[4] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing ml predictions for online algorithms. International Conference on Machine Learning, pages 303-313, 2020.
[5] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Mare Renault. Online computation with untrusted advice. In 11th Innovations Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhi-Leeibniz-Zenin
für Informatik, 2020.
[6] Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Transactions on Algorithms, 19(2):1334, 2023.
[7] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitereik. Learning to branch. In International Conference on Machine Learning, pages 353-362, 2018.
[8] George Bennett. Probability inequalities for the of independent random variables. Journal of the American Statistical Association, 57(297):33-455 1962.
[9] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Logarithmic regret from sublinear hints. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pages 18222-28233 2021.
[10] Oscar Boykin, Avi Bryant, Edwin Chen, ellchow, Mike Gagnon, Moses Nakamura, Steven Noble, Sam Ritchie, Ashutosh Singhal, and Argyris Zymnis. Algebird. https://twitter github. 1 /at.///ll/rr///////oo/o/// 2016.
[11] Vladimir Braverman, Stephen R Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, and David P Woodruff. Bptree: an 12 heavy hitters algorithm using constant memory. In Proceedings of the 36th ACM JIGMOD-SIGACT-SIIAN Symposium on Principles of Database Systems, pages 361-376, 2017.
[12] CAIDA. Caida internet traces, chicago. http://www.aaaaaaadaaaaanaonnoss chicago.xml, 2016.
[13] Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IFEE Transactions on information theory, -2(2))489-50, 2006.
10

---

[14] Moses Charikar, Kevin Chen, and Martin Farach- Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pages 693-703. Springer, 2002.
[15] Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions graph streams. 10th International Conference on Learning Representations, ICLR, 2022.
[16] Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference Machine Learning, ICML, volume 162 of Proceedings of Machine Learning Research, pages 3583-3602, 2022.
[17] Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based on the sum of observations. Annals of Mathematical Statistics, 239457493-507, 1952.
[18] Kenneth L Clarkson and David P Woodruff. Low-rank approximation and regression in input sparsity time. Journal of the ACM (JACM), 63(6):1-45, 2017.
[19] Edith Cohen, Ofir Geri, and Rasmus Pagh. Composable sketches for functions of frequencies: Beyond the worst case. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[20] Graham Cormode and Shan Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithmms, 55(1):58-77) 75, 2005.
[21] Erik D Demaine, Alejandro López-Ortiz, and J Ian Munro. Frequency estimation of internet packet streams with limited space. In Esa, volume 2, pages 348-360. Citeseer, 2002.
[22] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference Machine Learning, pages 2687-2696, 2021.
[23] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvit- skii. Faster matchings via learned duals. Advances in neural information processing systems, 34:10393-10406 2021.
[24] Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Learning sublinear-time indexing for nearest neighbor search. arXiv preprint arXiv:1901.0844 2019.
[25] David L Donoho. Compressed sensing. IEEE Transactions on information theory, 52(4):1289- 1306, 2006.
[26] Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson. Online algorithms with costly predictions. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 8078 -1011. PMLR, 2023.
[27] Elbert Du, Franklyn Wang, and Michael Mitzenmacher, Putting the "learning" into learning- augmented algorithms for frequency estimation. In Proceedings of the 38th International Conference on Machine Learning, pages
2021.
[28] Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-based support estimation in sublinear time. In 9th International Conference on Learning Representations, ICLR, 2021.
[29] Paul Erdōs. On lemma of littlewood and offord. Bulletin of the American Mathematical Society, (12))8898 898-902, 1945.
[30] Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning- augmented k--maas clustering. In 10th International Conference on Learning Representations, ICLR, 2022.
11

---

[31] Cristian Estan and George Varghese. New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice. ACM Transactions on Computer Systems (TOCS), 21(3):270-313, 2003.
[32] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for bent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, pages 2019.
2219-2327,00
[33] Amit Goyal, Hal Daumé III, and Graham Cormode. Sketch algorithms for estimating point queries in nlp. In Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language learning, pages 1093-1 1093-1103, 2012.
[34] Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. Augmenting online algorithms with E-accurate predictions. Advances in Neural Information Processing Systems, 35:2115-2121 2022.
[35] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, (8(330))13-300 1963.
[36] Chen Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
Leasningbbased
[37] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious learning- augmented caching. In International Conference on Machine Learning, pages 9588-9601. PMLR, 2022.
[38] Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning-based low-rank approximations. In Advances in Neural Information Processing Systems, pages 7400-7410, 2019.
[39] Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. data stream algorithms. In International Conference on Learning Representations, 2020.
[40] Richard M Karp, Scott Shenker, and Christos H Papadimitriou. A simple algorithm for finding frequent elements in streams and bags. ACM Transactions on Database Systems (TODS), 28(1):51-555 2003.
[41] Elias Khalil, Hanjun Dai, Yuyu Zhang. Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pages 6348-6358, 2017.
[42] Tim Kraska, Alex Beutel, Ed Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, pages 489-504, 2018
[43] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithmms, pages 1859-1877. SIAM, 2020.
[44] Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David Woodruff. countsketch. In / /ith International Conference on Learning Representations, ICLR, 2023.
Learning the positions in
[45] John Edensor Littlewood and Albert C Offord. On the number of real roots of random algebraic equation. ii In Mathematical Proceedings of the Cambridge Philosophical Society, volume 35, pages 133-148. Cambridge University Press, 1939.
[46] Zaoxing Liu, Antonis Manousis, Gregory Vorsanger, Vyas Sekar, and Vladimir Braverman. One sketch rule them all: Rethinking network flow monitoring with univmon. In Proceedings of the 2016 ACM SIGCOMM Conference, pages 101-114, 2016.
[47] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3302-3311, 2018.
[48] Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. In VL.DB'02: 02: Proceedings of the 28th International Conference on Very Large Databases, pages 346-357. Elsevier, 2002.
12

---

[49] Ahmed Metwally, Divyakant Agrawal, and Amr EI Abbadi. Efficient computation of frequent and top-k elements data streams. In International Conference on Database Theory, pages 398 412. Springer, 2005.
[50] Gregory T Minton and Eric Price. Improved concentration bounds for count-sketch. In Proceedings of the twenty-fifth anmual ACM-SIAM symposium on Discrete algorithms, pages 669-686. Society for Industrial and Applied Mathematics, 2014.
[51] Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming. 2(2):143-152, 1982.
[52] Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching, In Advances in Neural Information Processing Systems, pages 464-473, 2018.
[53] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In //th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[54] Thy Nguyen, Anamay Chaturvedi, and Huy Le Nguyen. Improved Marming-augment algo- rithms for k-means and k-medians clustering. 2023.
[55] Greg Pass, Abdur Chowdhury, and Cayley Torgeson. A picture of search. In Proceedings of the 1st international conference on Scalable information systems, pages 1-es, 2006.
[56] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pages 9661 1670, 2018
[57] Sandeep Silwal, Sara Ahmadian, Andrew Nystrom, Andrew McCallum, Deepak Ramachandran, and Seyed Mehran Kazemi. Kwikbucks: Correlation clustering with theap-weak, and expensive- strong signals. The Eleventh International Conference on Learning Representations, 2023.
[58] Partha Talukdar and William Cohen. Scaling graph- based semi supervised learning to large number of labels using count-min sketch. In Artificial Intelligence and Statistics, pages 940-947. PMLR, 2014.
[59] Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data survey. Proceedings of the IEEE, 104(1):34-57, 2016
[60] Alexander Wei and Fred Zhang. Optimal mouusteess-conisteenn trade-offs for learning- augmented online algorithms. Advances in Neural Information Processing Systems, 33:8042- 8053, 2020.
[61] David Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trendy& in Theoretical Computer Science, 10(1-2):1-157, 2014.
[62] Minlan Yu, Lavanya Jose, and Rui Miao. Software defined traffic measurement with opensketch. In NSDI, volume 13, pages 29- 2013.
[63] Matei Zaharia, Reynold S Xin, Patrick Wendell, Tathagata Das, Michael Armbrust, Ankur Dave, Xiangrui Meng, Josh Rosen, Shivaram Venkataraman, Michael J Franklin, et al. Apache spark: a unified engine for big data processing. Communications of the ACM, 59(1)):56-11 2016.
13


Reviews:
[{"review_id": "jVEqh6rQkg", "reviewer": "Reviewer_yxpU", "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.\nThey 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.", "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?\n\nAlg 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?\n\nCould 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.\n\nCould you also measure and disclose the power law exponent for the CAIDA and AOL datasets?\n\nFigures 2-5: Could you use the same color for best Our (C=..) line in the left and right sub-plots? \n\nLines 249-250: three columns and varying number of rows -> 3 rows and varying number of columns (typo).", "limitations": "Yes, it's absolutely forthcoming and adequate.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1) Problem and techniques studied are extremely well motivated and widely used.\n2) Solid theoretical analysis and tight new lower and upper bounds.\n3) Introduces multiple new algorithm variants.\n4) Substantial error reduction in the experiments.\n5) Paper is well written and structured.\n\n", "weaknesses": "1) No experiments with the theoretically analyzed algorithm, no theory for the simpler variant in the experiments.\n2) I would love to see some experiments with the parsimonious algorithm as well.\n3) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad to hear you found our paper interesting and appreciate your comments! We address them below:\n\n>No experiments with the theoretically analyzed algorithm, no theory for the simpler variant in the experiments.\n\nThe specific setting of parameters for the theoretical algorithm (number of CS tables, threshold for heavy/light elements) are chosen to achieve the best asymptotic bounds we were able to prove. In practice, our belief (backed up by the experimental results) is that the core algorithmic idea of truncating low estimates to zero will yield benefits, but that the specific parameters/setup best for the asymptotics are likely not the best when you process a specific dataset. It is a very nice question whether a simplified algorithm could be shown to achieve the same bounds as our algorithm which uses $O(\\log \\log n)$ tables.\n\n> I would love to see some experiments with the parsimonious algorithm as well.\n\nWe are glad to hear your interest and will try to include experiments using the parsimonious version of the learned algorithm in the final paper.\n\n>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.\n\nThis is a fair point, and we will make this explicit in the paper. At least for the learned algorithms, as the high-level idea for applications is that the user is processing similar data over time (and therefore can learn some structure), we believe it is reasonable to also think that they can tune hyperparameters on past data. Though this may not be the case in applications of the non-learned algorithms, and we will mention this.\n\n>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? \n\nThank you for your comment and pointing out the typo. Indeed, the 4 should be a 3 (or any fixed odd integer at least 3). We will fix the typo in the updated version of the paper.\n\n> 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? \n\nThis is a very crucial but subtle point and we thank you for pointing it out. We hope the following explanation is informative. First, we know that a *single* CountSketch (CS) table cannot achieve the guarantees of our best algorithm. Indeed, Table 1 (and our Theorem C.4) gives the tight error bound for a single CS table. The intuition for why a single CS table is not sufficient is roughly as follows: a large portion of the error is incurred due to elements whose true frequencies are much smaller than the expected error guarantees of CS (more rows only improve the concentration of the error, not the expected value!). Thus, we cannot simply rely on estimates from a CS table and must do something different.\nIndeed, our algorithm goes beyond CS by employing a two step procedure. The first step can be thought of as a filtering step like you stated. This filtering step informs us whether to use the estimate of the very last (large) CountSketch table or output 0. Multiple tables in the first step simply reduces the probability that we accidentally use the estimate of the last CS table for these ‘tiny’ frequencies (where the ‘right’ answer is to output 0). It turns out that it’s enough to ensure this failure probability is at most $1/poly(\\log n)$, so using $O(\\log \\log n)$smaller CS tables in the filtering step suffices and gives a clean way to prove our improved bounds. It could be true that much fewer CS tables suffice for the filtering step, and this is an interesting question for future research. \n\n>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\n\nWe did indeed consider questions of this type and for the first four algorithms of Table 1 (for power law distributions), we do have (nearly) tight bounds. For the remaining two algorithms, we have some partial analysis, which needs some polishing. We will consider including these bounds in the final version of the paper. It is an interesting direction for future work to consider other distributions like log-normal as you suggested.\n\n>Could you also measure and disclose the power law exponent for the CAIDA and AOL datasets? \n\nThe frequency plots of both CAIDA and AOL datasets are given in Hsu et al and we will provide a reference to their discussion on power law parameters of these datasets.\n\n>Figures 2-5: Could you use the same color for best Our (C=..) line in the left and right sub-plots? \n\nThank you for the suggestion. We will update the figure.\n\n>Lines 249-250: three columns and varying number of rows -> 3 rows and varying number of columns (typo). \n\nThank you for pointing out the typo. It will be fixed in the updated version.\n\n\n"}, {"review_id": "B2uZwUAPs9", "reviewer": "Reviewer_5HgB", "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.", "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. \n\nIn 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.", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n\nFurthermore, the experimental section does not include results for the parsimonious algorithm and less heavy-tailed distributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your interest in our paper and your comments. We address questions and concerns below\n\n>It appears that for non-Zipfian distributions, the non-simplified Algorithm 2 would have to perform two passes over the data stream since Algorithm 6 would need to first output an estimate of the L2 norm of the tail of the frequency vector which presents a major drawback. \n\nWe believe there is a misunderstanding and we hope our comment clarifies it. All of our algorithms only require \\emph{one pass} over the stream. Algorithm 2 outputs an estimate of the frequencies \\emph{after} the stream has ended. Furthermore, the output of Algorithm 6 is only used to compute approximate frequencies after the stream has ended. Thus, both Algorithm 1, our main streaming algorithm, and Algorithm 6, which estimates the tail norm of the frequency stream, can be run in one pass in parallel. Later, after the stream ends, they can be combined to output approximate estimates. \n\n>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. \n\nThanks for pointing out this discrepancy. Indeed, the predictions we have for CAIDA are worse than that of AOL (accuracy of recovering the top 1000 say is around 0.4 for AOL and 0.2 for CAIDA). We are working to investigate why this discrepancy exists and will update the paper accordingly as well as include quantitative details on the prediction quality.\n\n>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. \n\nAccounting for the space used for learning is an important consideration. As pointed out in Hsu et al. in the setting where we are sketching many subsequent streams of data (e.g., different days), the space cost for storing a learned model can be amortized over time. We will add a brief discussion of this point to the paper including quantitative details.\n\n>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.\n\nSee above.\n\n>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. \n\nThanks for the comment. We agree that it would be useful to have this stated more clearly in the paper, and will do so in the final version.\n\n\n"}, {"review_id": "gmGKV4EXAa", "reviewer": "Reviewer_TyeE", "summary": "Authors study frequency estimation algorithms CountMin and CountSketch\nand propose their modifications tailored for heavy tailed distributions.\nThey first analyze CountMin and CountSketch, showing that the second\none achieves better theoretical bounds on such distributions which explains\nexperimental results in previous work.\nThey propose a different algorithm with significantly better performance\nbounds on heavy tailed distributions which also satisfies worst case guarantees\n(for the case when the input does come from a considered heavy-tailed distribution)\nwhich are comparable to CountSketch.\nThey also propose an ML-augmented variant of their algorithm which assumes that\nthere is an oracle which correctly identifies half of the heavy hitters. This algorithm\nalso works in parsimonious setting where it is allowed to receive only a few predictions.\n", "questions": " * if your algorithm reports too many items as heavy hitters, what does your algorithm do?\n* 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$?", "limitations": "assumptions clearly stated in the theoretical results", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* They consider problem important both in theory and practice in a setting which occurs often in practice\n* They show limitations of the existing algorithms and design new ones overcoming these limitations\n* 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\n* 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">I did not see lower bounds for the problem in their setting. It is not clear whether better algorithms are possible \n\nProving lower bounds for learning-augmented frequency estimation, or even frequency estimation under our expected error metric, is an interesting future research direction. \n\n>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 \n\nOur learned version has worst case guarantees, even if the predictions are totally incorrect. This is because the algorithm explicitly keeps track of the frequencies of a select number of elements (those deemed the top O(B) heavy elements by the predictor). For these elements we incur no error, even if they don’t turn out to be true heavy elements. For the other elements, our algorithm inputs them into our improved version of CountSketch without predictions, whose guarantees are listed in Theorem 2.1 (see Lemma 3.3 for a general version with no Zipfian assumptions). This is the same type of worst-case guarantees given by prior works such as Hsu et al.\n\n\n>If your algorithm reports too many items as heavy hitters, what does your algorithm do? The 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 ith heavy hitters with some  probability depending on i?\n\nFor our best error bounds given in Theorem 3.1, we do assume that the predictor correctly identifies the top O(B) heavy elements. This is the same prediction model used in the prior work of Hsu et al. It is indeed likely that the prediction model can be relaxed to obtain similar improvements. Our algorithm is more robust to false positives, meaning light elements which are classified as heavy, than false negatives, which are heavy elements classified as light. Therefore, it is likely that our best results extend to the case where the prediction’s accuracy is tied to the true heaviness of the frequency. Nevertheless, as demonstrated by our superior empirical results, our algorithm generalizes to noisy real world predictions, demonstrating the versatility of the prediction model used in our work and Hsu et al.\n\n"}, {"review_id": "HgEDNiUsIu", "reviewer": "Reviewer_UWwz", "summary": "Summary of the Paper\n==================\n* 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.\n* 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|$.\n* 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$).\n * They also provide tight bounds for the expected estimation error of CountSketch, with and without learning.\n* 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)$).\n* They also propose a parsimonious variant of the algorithm (limited number of queries) and do an experimental evaluation.", "questions": "None", "limitations": "Not applicable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "\n* 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).\n* 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).\n* The proposed \"better frequency estimation algorithm\" provides tangible improvements over CS and CM, both wiith and without learning-augmentation.\n* 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.\n* The work includes the implementation of the algorithms and experimental evaluation.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are happy to hear that you found our paper interesting and thank you for your time and comments. "}, {"review_id": "FHb7KcCHOT", "reviewer": "Reviewer_iUr9", "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.\n\nIn 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. \n\nExperiments justify the theory is predictive of performance. ", "questions": "(see Weaknesses, please)", "limitations": "na", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Learning-augmented frequency estimation is itself a very nice question, I was looking forward to reading this paper in my pile. \n- The algorithm is clean, straight-forward. I believe the results are correct. \n- The paper is grammatically well-written.\n\n", "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). \nPerhaps 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?\n\n- 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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thanks you for your thorough review and your comments. Below we address your questions and concerns.\n\n>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.  \n\nWe would like to first point out that our algorithm without predictions (Theorem 2.1) already outperforms the learning-augmented version of the standard CountSketch algorithm supplied with perfect predictions, in low space regimes. Secondly, while it is true that the best bounds obtained in Theorem 3.1 assume access to perfect predictions, our learned version does indeed possess worst-case guarantees, even if *all* predictions are incorrect. The worst case guarantees follow simply by the design of the algorithm: it explicitly keeps track of the frequencies of a select number of elements (those deemed the top O(B) heavy elements by the predictor). For these elements we incur no error, even if they don’t turn out to be true heavy elements. For the other elements, our algorithm inputs them into our improved version of CountSketch without predictions, whose guarantees are listed in Theorem 2.1 (see Lemma 3.3 for a general version with no Zipfian assumptions). This type of worst-case guarantees as well as the prediction model is identical to prior works on learning-augmented algorithms for frequency estimation [1]. In addition, it mirrors the consistency/robustness guarantees that appear in several algorithms with predictions papers (see the survey [2]) which bound the performance with perfect predictions (consistency) and with arbitrary predictions (robustness).\nLastly, we believe our best error guarantees, which are given in Theorem 3.1, can also be obtained with weaker prediction models. Our algorithm is more robust to false positives, meaning light elements which are classified as heavy, than false negatives, which are heavy elements classified as light. Therefore, it is likely that our “learned version” results extend to the case where the prediction’s accuracy is tied to the true heaviness of the frequency. Nevertheless, as demonstrated by our superior empirical results, our algorithm generalizes to noisy real world predictions. This demonstrates that the prediction model (used in our work and [1]) is a useful model to develop novel algorithms. \n\n>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? \n\nWe can in fact provide some trade-offs between the quality of the prediction and the weighted error bounds, specifically for the (Learned) CountSketch algorithm. We left these out of the submission but will consider including them in the paper. For expected error, these results give a smooth trade-off between the bounds for the classic and corresponding learned algorithms (row 2 and 4 of Table 1). The result assume that the predictor may misclassify an element with some probability $\\delta$. If $\\delta=O(\\ln(n/B)/\\ln(n))$, then it turns out that we asymptotically obtain the same expected error as with the learned variant which has access to perfect predictions. For the (Learned) CountMin algorithm (row 1 and 3 of Table 1), a similar trade-off is presented in [1] where it is also the case that when $\\delta=O(\\ln(n/B)/\\ln(n))$, the learned variant of the algorithm has the same asymptotic expected error as with a perfect predictor. As indicated above, there is more interesting work to be done on the prediction error. Especially exploring the asymmetry in the robustness to respectively false positives and negatives is a direction for future work.\n\n>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. \n\nThe suggested table is already in the appendix and following the reviewer’s suggestion, we will move Table 2 in the main body and integrate it in Table 1. To summarize, [Hsu et al. 2019] only analyzed CM and its learned variant.\n\n\n\n[1] Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. ICLR 2019.\n\n[2] Michael Mitzenmacher and Sergei Vassilvitskii. 2022. Algorithms with predictions. Commun. ACM 65, 7 (July 2022), 33–35. https://doi.org/10.1145/3528087\n"}]

Author rebuttal:

Meta-review: The reviewers unanimously agreed that this paper was of interest as it gives several compelling results including tight bounds for frequency estimation with count-min and count-sketch for Zipfian distributions, a simple new approach based on truncating small frequency estimates, which gives stronger error bounds, and a learning augmented version of that approach with even tighter error bounds. The paper is clearly above the bar and should be of general interest to those working on learning augmented algorithms and streaming algorithms.
Decision: Accept (spotlight)