Learning-Augmented Data Stream Algorithms
Authors: Tanqiu Jiang
Yi Li
Honghao Lin
Yisong Ruan
David P. Woodruff
Venue:  (2020)
Keywords: streaming algorithms
heavy hitters
F_p moment
distinct elements
cascaded norms

Abstract: The data stream model is a fundamental model for processing massive data sets with limited memory and fast processing time. Recently Hsu et al. (2019) incorporated machine learning techniques into the data stream model in order to learn relevant patterns in the input data. Such techniques were encapsulated by training an oracle to predict item frequencies in the streaming model. In this paper we explore the full power of such an oracle, showing that it can be applied to a wide array of problems in data streams, sometimes resulting in the first optimal bounds for such problems. Namely, we apply the oracle to counting distinct elements on the difference of streams, estimating frequency moments, estimating cascaded aggregates, and estimating moments of geometric data streams. For the distinct elements problem, we obtain the first memory-optimal algorithms. For estimating the $p$-th frequency moment for $0 < p < 2$ we obtain the first algorithms with optimal update time. For estimating the $p$-the frequency moment for $p > 2$ we obtain a quadratic saving in memory. We empirically validate our results, demonstrating also our improvements in practice. 

Published as a conference paper at ICLR 2020
LEARNING-AUGMENTED DATA RITHMS
STREAM
ALGO-
Tanqiu Jiang
Li
Department of Electrical and Computer Engineering Lehigh University Bethlehem, PA 18015, USA taj320@lehigh.. edu
School of Physical and Mathematical Sciences Nanyang Technological University Singapore 637371
#ili@ntu.edu.cr
Honghao Lin
Yisong Ruan
Zhiyuan College
Department of Software engineering
Shanghai Jiao Tong University Shanghai, China 200240
Xiamen University
Xiamen, Fujian, China 361000
honghao.lines edu. on
243201522028028stuu edu xmu, on
David Woodruff
Computer Science Department
Carnegie Mellon University Pittsburgh, PA 15213, USA
dwoodrufecs cmu. edu
ABSTRACT
The data stream model is a fundamental model for processing massive data with limited memory and fast processing time. Recently Hssu et al. (2019) incor- porated machine learning techniques into the data stream model in order learn relevant patterns in the input data. Such techniques led to the training of an oracle to predict item frequencies in the streaming model. full power of such an oracle, showing that it can be applied to a wide array of problems in data streams, sometimes resulting in the first optimal bounds for such problems, and sometimes bypassing known lower bounds without such oracle. We apply the oracle to counting distinct elements on the difference of streams, estimating frequency moments, estimating cascaded aggregates, and estimating moments of geometric data streams. For the distinct elements problem, we bypass the known lower bound and obtain new space-optimal algorithm. For estimating the p-th frequency moment for 0 < < 2 we obtain the first algorithms with optimal space and update time. For estimating the p-th frequency moment for > 2 we obtain a quadratic savings in memory, bypassing known lower bounds without an oracle. We empirically validate our results, demonstrating also our improvements in practice.
this paper we explore the
INTRODUCTION
Processing data streams has been an active research field in the past two decades. This is motivated by the increasingly common scenario where the size of the data far exceeds the size of the available storage, and the only feasible access to the data is to make a single or a few passes over the data. This situation occurs, for example, in network applications with high-speed packets being sent through routers with limited resources. Other examples include processing internet search logs, sensor net- works, and scientific data streams. For introduction data streams, see, e.g., Muthukrishnan 2005).
Formally, in the data stream model, assume there is underlying frequency vector E Z" initialized to 0", which evolves throughout the course of a stream. The stream consists of updates of the form (ž, w), meaning I, xe w. Suppose M is such that ||æ:]] max (1....)) |xa| < M

---

Published as a conference paper at ICLR 2020
throughout the stream. At the end of the stream, we asked to approximate f()) for a function
f Z" + R. Because of the sheer size of the stream, most algorithms are approximate and randomized. Typically, such algorithms output estimate Z for which Pr[(1 - f) s Z s (1 + =))(()) 2 2/3, where the probability is over the randomness used by the algorithm, and not of the input stream, which may be worst-case stream. The success probability 2/3 can be replaced with any constant greater than 1/2 by independently repeating the algorithm a constant number of times and taking the median estimate. The space complexity of the algorithm is measured in bits and the goal is to use much less than the trivial n bits of space required to store I.
A common difficulty in designing algorithms in the data stream model is that the coordinates for which |ay| is large. i.e., the heavy hitters, are not known in advance. Such coordinates usually require very accurate estimates in order to achieve an accurate final estimate of the function value. A number of techniques have emerged for identifying such coordinates, such as the Count-Min and CountSketch. These techniques are often used at multiple scales by subsampling the input coordinates and finding heavy items in the subsample, and have found applications to estimating frequency moments, cascaded aggregates, earthmover distance, and empirical entropy, among other statisties (Indyk& & Woodruff 2005 Chakrabarti et al. 2006 Jayram & Woodruff 2009 Andoni ett al.. 2009: McGregor et al. 2016).
In many applications. however, the worst-case input is rarely seen; in fact, there is usually a pattern inside the underlying vector. For instance, in network traffic monitoring, the large or "elephant" flows fluctuate on daily basis, but the actual source and destination servers of those flows do not vary much. In our formulation, this implies the value fluctuates while whether or not æ; is a heavy coordinate remains stable. Motivated by this well related work learning oracles for algorithm design (Gupta & Roughgarden 2016) Dick et al., 2017: [alcan et al. 2018a b), Hsu et al.) 2019) introduced the notion of a heavy hitter oracle into the data stream model. The heavy hitter oracle, trained on past data, receives coordinate index i and returns a prediction of whether x; will be heavy or not. They showed that such an oracle simplifies classical heavy hitter algorithms such as COUNT-MIN and COUNT-SKETCH We note that similar oracles were also studied in previous work, c.g., membership oracles for Bloom filters by Kraska et al. (2017). These works demonstrate the feasibility of creating such oracle using machine learning techniques. Recently, learned or- acles for low rank approximation, which can be viewed as an analogue of heavy hitters for heavy directions, was explored by Indyk et al. (2119)
The work of Hsu et al. (2019) is the starting point of our work. While Hsu et al. (2019) showed applications of the heavy hitter oracle frequency estimation, the full power of such oracle remained largely unexplored. Our main goal is to understand if such an oracle is more broadly useful, and whether it can give memory and time improvements to the large number of data stream problems mentioned above. Accurately estimating the heavy hitters in a vector is the bottleneck of existing algorithms for numerous data stream problems, and one cannot help but ask:
Can a heavy hitter oracle be applied to a large number of problems in the data stream model to obtain significantly improved bounds for these problems?
We consider estimating the following common functions f(x) in the data stream model:
Distinct Elements: f(z) = ||æ]|o. where ||.: llo is the number of nonzero coordinates of x. defined as ||=||o- Hi I3 * 0}|- This quantity is useful for detecing denial of service attacks and database query optimization (Kane et al., 2010b).
the Fp-Moment: fxx = || where |><| is the usual f--norm of x, defined as ||^||p
[ |z 1 For 0 < p < 2, these are often more robust than the Euclidean norm (Indyk] 2000). For p these are used to estimate skewness and kurtosis (Indyk & Woodruif] (005). the (ki, p)Cascade Norm: in this problem J: is an n x d matrix that receives updates to its in-
dividual entries, and f(x)= = || k.p := (E, 2ig ///////// These are useful for executing
multiple databse queries (Cormode & Muthukrishnan 2005 Jayram & Woodruff 2009).
These problems have also been studied for non non-numeiiaal data, such as geometric data. For example, stream of rectangles in Tirthapura & Woodruff (0122.
the Fp Fp-moment problem was studied One can think of underlying A d'ddimensional vector 2; identified with d-dimensional rectangle {1...., A]d. Without loss of generality, we assume that A is a power of 2. Each item in the stream is pair of the form (R, w). where R is d-dimensional rectangle and w is an integer, meaning
2

---

Published as a conference paper at ICLR 2020
Problem
Result Type
Previous Result
This work
( 2 n log logn))
0 2
log n log Theorem
Distinct Elements
S
Kane et al. 2010b)
( 2/p)
(n 1/p
F6 Moment (p > 2)
S
B.g.AAndor et al.
2011
Theorem
Update T
amortized O(log" log log :
expected amortized O(1)
Pp Moment Fast Update (p
Reporting T
0 log log log )
0
Kane et al. 2011
Theorem
Cascaded Norm (k p 2 2)
O( 2/k d"' 2/p)
O 1/k- (2k) d 1/P)
S
Jayram & Woodrufi (2009)
Corollary 20
Rectangle Fp Moment (p> > 2)
O(Ad(1-27)) (oly
O d(1/2-1/p) poly voly()))
S Tirthapura Woodruff(
Theorem 23
Table I: Summary of previous results and the results obtained in this work. We assume that m, M
poly(n). In the column of result type, S denotes space complexity and T denotes time complexity. We view as constant for the listed results of the Fp Moment and Cascaded Norm problems.
Problem
Heavy Hitter Oracle
Distinct Elements
2
>
2paly[1/e)
F3 Moment (p > 2)
T.
2
x
Fp Moment Fast Update (p < 2)
2
P
2
|x; P >
Tog (1/e) log Log[1/e] |
Cascaded Norm (k: 2 p 2 2)
[ P
>
|
/
Rectangle Fp Moment (p > 2)
- /
Table 2: Summary of the threshold of the heavy hitter oracles used in each problem. Note that two oracles are used for the F, Moment Fast Update problem.
I; f 24 + w for all points E R. The goal is estimate (xx |>>|. This is called the Rectangle F3 Momeettt problem, which occurs in spatial data streams and constraint databases.
Our Results We show that heavy hitter oracle can greatly improve the complexity of wide array of commonly studied problems in the data stream model, leading to the first optimal bounds for several important problems, and shattering lower bounds that have stood in the way of making further progress on important problems. We note that not only do we give new algorithms, we also give several lower bounds for algorithms equipped with the oracle, that show optimality of algorithms even with oracle. Our algorithms not only give practically better, theoretically- grounded improvements to these problems with an oracle, they also shed light on what exactly the difficulties are of making further progress data stream problems without an oracle. We consider both perfect oracles and oracles that may sometimes make mistakes.
We summarize in Table [ our improvements to existing algorithms using appropriate heavy hit- ter oracles, whose conditions are summarized in Table Throughout, we make the conventional assumption that m, M (n)y(n).
Distinct Elements: For the problem of estimating ||<||o. we improve the prior memory bound of 0 n(lo log log n)) O log n log ). For constant e, this gives an optimal O n bits of memory, breaking recent 2(log n log log n) bit lower bound shown in Woodruff & Yang (2019) Examining the lower bound argument Woodruff & Yang (2019), the hard instance is precisely when there are many items of large frequency, namely, the product of the first small number of primes. This prevents hashing- based algorithms, such as the one in Kane et al. (2010b), from working with Ollgg)) v)) bits of space, since hash values are typically taken modulo a small prime and such heavy items necessitate the use of a large enough prime. Surprisingly, we show that with a heavy hitter oracle, that our (log n) bit algorithm is optimal even given a heavy hitter oracle; see the (logn) lower bound in Alon et al. (1999), which holds even if all item frequencies are in the set (0, 1,2).
separately handle such items and thus bypass this lower bound. We note
3

---

Published as a conference paper at ICLR 2020
Fp -M-mmett Estimation, 0 < p < 2: There is long line of work on this problem with the best known bounds given in Kane et al. (2011), which achieve an optimal Oie-2 n) bits of space, and (1ogg(1/c) log log 1/c) time to process each element. The existing algorithm is based on separately handling those elements i for which |a,|² 2 <| i.e., the heavy hitters, from the remaining "light items". Although we can simply store the heavy hitters given heavy hitter oracle, unfortunately, the large Ollog"(1/ / log log 1/e) processing time in the algorithm of Kane et al. (20TT) also comes from running fast multipoint evaluation on the light elements.
We observe that if we instead train two oracles, one for detecting heavy hitters, and one for de- tecting items Ty with |a:||" 2 (I/s) [og( |a-1 then we can also separate out "medium items", i.e., items that are detected with this oracle but not our heavy hitter oracle. There are only O (1/e) log log(1/e)) medium items and so assuming log n 2 poly(log(1 (1/)), one could perfectly hash all such items and maintain their hashed identities in the optimal O log n) bit of space. However, one cannot maintain their counts, since each count is O(log n) bits, and approxi- mate counts do not work if the stream can increment or decrement the coordinate values 24. This is too much memory, as it would lead to O -2 (log n.) log"(1/e) log log(1/))) bits of space, even worse than without the oracle. We could also maintain so-called p-stable random variable for each medium item, and use it to estimate the Fp-moment of the medium items, but this would again be O(e (log n) (1/ee log log(1/e) bits of space to store one random variable per medium item. We instead observe that most of the p-stable random variables are small, and so can be stored with many fewer than log n bits, and therefore globally we can get by with only O(c log n.) bits in total for estimating the medium items. Finally, for the light items, the critical observation that we can sub-sample a (1/e] log [1/{ fraction of them, and still accurately estimate their contribution. But this means since while that has update time Olog" (1/c) log log(1/c)), on average it is only executed on one out of every log"(1 log log(1/e) items.
the multipoint evaluation algorithm of Kane al. (20TT) such items,
In summary, with the aid of our oracles and by separately handling these three types of items, we are able to achieve the optimal ((1) amount of update time per item, while retaining the optimal O(c log n) bits of memory.
F, F,-Moment Estimation for p 2: It is well-known (Bar- Yossef et al. 2004) that a hard input distribution for this problem is when a random coordinate of a has absolute value n/ and all other coordinates have value 0 or 1. In this case, one needs to certify that there is indeed a coordinate of value n 1/2, as it contributes a constant fraction of - There is a known 12n))2/p) bits of space lower bound for this. However, heavy hitter oracle exactly allows us overcome this, as it can be used to separately identify such items. Our idea is to separate out every item i for which |r,|2 2 ||اB with the oracle, and run an existing Fp-estimation algorithm on such items. Since there are at most 1/2 items, existing algorithms give (n2/2)1-2/p poly(logn) = n 1/2-1//p poly pooy(log n) bits of memory for this problem. For the remaining light elements, one can show that if one subsamples only a 1/2 fraction of them and then runs an existing F--estimation algorithm on them, one can use this accurately estimate their contribution. This again takes 1/2-1/1 pooy n) bits of memory, balancing the memory with the other part of our algorithm and giving a quadratic improvement in memory in the case without a heavy hitter oracle. Overall our algorithm uses ( 1/p poly (log bits with an oracle and we can in fact show that this is tight up to logarithmic factors as there exists lower bound of 2/22/11 bits provided the same oracle.
We describe our algorithms for cascaded norms and rectangle Fp moments in the appendix.
We conduct experiments for the distinct elements and the Fp moment (p > 2) problems, on both real-world and synthetic data, which demonstrate significant practical benefits.
2 PRELIMINARIES
Notation We let [n] denote the set n.). The function Isb(z) denotes the index of the least significant bit of a non-negative integer x.
4

---

Published as a conference paper at ICLR 2020
Space and Time Complexity For streaming algorithms, the efficiency is characterized by the space (memory) complexity and the time complexity. The time is further divided into update time and re- porting time. A data stream algorithm maintains data structure D while processing the data stream and at the end of the stream, it outputs an approximation Z to (x) The space complexity refers to the size, in bits, of 'D. The update time refers to the time spent to update the data structure 'D upon receiving a single stream update. The reporting time refers to the time to output the approximation Z at the end of the stream.
Heavy Hitter Oracle We assume access to a heavy hitter oracle, which receives an input i E [n]. and outputs whether 2; will be heavy hitter at the end of the stream. The definition of heavy hitter varies for different data stream problems. There are two kinds of oracles. The first kind indicates whether or not |a:]] 2 T and the second kind indicates whether or not | 2 + ||= where T pre-determined threshold associated with the problem. We shall use an oracle of the first kind for the distinct elements problem and oracles of the second kind for all other problems.
In the experiments, the heavy hitter oracle receives an E [n]] and outputs the predicted value of T3. The implementation of the first kind of oracle is thus straightforward. For the second kind of oracle, there are at most T coordinates H2 satisfying |a,,?? 2 # =|[= We shall regard the largest T coordinates in the predicted vector æ as the heavy hitters in our implementation (instead of calculat- ing the | l of the predicted vector r), which is in conformity with the implementation in the prior experiments Hsu et al. 2019).
3 DISTINCT ELEMENTS
The current best algorithm for estimating Lo = ||æ]|oo in the presence of additions and deletions to coordinates of v, is due to Kane al. (0TO0). A key component of their algorithm is constant- factor approximation algorithm, called ROUGHLOESTIMATOOR which returns a value Lo satisfying Hh Lo S Lo I Lo with probability least 2/3. The space is (log n log log(m.M) bits and the up- date and reporting times are O(1). In this section, we improve the space of ROUGIILOESTIMATOR to (logn) n) bits with the help of trained oracle. All proofs are postponed to Section A
The algorithm first picks pairwise hash function h : [n] + [r]] and subsamples coordinates at log n scales, where the j-th scale consists of the coordinates i for which Isb(h(i)) = j. In each scale, it uses a small-space counting algorithm EXACTCOUNt to obtain, with probability at least 1 1- n, the exact value of ||æ|||o at that scale. Then it finds the deepest scale, i.e., the largest j. with |æжl above some fixed constant threshold, and returns Lo = 2 as the estimate. If such a j does not exist, it returns Lo
The EXACTCOUNT procedure in Kane et al. (2010b) uses a hash function N' [m] +
[B], where B Oee²) ) for some constant e for which /t' is perfect hashing of set of size at most c. Each bucket & E [B] is counter which keeps track of (Ento= mz) mod p for some large prime p. The estimate is the number of nonzero buckets, and EXACTCOUNT returns the maximum estimate of (log(1/nn) parallel repetitions.
Now, with the trained oracle, we can pick to be smaller (1/y( value in EXACTCOUNT. In the higher-Ievel ROUGHLOESTIMATOR algorithm, whenever an update made heavy coordinate i identified by the oracle, the corresponding bucket inside EXACTCOUNT is marked as nonempty regardless of the counter value, since we know the heavy item will never entirely deleted, since by definition it is heavy at the end of the stream (note this is not true of non-heavy elements). In the finds the deepest scale with at least one nonempty bucket.
end, R
The following is our new guarantee of EXACTCOUNT.
Lemma 1. Assume that Lo < and suppose that B = (c²)) The subroutine EXACTCOUNT
returns the exact value of Lo with probability at least 1 1- n using O(B log(1/e)) bits of space, in addition to storing O ([log(/nn) independently chosen pairwise innpriiie-ideeeddeet hash functions from [n] to [B). The update and reporting times are (()).
Now specify some details of the algorithm ROUGHT It chooses 141 and = 1/16 for EXACTCOUNT, and the EXACTCOUNT algorithms for different scales all share the same (1lo(() 1/1)) hash functions. The following is our new guarantee.
5

---

Published as a conference paper at ICLR 2020
The algorithm ROUGHLOESTIMATON outputs value Lo. which satisfies nio Lo I Lo & Lo with probability at least 13/16. The space complexity is O(log(n) log(1/c)) bits, and the update and reporting times are (1))
Theorem 2.
With constant- factor estimate R to Lo. the high-level idea is to subsample each index in [n] with probability K/R. Then the number of distinct surviving items is (()). To estimate the number of distinct surviving items efficiently, one hashes them into ( buckets and counts the number T of non-empty buckets, which is simulated by updating a bit vector of length ((K). The final estimate can be deduced from the number of distinct surviving items, which can be shown to be (1 + apprroxaaaininn to Fo when A = @(1/e)). Since we do not know Lo in advance, we have to guess its value using log n geometrically increasing values, and our memory can be thought of as a bucket matrix A of dimension (log n) x K. In parallel we run the ROUGHL.OSTTIMATOO above, so the end of the stream, we will obtain a constant- into the appropriate row of A (the appropriate buckets). A problem is how to efficiently maintain a bucket. In Kane et al. (0100), each bucket stores the dot product of frequencies hashing to it with random vector over large fimite field of order poly K log (n)),.)), using (log K +log (n.M) = (log((1/)) /e) + log log (n) bits. Now, using a similar argument to the proof of Lemma with the help of our heavy hitter oracle, we can mark the buckets containing a heavy hitter as nonempty and reduce the order of the finite field to (poly (1))). This improves the space complexity of each bucket to (l(o((/Ee) bits. Combined with the complexity of ROUGHLOESTIMATTE with the following theorem.
estimate R, allowing us look
we conclude
Theorem 3. There an algorithm for .aprrxxmiiii Lg using space O(c ((o-2(1og ni) log(1/c)) with success probability at least 2/3, and with ((1) update and reporting times.
4 F, ESTIMATION, p >> 2
We start with a well-known algorithm for estimating |æ]| in a stream.
Lemma 4 (Precision Sampling, (Andoni et al. (2011). There is a randomized algorithm, called the Precision Sampling algorithm, which returns an estimate X to ||=l such that it holds with probability at least 0.9 that (1 -() [=llB S X (1 + + The algorithm uses B(n)
O(p²c 1/ log(n) log(M)) bits of space.
In the rest of the section, we assume that there is an oracle which can tell us if |x, heavy hitter. The main idea is that we separately estimate the Fp momentt of the heavy hitters, and for the remaining light elements, we use sub-sampling to estimate their contribution with sampling rate 1/p.
|| is a
Let Tn, Ju S [n] denote the subsets of indices of the heavy hitters and the light elements, respec- tively. Since I4 < s, we can use an F' estimator to (1 + e)-aprooxmmaee || l with space B(s). For the light elements, we use sub-sampling algorithm: we set sampling rate 1/p, and for each item E Jt., with probability 1/p we choose it. For each item we choose, we calculate F. = Σ l and use pF, to estimation || llg. By Chernoff bound, with high probability, sample most 3n/p elements.
To analyze it, we let = pFs. and we have the following lemmas. All proofs this section are postponed to Section B
Lemma 5. E[Y] I1, Ip Var[Y] S -1|=113"
Lemma 6. we repeat the sub-sampling kpps times independently with sub-sampling rate pe?, we can get (1 + -)-aproximation of F, with probability at least 1 - 1/k.
If we use the estimator in Lemma 4 in both parts (heavy part and light part), The total space com- plexity is (ss) + 2 - Letting &
Vr. we obtain an F3 estimation algorithm with space 0(E-An112211 1/2-11/ log(n) log(M)). We remark that this bound is tight in up to logarithmic factors as there is lower bound of 1222/2-1//) bits even in the presence of the oracle.
Theorem 7. Under the assumption of a heavy hitter oracle, we can estimate ||=|| within a factor 1 2e in O(E 0n 1/2-1/2/1/// 1/p log(n) log( M)) bits with success probability at least 3/5.

---

Published as a conference paper at ICLR 2020
The above analysis is based on the assumption that the oracle is perfect. In practice, sometimes the oracle makes mistakes. Here we assume that for each item i, the probability the oracle gives us an incorrect prediction is 5. We have the following theorem for noisy oracles.
Theorem With a noisy heavy hitter oracle with error probability 5, we can estimate I|r|Ip within factor 1 + 2e in O( 06--112/201/9 log(n) ())( bits of space when d = O(1 nn), or in OiE ((E) 1 1-2p log(n) lo)(M)) bits of space otherwise. Both guarantees hold with success probability at least 3/5.
5 EXPERIMENTS
5.1 DISTINCT ELEMENTS
5.1.1
INTERNET TRAFFIC DATA
For this experiment, the goal to estimate the number of distinct packets for each network flow. A flow is sequence of packets between two machines on the Internet. It is identified by the IP addresses of its source and destination and the application ports.
Dataset: The traffic data is collected at a backbone link of a Tierl ISP between Chicago and Seattle in 2016 (CAIDA). Each recording session is around one hour. Within each minute, there are around 30 million packets (meaning 30 million updates) and 1 million unique flows. The distribution of packet counts over Internet flows is heavy tailed, see Hsu et al. (2019).
Model: We use the prediction results in Hsu et al. (2019), which predict the logarithm of the packet counts for each flow. In Hsu et al.) (2019), the authors use two RNNs to encode the source and destination IP addresses separately and additionally use two-layer fully-connected networks to en- code the source and destination ports, Then they concatenate the encoded IP vectors, encoded port vectors, and the protocol type as the final features to predict the packet counts. They use the first 7 minutes for training, the following minute for validation, and estimate the packet counts in subse- quent minutes.
We plot the estimation error vs. total number of buckets for the 20th minute the CAIDA data. We run the estimation algorithm 5 times and calculate the average estimation error. The result is shown in Figure 2 The total number of unique flows appearing in a single test minute is about 1.1 10 For every light coordinate, we make extra update that makes this coordinate 0 with probability 0.5.
Results:
There are two parts to our algorithm. For use the heavy hitter oracle to predict whether the coordinate will be larger than 2 We randomly select prime from [11,31] for the hash buckets. The total number of buckets in this part is about 4 x 103 (each bucket can store number in {0. 1,.., 31 and has an extra bit to indicate whether has been marked). For the other part of our algorithm, we create a bucket matrix of dimension (log n) x K with K ranging from 2 to 29, Each entry in A can also store number between 0 and and with an additional bit to indicate whether has been marked. From the plot we can see that the algorithm achieves approximation error of about 2.5% using at most 1.5 x 10* buckets, approximately 1.5% of the space needed if we were to keep an individual counter for each flow.
we set 10 and 7) 1/4. We
5.1.2 SYNTHETIC DATA
To further demonstrate the advantage of having a heavy hitter oracle, we run the previous algorithm due to Kane et al. (2010b) (where we randomly choose prime p E [11,3] as the divisor for each bucket) and input vector x of dimension n 10 with i.id entries uniform on {0, I,..., 1003. Then for each coordinate i and each prime p E [11,31] 31], we multiply I; by with probability 0.2. We set the threshold to be a heavy hitter to 200 that is, the oracle reports I; as a heavy hitter if [ > 210
modified algorithm on the synthetic data designed
follows: first, generate an
We use the optimal parameters in the last experiment (c 10. 17 1/4 and K 29) and vary the total number of buckets from 7000 to 15000. The results are shown in Figure ! We see that having an oracle significantly reduces the estimation error.
Results:
7

---

Published as a conference paper at ICLR 2020
0.25
0.200
675
0375
Aactngg Cammuon SroP
0.0
0.300
06.9
1020 3200
2000
Total MRarior Duchet
20000 11200 12000 13000 24002 22000
0020
10000
Figure 1: The estimation error of the Lo- norm in the synthetic data
Figure 2: The estimation error of the Lo- norm in the 20th minute of the CAIDA data
5.2 F, ESTIMATION
5.2.1 SEARCH QUERY DATA
For this experiment, the goal is to estimate the frequency moments of the vector indicating the number occurrences each search query appears.
Dataset: We use the AOL query log dataset, which consists of 21 million search queries collected from 650 thousand users over 90 days. There are 3.8 million unique queries. Each query is search phrase with multiple words. The distribution of the search query frequeeciess is Zipfian, see Hsu ct al. 2019).
We use the prediction result in Hsu et al. (019). which predicts the number of times each search phrase appears. Hsu et al. (2019), the authors train an RNN with LSTM cells that takes characters of search phrase input. The final states encoded by the RNN fed to fully- connected layer to predict the query frequency. They use the first days for training, the following day for validation, and estimate the number of times different search queries appear in subsequent days. We use this prediction result as an indicator which search phrases are the heavy hitters.
Model:
We plot the estimation error versus the total number of buckets for the 50th and 80th day (p = or p = 4). For the same data, we run the estimator 10 times and calculate the average estimation error. The results shown in Figure
Results:
For our algorithm, we notice that the total number of search phrases that appear in a single day is about 1.5 10a and so /n < 400. We can store the heavy coordinates identified by the heavy hitter oracle directly. Given the budget of the number of buckets, we divide them into two parts. Half of them were used to store the heavy items, and the other half are used by the sub-sampling algorithm with the precision sampling estimators to estimate the frequency moment of the light elements.
In comparison, we also run the classical precision sampling estimators. Our results show a larger estimation error owing to the constraint of relatively few buckets. Note that for fixed bucket budget Bua there is trade-off between the number k of repetitions and the number B = B /k of buckets allotted for the hash function in each repetition. We plot the results for different values of A 10, 20,30. 30.
clear from the plots that estimation error of the oracle-aided algorithm about 1% even when the total number of buckets is small, demonstrating strong advantage classical precision sampling estimators.
5.2.2 SYNTHETIC DATA
number real-world datasets have the property that the heavy coordinates contribute a large fraction of the F,-moment, increases, and needs only obtain good approximation of
8

---

Published as a conference paper at ICLR 2020
precse semoiing
16-
pression sempkin
02-
sampiny
predisim senoling
PrOson samping
14
preaxesn sempling
Our edlimttrtiigggg moncl))
edliaeont King onedle)
Netrape Extivtiin Ener
0--
1.2
1.-
0.8
0.2
0.0
203
200
130
500
6.0
100
200
300
(20
300
600
100
Total Mur bor of buckcts
Total Number of buccots
Figure 3: The estimation error of the moment of search queries. The left figure corresponds to p (80th test day) and the right p 4 (50th test day).
the Fp-moment of the heavy coordinates. This indeed one of the reasons why we achieved low error for search query estimation. In order to show that our subsampling algorithm also achieves good approximation for the light coordinates, we considered the following data set.
We generated an input vector of dimension n = 10 with the first /n coordinates being heavy and the remaining coordinates being light. Each coordinate a uniform random variable in (0, 1), later renormalized such that the heavy and the light parts contribute equally to the total F--moment, ie., | 1p = || lp.. Hence, a good approximation of ||>|| requires a good approximation of both parts.
Results: We plot the estimation error vs. total number of buckets for p 3 in Figure For our fixed the number & of repetitions to 100 and varied the total number of buckets from 108 to 2 x 106 (1% to 2% of the length of r). We repeated the sub-sampling algorithm 9 times. In each of the 9 repetitions, we also used the precision sampling estimators, repeating 100 times.
algorithm and classical precision sampling,
From the plots we that algorithm achieves significantly smaller relative approximation error than the classical precision sampling algorithm for every number of buckets. In particular, using 2 10th buckets, i.c., 2% space of what needed store the entire vector x, our algorithm achieves a 15% relative estimation error while the classical precision sampling obtains only a 27% relative error. Another observation is that since subsampling reduces the space consumption, our algorithm has faster update time when is large.
LCKNOWLEDGMENTS
0.5
Prechuin Semplng
The authors would like to thank the anonymous reviewers for helpful comments. Y. Li sup- ported in part by Singapore Ministry of Educa- tion (AcRF) Tier 2 grant MOE2018-T2-1-00 D. Woodruff would like to thank partial sup- port from the National Science Foundation un- der Grant No. CCF-1815840 and the Office of Naval Research (ONR) under grant N00014-18- 1-2562.
Sycrog- Eatmutoo 2014
3.59
0.50
630
0.3
Tutal FArriar of tudadd
Figure 4: Estimation error for the Fz-
moment on synthetic data

---

Published as a conference paper at ICLR 2020
REFERENCES
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. Efficient sketches for earth- mover distance, with applications. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pp. 324-330, 2009.
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In IEEE 52nd Anmual Symposium on Foundations of Computer Science, FOCS 2011,
Palm Springs, CA, USA, October 22-25, 201 I, pp. 363-372, 2011.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pp. 603-614, 2018a.
Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized lloyd's families. In Advances in Neural Information Prucessing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada., pp. 10674, 2018b.
data stream and communication complexity. J. Comput. Syst. Sci., 68(4):702-732, 2004. Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to
Vladimir Braverman and Rafail Ostrovsky. Recursive sketching for frequency moments. CoRR, 2010.
CAIDA. Caida internet traces 2016
passive equinix chicago. xml
Amit Chakrabarti, Khanh Do Ba, and S. Muthukrishnan. Estimating entropy and entropy norm on data streams. Internet Mathematics, 3(1):63-78, 2006.
Graham Cormode and S. Muthukrishnan. Space efficient mining of multigraph streams. In Proceed- ings of the Twenty-fourth ACM JIGACT-SIGMODD-SIEII -IGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA. pp. 271-282, 2005.
Travis Dick, Mu Li, Venkata Krishna Pillutla, Colin White, Nina Balcan, and Alexander Smola. Data driven resource allocation for distributed learning. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 22-22 April 2017, Fort Laud- erdale, FL, USA, pp. 662 671,, 2017.
Rishi Gupta and Tim Roughgarden. A PAC approach to application-specifie algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16. 2016, pp. 123-134, 2016
Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-bass based frequency estimation algorithms. In 7th International Conference Learning Representations, ICLR 2019, New Or- leans, LA, USA, May 6-9, 2019.
Piotr Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computa- tion. In Proceedings 41 Annual Symposium on Foundations of Computer Science, pp. 189-197. IEEE, 2000.
Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 202-208, 2005.
Piotr Indyk, Ali Vakilian, and Yang Yuan. abs/1910.1 13984, 2019.
Learning-hased low-rank approximations. CoRR,
T. S. Jayram and D. P. Woodruff. The data stream space complexity of cascaded norms. In 2009 50th Annual IEEE Symposium Foundations of Computer Science, pp. 765-774, Oct 2009.
10

---

Published as a conference paper at ICLR 2020
Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. In Proceedings of the Twenty-Fie eiesty-First Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pp- 1161-1178, 2010a.
Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct ele- Symposium
ments problem. In Proceedings of the Twenty-ninth ACM SEGMOD-SIGACT.A. on Principles of Database Systems, PODS '10, pp. 41-52, New York, NY, USA, 2010b. ACM.
Daniel M Kane, Jelani Nelson, Ely Porat, and David P Woodruff. Fast moment estimation in data streams optimal space. Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 745-754. ACM, 2011.
Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. CoRR, abs/1712.01108, 2017.
Ping Li. Estimators and tail bounds for dimension reduction in la (0 < a < 2) using stable ran- dom projections. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pp. 10-19, 2008.
Andrew McGregor, A Pavan, Srikanta Tirthapura, and David P Woodruff. Space-efficient estimation of statistics over sub-sampled streams, Algorithmica, 74(2):777-11,, 2016.
S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theorel- ical Computer Science, 1(2), 2005.
John Nolan. Stable distributions: models for heavy-tailed data. Birkhauser Boston, 2003.
Anna Ostlin and Rasmus Pagh. Uniform hashing in constant time and linear space. In Proceedings of the thirty-fifth annual ACM symposium Theory of computing, pp. 622-628. ACM, 2003.
Srikanta Tirthapura and David Woodruff. Rectangle-efficien aggregation in spatial data streams. In Proceedings of the st ACM SIGMOD-SIGACT-SIGAA symposium on Principles of Database Systems, pp. 283-294. ACM, 2012.
David P. Woodruff and Guang Yang. Separating k-player from t-player one-way communication, with applications to data streams. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9- 2019, Patras, Greece., pp. 97:1 17:14, 2019.
Vladimir Zolotarev. One-dimensional stable distributions, volume 65. American Mathematical Soc., 1986.

---

Published as a conference paper at ICLR 2020
A OMITTED PROOFS IN SECTION
3
Proof of Lemma / nonempty. It suffices to show that a bucket containing only light coordinates is nonempty mod- ulo p. Since the light coordinates are at most 2noly(1/0), there are most of them by assumption, their sum S is thus at most 2Po)y(1/c), This implies that S has at most poly(1/e) prime factors. If we choose a random prime p of size (oly(1/e), then S mod p # with probability at least 1 poly(e) if S * O. Taking union bound over @(c²) buckets proves the correctness. The space and time complexity are immediate from the description of the algorithm.
If a bucket contains a heavy hitter, it is marked nonempty and it is indeed
Proof of Thhorrmm 2 The proof almost identical to that in Kane et al. (20T0b). The space and time complexities are follow from the description of the algorithm.
Next we show correctness. Let Lo(j) denote the true number of distinct elements in the j-th scale. Then E La Lo/25 Let
max E (i) > }} and j*x max < E Lo (j) 2 55);
As shown in Kane et al. (2110b). if jr exists, it holds that 55 I E Lo(j < 110 and Pr(32 <
Lo(j**) 142] 2 8/9. With our choices of c 141 and 1 1/16. EXACTCOUNT returns
nonzero value for the - scale with probability 8/9 1 1/16 > 13/16 by Lemma | It follows
that the deepest scale j we find satisfies j S j S J" Hence, Lo = 21 E Lo(j") S 110 2
and Lo 2 E Lo(i") 2 2 as desired. If j does not exist, then Lo < 55, and Lo = 1 is
55-approximation this case.
B OMITTED PROOFS IN SECTION 4
Proof of Lemma 5
We let Y = pp' = p Stlal", where fi = if i was chosen, and fo =
otherwise. So we have that B[ʃi] 1
p'
It thus follows that B[ = ||ا| [pp, that is, Y is an unbiased estimate. Then,
- - p²
E
ft
2p
Σ
SiLs (co (1
||/01 12p
it1
- p²
E
filzz
2P1
+
Σ
/
1
- 11=01
2p
JEIz
|
To bound this, we notice that we have the fact that xi <
and p >> 2, so
|
p Σ
82 8 -1
l
29.
ps
kETz
So finally we have that Var
< - - pp
Proof of Lemma 6 By Chebyshev's inequality, we have that
pca
|
Pr Pr - ||=|||| > <||=|1
ks
|
2p
Proof of Theorem 7 For the heavy hitters, note that |H S n/s Vτ. For this part, we can use ()(V)) space to get an H for which H - -1 [|:] < <|| | with probability at least g by independently running 9 estimators and then taking the median.
?
For the light elements, for every sub-sample round i, we independently run 0(1) estimators with rate /nce 2 and use their median Z, be the estimate of this level of sub-sampling. Let Y, be the
12

---

Published as a conference paper at ICLR 2020
true Fg --moment of this sub- sub-sample. Then with probability least 99 it holds that |Y; - Z,1 S cY₁ Taking union bound, get that if we do the sub-sampling 10 times, with probability least 9 IY= Zil S i. I| holds for every Using Lemma 6 we can get that with probability least 9 10*
I - | S E و 1 + E |> The overall success probability of this part is at least 5.
So we get that H + - ||=||p1| S e|| + ||=|| + +ellar w l = 2e||=]1 with success probability at
least 8/5. The total space complexity is B(vn) + (
v = O "n 2 log(n) (M))
Proof of Theorem & For an element z; which the oracle indicates as light, we know that with prob- ability 6, it is truly light. Combined with Theorem 5 obtain that
Var[Y] $ p(1 8)
Σ
2p
Ira 2p S (1
11 + po1|=11?
iET
Hence, when 8 = 0 )2)) Theorem continues to hold. Otherwise we can let s = nó and
22811 and the space complexity becomes 0(c=((n))"= log(n) log(M)) bits.
Lower Bound The upper bound in Theorem 7 is asymptotically tight in up logarithmic fac- tors, since we have the following matching lower bound even in the presence of an oracle which indicates whether |a;|
Já 1=1
Theorem 9. Suppose that <<< and that a heavy hitter oracle indicates whether |xa > vn [ for the whole underlying vector Any randomized streaming algorithm that estimates | with a factor (1 (1 with probability 2 29/10 requires (/ce2//p//211/ bits of space.
Proof of Theorem 9 We assume v be an integer and define our hard instance follows: for every 1 < vn, let x 1 with probability 1 1-1/vT, and x; (46)2/Pn,/22 with probability 1/vn. And for i vn, 22 = I; mod vi- In this case, ||>|| 2 n, so any coordinate will not be heavy hitter. We note that if our algorithm can outputs an (1 + approximation of ||>]]] it can also output an (1 + approximation of |ل||||||
To prove our lower bound, we will use the 6 communication problem in Yossef et al. (2004): there are two parties, Alice and Bob, holding vectors o, E 2" respectively, and their goal is to decide if lla - bll xo < 1 or ||a blloo 2 k. From Bar- Yossef et al. (2004). we can get 12 k²)) bits lower bound.
Now claim that: if we set Vn, k (on and make - b -[ then any streaming algorithm outputs (1 (1 approximation Y of || || can be used to build commu- nication protocol for solving this 6 problem with communication proportional to the algorithm's space complexity. In this case, if ||e blloc 1, then we have Y s (1+ (1+e)llzpall ll (1 + e). e)/n
Otherwise, 2 () 1 + 4e
By this reduction, under the oracle assumption.
finally get an A(m/k2) 2/c-2//01/2-1/09 bits space lower bound
C FAST MOMENT ESTIMATION, 0 < <p< <
When 0 < p < 2, the FG estimation problem can be done in optimal O2 (lg-2log n) bits of space. Here we show how to improve the update time while maintaining this amount of space.
In the rest of the section, we assume there are two oracles: one can tell us whether |æ,|² > e² ||
and the other can tell us whether |r,|" > elements heavy elements, medium elements, and light elements. Let I IM, In C [n]] denote the subset of indices of the heavy elements, medium elements, and the light elements, respectively.
(og"(1/e) log log(1/e) ||=||.. We call these 3 categories of
2²
For the heavy elements, we can use O(e 2 log(M)) space to store them. We now turn to the other two parts. For the light elements, will use the LightEstimator in Section in Kane et al. (001
13

---

Published as a conference paper at ICLR 2020
Lemma 10 (Kane et al. (2011 Suppose we are given O < < 1, and given list L S [n] such 2 é |= There is an algorithm LightEstimator which returns an estimate X to | such that XX - -| I =|| with probability at least 0.9. The spuce usage is O log((em (nmM)), the amortized update time is (1oe)(1/)) log log(1/))), and the reporting time is (11ee).
that E L if and only if 1
For the light elements 2,, note we have the condition |aa| I (1 / log log(1/
1 Using Lemma [ Lemma and the argument in Theorem 7 if we use the LightEstimator to do the sub- sampling algorithm with rate p (1g/(1/c) log (og((/)) for the light elements, we just need to sub-sample ((1) times to get approximation X of ||2 [IB such that |X || 1 S e|| l with probability at least 0.9. Note that for each update (i, v) in the sub-sampling process, if x; is not se- lected by the sub-sampling algorithm, the update time O(1) (we do not need to do anything), oth- erwise, by Kane et al. (201 we know that the amortized update time is (log" (1/e) log (L/))) Notice that in Lemma 5 we just need a pairwise independent hash function for the sub-sampling. So during the process, the expected amortized update time is O log (1/e) log log(1/e) 0().
Theorem 11. Suppose we are given 0 < < <<> 1, and given the lists It. There is an algorithm which returns an estimate X to || such that |X || S <||=|| with probability at least 0.9. The space usage is O(E-2log(( (o) the expected amortized update time is O()), and the reporting time is (-1/(2)-
It remains to handle the medium elements. Here we will still use the LightEstimator, but do some adjustments. Before describing our LightEstimator data structure, we first define the p-stable dis- tribution.
Definition 1 (Zolotarev Zolotarev 1986)) ). For 0 < < 2, there exists a probability distribution
Dp called the p-stable distribution satisfying the following property. For any positive integer n and vector I E RR,, if 1I.... Zn ~ D, are independent, then fn
Z, ~ ||=|| 2 for Z ~ D,-
Lemma 12 (Pagh and Pagh. Ostlin & Pagh| (2003) Theorem 1.1). Let S C = [u] be set of
2 > 1 elements, and let V = [b) with I < S u. Suppose the machine word size is (llo((u)). For any constant e > O there is a word RAM algorithm that, using time log(=) log (0)()))) (v) and Ollg(()) + log log(u)) bits of space, selects a family H of functions from U V (independent of S) such that:
1. With probability 1 - (11/2)), H is z-wise independent when restricted to S.
2. Any h E H can be represented by a RAM data structure using O(2 O(=log(v) (og(v)) bits of space, and h can be evaluated in constant time after an initialization step taking ((2) time.
In Kane et al. 20111. LightEstimator was defined by creating R- = 4/e² independent instantiations of the estimator Dj. which we label D!.... DR. and picking a hash function h [m] - [R] using
Lemma 12 Upon receiving an update to z; in the stream, the update was fed to D The estimator Dj is a slightly modified version of the geometric mean estimator of Li (2008). which takes matrix A E Rtx", where each row contains ( /eis-ise p-stable entries and the rows being independent
from each other, and maintains y = Ax in the stream. Furthermore, in parallel we run the algorithm of Kane et al. 2010aa) with constant error parameter to obtain a value Fp in [|| | 3||=||/ The estimator Est, is min(Cre, (IT) ly, (it)). F//e/. Hence in Kane et al.
2011 the update time the time to evaluate ((1/e")-wiss independent hash function over a field of size poly(nm.M), which is (log"(11 (1/e) log log(1/e)) Therefore, if we can store the hash values of the p-stable entries for the medium elements, then we can improve the update time to O(1) for this part (note that the parameter is a constant). We need the following lemma.
Lemma 13. Let l = O log² ! log log !) and X1, X2,.., X2 be p-stable random variables. With probability at least 0.9, the following holds. There exists T' C [K] such that |T'] O(1/e) for which [X, S poly log(1/e))fo for all T, and consequently, each such X; can be approximated by some X, satisffing Xx, - X,I < poly(e) and each such X, can be recovered from ({lo((1/e) bits.
To prove this, we need the following result.
14

---

the amortized update time is Published as a conference paper at ICLR 2020
Lemma 14 (Nolan (200)). Theorem 1.12). For fixed 0 < < 2, the probability density function
6p of the p- p-stable distribution satisfies 0p(x) = ((1 + +z(p+)) and is an even function. The cummlattiv distribution function satisfies px(x)) = 0([x) P).
Let I = [- log 3/p (1/e), log 3/p (1/ee). For a p-stable random variable X; by Lemma Pr X; & 1} = O log" (1/e)). So the expected number of X; for which X; & is Ok/ log (1/e)) )= = 0(//²). By Markov's inequality, with probability at least 0.9, the number of these X; are O For X; contained in I, we can uniformly partition into subintervals of length poly(e), and there will be O(poly(1/e)) many subintervals. Let X, be the nearest partition point. It is clear that X; can be recovered from ([log(1/e) bits to store the index of the partition point.
Proof of Lemma
13
The following lemma tells that we can use the approximation value given by the p-stable random variables in the Est,
Lemma 15. Let k O log" 1 loglog 2) Suppose we are given a, b, E R and la; - bal S ca for all i. Then we have Ka a) (b, I 10= for sufficiently small e.
Proof. By the e5 (0-11 S 1 (recall that p < 2).
Schwarz inequality. la - b,x)l I Iaa -1122/1/12 I vkeat
Finally, we have the following theorem.
Theorem 16. Suppose we are given 0 < E < and the lists IM- There is an algorithm which returns an estimate X to || Ip, such that |X || llg I 2e||=]] with probability at least 0.8.
The space usage is O(e max max(log(mmm))) (og(nm))),og (og" log log(1/e))), O(1), and the reporting time is (()/c2).
1 log" log log! 1. Note that there are at most io medium elements. Using Lemma 12 we pick two hash functions h [n] + [k], h2 [n] - [1/e]], and we can assume with high probability, they perfectly hash our input set of items. Lemma 13 tells us with probability at least 0.9, we can use these two hash functions and use 0(1) time to read the p-stable random variables for the medium elements (if X; E I, we store X; in the cell which fn (i) refers to, using (log([/))) bits. Otherwise we store X; in the cell which h2 (i) refers to, using (log((M) bits).
Proof. Let
Suppose that d(x) is the pdf of the p-stable distribution. For a p-stable Y, we have that P c)) S ((r)dr= I (0) = poly(c) when g is sufficiently large. Hence, in Lemma 13 and Lemma 15 we can pick a sufficiently large such that with probability at least 1 - (- ). all of the true values y4 output by the Est, are least e" [||==[p. and the ÿ output by the Est, using the stored p-stable random variables satisfy 18; el S e++ [| p. So the approximation from the p-stable random variables will affect our estimate by at most el e||x] This completes the proof.
Using Theorem II and 16 we will have our result:
Theorem 17. Let 0 < p < 2 and 0 < 1/2. There exists randomized algorithm which outputs (1 + 1 with probability at least 0.7 using O(c max(log(nm.M)) log" (1/c) log log(1/c)))
bits of space. The expected amortized update time O(1). The reporting time is ((1/e))
In the case of noisy oracle, we assume that for fixed 8, our oracle will not identify more than (s)) items as heavy hitters (meaning that [a;] > ]| [|))) Then we can adapt the preceding theorem to the noisy oracle version.
Theorem 18. Let < < and 0 E < 1/2. Suppose that the heavy hitter oracle errs with probability 5 = O loge(1/e) log lo There exists an algorithm which outputs (1 + 3e) 3<)]B with probability at least 0.7 using ( max(log(mm)) (nmM), log² (1/e) log log(1/e))) bits of space. The expected amortized update time is 0(1). The reporting time e
15

---

Published as a conference paper at ICLR 2020
Proof. We only need to consider the difference in the estimation of | When 5 O (nge(1 log lng(T/e)) note that our sub-sampling rate is (1/c( log (1/()/)). follows from Theorem 8 that Theorem continues to hold.
D CASCADED NORMS
For notational simplicity, we consider approximating (z)) = Ei= E Biy P) with k 1 and p 2 2. The cascaded norm || then satisfies || = (F/)(F,(z)) for k p 2.
We follow the algorithm in Jayram & Woodruff (2009), which first downsamples the rows in log n levels, and then samples in each level Q = O( 1 1yk entries from the row-sampled submatrix proportional |z,/", and at last estimates the (F,) cascaded norm from those samples. The first step of l fp-sampling is further decomposed into two steps: (i) dividing the entries into layers by their magnitudes and uniformly sampling sufficiently large of entries in each layer, and (ii) performing "L, "y-sammlingg from those samples, We shall improve the space complexity of Step (i) with a heavy hitter oracle.
We first elaborate how Step (i) was done. It splits the entries in the row-sampled matrix X into layers, where the t-th layer Sx( consists of entries in [<n)=11 [nn'). A layer t is said be con- tributing if [s((X)(((n")) 2 Fp(X)/(BO). It needs to return Bt = (X) (X)) samples from each contributing layer t. Suppose that |S,(X)//2) < 8t < (x)()) for some j. and the algorithm subsamples each entry with probability 1/22, obtaining a subset Y; of entries. It can be shown that with high probability, for a contributing layer t, it holds that |0/0////////00-///////0 log X1). and therefore the standard COUNT-SKETCH algorithm recover all those entries with ((Q2/P|X|" x11-2/P) space.
(2i)²)² 2
2|1-
Consider the top level without subsampling of the rows. Suppose that the heavy hitter oracle de- termines whether |2,|" 2 ||=||//T for each entry xy of the matrix with some threshold T. In the algorithm of Step (i), without loss of generality, we can assume each layer contains either light layer cordingly. If a light layer is contributing, since each entry is at most Fp/T, there must exist at least N₂ (X), ( ((T))))PHP))))) //E, entries that level. We would require that N, > B,, for which it suffices to have T (2())). We can downsample the layer at rate 0Q/T,, and then apply the preceding algorithm and thus the number of buckets can be reduced by factor of T/ T/(Q)). Note that the heavy layers come from the at most T heavy hitters. This leads to space complexity of Ö(Q2/PT1-24 2/p | 2/1p/ ((Q)) Let T (() In this case, T = ((0Q) is satisfied and the space complexity is 0(0112+2//1////2-1111)
heavy entries only light entries only, and call the layer heavy layer
For the j-th level of row sampling, note that the same (global) heavy hitter oracle, when applied to this row-subsampled matrix, effectively has T replaced with T/2'. However, |X] is also replaced with |x2/22, and thus we would require 7' = ?((20QQ) and we can downsample the layer at rate 240Q/T. This means that the space complexity is (2 5)= 1-2/9 fraction of the space of the top level.
The constraint of T ((220Q) allows for < 1 log Q
[X] For j 1/2 log &
|X| can just the
old algorithm with space
Plugging in Q ((nk-1/k) and | nd and noting that the space of the subsequent steps dominated by this very first sampling step, we have:
Theorem 19. Let > and k 2 L,p 2 be constants. There exists a randomized algorithm which receives x d matrix x and outputs (1 a)approxxmmation to (x)(F(x))) with probability at space.
least 2/3 using Ö(n² + to + -+
Replacing with k/p, we obtain our final result for cascaded norms.
Corollary 20. Let E > 0 and p 2 be constants. There exists randomized algorithm which receives an n x d matrix x in stream of additions and deletions to its coordinates, and outputs (1 e)aapproxination to | with probability at least 2/3 using Ö(n M/n-- -/2 t d - space.
16

---

to recover a list of the Published as a conference paper at ICLR 2020
E RECTANGULAR P,
The rectangle-efficient algorithm in Tirthapura & Woodrufi (2012) is based on the F, moment es- timation algorithm Braverman Ostrovsky (2010). In Braverman & Ostrovsky (2010), they first subsample to obtain the substream D, G 0, 2,,,2,.. logn), n), where Do is the full stream, and if i Dy, then i Dj+1 with probability 1/2. For every substream D,, they run the COUNT-SKETCH algorithm to recover all (a /nn -heavy hitters, whence they can obtain a good final estimate.
The algorithm in (Tithhaurra Woodruff (2012) is similar. Instead of updating the counter in each coordinate inside a rectangle, they developed a rectangle-efficiett data structure called RECT- ANGLECCUNTSSEECHH We follow their notation that (*)) denotes a function of the form f /pooy(1//e, /e, d, log(m&/6)).
Lemma 21 (RECTANGLECOUNTSKETO) BECTANGLLCCOUNTSSKECCHYYY can be updated rectangle -fticieett time (' -). The total space is On (x-2) words. The data structure can be used to answer any query E GF(A),, return- ing a number ((1) with (i) xzl S 7|/2]122 The algorithm succeeds on all queries simultaneously
Tirthapura & Woodruff (0122). The data structure
with probability 1 1
they subsample the items into a logarith- mie number & d log () of levels. In particular, for j [o]. i Dj if g(i) A2/2/-1. In each level, they give an algorithm which invokes RECTANGGECCONNTSSETCHHY
Under an arbitrary mapping g GF(A)" - - 21, A}.
F, heavy hitters. Then they use the heavy hitters from each layer to calculate the final estimate.
Lemma 22 (Tirthapura & Woodruff (2012)) For p. > 2, there is an algorithm which uses with y O o / and with probability at least 1 - 5 outputs a set P of (11/a) pairs (i, xd) such that E(sgeerla ||?!| | P| I e||==| and all elements with |x,|P 2 a appear as the first element of some pair in P. The algorithm uses 27 words of space.
RECHANGLICOUNNSAATCCCC)
Since the algorithm relies on a subroutine that finds the fp-heavy hitters, the improvement with a heavy hitter oracle is similar to that for the mo-moment problem. Specifically, suppose the heavy hitter oracle is able to indicate whether [r; 44/a use rectangle-efficient estimator for the substream which contains all the heavy items, while for the light items, we can use the subsampling algorithm with rate A d/2 Note that for each substream, have ||o||oo < 4//2 (for those i's that inequality, it holds that ||æ||| S Ad/1-d/(2p) ||>]|p-- Following the proof of Lemma 22 we can set ( + aF (4/4-d/(2p)) to find those heavy hitters. We thus have the following theorem.
1 ||=/| We know from Theorem 7 that we can
in the substream, see I; 0), so by Hölder's
Theorem 23. Under the assumption of a heavy hitter oracle, there is a rectangle-efficien single- pass streaming algorithm which outputs (1 + e) -approxximation to | with probability ô for
p > 2. It uses O" (Ad(1/211/)) bits of space and O" (Ad(1/2-1/p)) time to process each rectangle in the stream.
17


Reviews:
[{"review_id": "Sye1Z22R5B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents algorithms for solving computational problems in a datastream model augmented with an oracle learned from data. The authors show that under this model, there exist algorithms that have significantly better time and space complexity than the current best known algorithms that do not use an oracle. The authors support their theoretical analysis with experiments in which the oracle is represented by a deep neural network and demonstrate improvement over classical algorithms that do not use machine learning.\n\nOverall, this paper seems like a solid contribution to the literature. However, in its current state it does seem to be presented and motivated in a way that is appropriate for the audience of ML researchers at ICLR. It reads very much like a STOC theory paper, and a lot of the key ML details that would be relevant to audience at this conference seem to have been shoved under the rug in a way. Therefore my score for now is a weak reject, but I am very happy to increase the score if the authors address my presentations concerns.\n\nMajor comments:\n* The oracle-augmented datasteam model needs to be contextualized better. I don't have a good sense of whether this is a reasonable theoretical model to explore and a lot of very basic questions remain unanswered for me. For example, how do I even know that the oracle in question exists? What are the particular assumptions under which it exists? What are the requirements on the training data, optimization ability, generalization error, etc. How do we know that we can create in practice ML learning models that are sufficiently accurate to serve as an oracle?\n\n* The connections to deep learning seem arbitrary in some of the experiments. In one of the experiments, the authors train neural networks over a concatenation of IP address embeddings. Why do we need to use deep learning here? What is the benefit of using DL algorithms within the oracle-augmented datastream model? Is a simple algorithm enough? What algorithms should we ideally use in practice? What if you used simpler online learning algorithms with formal accuracy guarantees?\n\nMinor comments:\n* I thought there was a bit over-selling in intro. The authors say that they match the theoretical lower bounds for several problems. However, you are in a different computational model in which you now have access to an oracle. This needs to be made more explicitly, and language could be a bit toned down (e.g. in this model, we can obtain runtime that match or improve over lower bounds...)", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HJxwv99GqS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Algorithms for Streaming data using a machine learning oracle is analyzed theoretically and empirically.\n\nThe idea is to build on some recent work (Hsu 19) which used RNNs to predict heavy hitters in streaming data. The purpose of this paper is to analyze whether such an oracle can help streaming algorithms to obtain improved bounds. I am not very familiar with this line of research so my comments will be more general in this case. The idea of improved bounds for streaming algorithms using machine learning oracle seems to be very appealing to me. The authors present novel theoretical results supporting this.\n\nExperiments are performed on real as well as synthetic datasets using Hsu et al.’s method as an oracle.  Two real-world problems are selected, i.e., distinct packets in a network flow, Number of occurrences of each type of search query, and it is shown that using a oracle improves performance as compared to methods that do not use the oracle. Overall, I think the paper seems to be  an interesting direction which has both formal guarantees and experiments validating them in real-world datasets. One issue is perhaps, very little in terms of related work. I am not sure if this is the first work in this direction of proving bounds assuming an oracle or if there is some background work that the authors could provide to put this into context.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJloMuTnFr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper talks about calculating various statistics over data streams. This is a very popular topic and is very relevant in big data analysis. A lot of work has been done in this general area and on the problems that are discussed in the paper. The new idea in the paper is better streaming algorithms under the assumption that there is a “heavy hitters” oracle that returns data items that have a lot of representation in the stream. The authors give provably better algorithms for the distinct elements problem, F_p moment problem (p > 2), and some more problems. These are important problems in streaming data analysis. They improve the space bounds and interestingly in some cases the bounds are better than what is possible without the oracle assumption. This also shows the power of such an oracle. There are experimental results to demonstrate the efficiency of the algorithms. At a high level the work seems good and interesting for a large audience interested in streaming data analysis. I have not gone over the proofs in detail (much of which is in the appendix).\n\n- Even though oracle results are interesting, to make it practical it may make sense to talk about a more realistic, weaker oracle where some of the queries may be incorrect.\n- It may even make sense to minimise the number of oracle calls which can be thought of as a resource and discuss the relationship between number of oracle calls and other resources such as space.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper theoretically analyzes the use of an oracle to predict various quantities in data stream models.  Building upon Hsu et al., (2019), the overriding goal is to examine the degree to which such an oracle is can provide memory and time improvements across broad streaming regimes.  In doing so, optimal bounds are derived in conjunction with a heavy hitter oracle.

Although the rebuttal and discussion period did not lead to a consensus in the scoring of this paper, two reviewers were highly supportive.  However, the primary criticism from the lone dissenting reviewer was based on the high-level presentation and motivation, and in particular, the impression that the paper read more like a STOC theory paper.  In this regard though, my belief is that the authors can easily tailor a revision to increase the accessibility to a wider ICLR audience.
Decision: Accept (Poster)