Learning-Augmented Moment Estimation on Time-Decay Models
Authors: Soham Deepak Nagawanshi
Shalini Panthangi
Chen Wang
David Woodruff
Samson Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: learning-augmented algorithms
time decay
sliding window model
moment estimation
Primary area: learning theory

Abstract: Motivated by the prevalence and success of machine learning, a line of recent work has studied learning-augmented algorithms in the streaming model. These results have shown that for natural and practical oracles implemented with machine learning models, we can obtain streaming algorithms with improved space efficiency that are otherwise provably impossible. On the other hand, our understanding is much more limited for the sliding window model, which captures applications where either recent data leads to better or older data must be expunged from the dataset, e.g., by privacy regulation laws. In this paper, we utilize an oracle for the heavy-hitters of datasets to give learning-augmented algorithms for a number of fundamental problems in the sliding window model, such as norm/moment estimation, frequency estimation, cascaded norms, and rectangular moment estimation. We complement our theoretical results with a number of empirical evaluations that demonstrate the practical efficiency of our algorithms on real and synthetic datasets.

Published as a conference paper at ICLR 2026
HEARNING-AUGMENTER MOMENT ESTIMATION ON -EEAYY MODELS
Soham Nagawanshi"
Shalini Panthangi
Chen Wang
David P. Woodruff
Samson Zhou' !
ABSTRACT
Motivated by the prevalence and success of machine learning, line of recent work has studied pormiing-uumenner algorithms in the streaming model. These results have shown that for natural and practical oracles implemented with machine learn- ing models, we can obtain streaming algorithms with improved space efficiency that are otherwise provably impossible. On the other hand, our understanding is much more limited when items are weighted unequally, for example, in the sliding-window model, where older data must be expunged from the dataset, e.g., by privacy regulation laws. In this paper, we utilize an oracle for the heavy-hitters of datasets to give auggmettd algorithms for number of fundamental problems, such as norm/moment estimation, frequency estimation, cascaded norms, and rectangular moment estimation, in the time-decay setting. We complement our theoretical results with number of empirical evaluations that demonstrate the practical efficiency of our algorithms on real and synthetic datasets.
INTRODUCTION
The streaming model of computation is one of the most fundamental models in online learning and large-scale learning algorithms. In this model, we consider an underlying frequency vector x E R", which is initialized to the zero vector 0". The data arrives sequentially as stream of m updates, where each update at time E [m]] is denoted by (t, ot). Each o, modifies a coordinate x; of the frequency vector for some E [ni] by either increasing or decreasing its value. The goal is usually to compute a function f(x) of this underlying frequency vector using memory substantially smaller than the input dataset size. The data stream model has widespread applications in traffic monitoring (Chen et al., 2021), 1), sensor networks (Gama & Gaber, 2007), data mining (Gaber et al., 2005; Alothali al., 2019), and video analysis (Xu et al., 2012), to name a few. The research on data streams enjoys a rich history starting with the seminal work of Alon et al. (1999). Some of the most well-studied problems in the data stream model are often related to frequency (moment) estimation, i.e., given the frequency vector x, compute the Fp frequency ||x|3" E |x,|". A long line of work has thoroughly explored streaming algorithms related to frequency estimation and their limitations (see, e.g., Alon al. (1999); Chakrabarti al. (2003); Bar- Yossef et al. (2004); Charikar et al. (2004); Woodruff (2004); Cormode & Muthukrishnan (2005); Indyk & Woodruff (2005); Li (2008); Andoni al. (201 1); Kane et (201 1); Braverman & Ostrovsky (2013); Braverman et al. (2014; 201 2018b); Woodruff & Zhou 10));;;); Indyk et al. (2022); Braverman et al. (2024a) and references therein).
For p > 2, the celebrated count-sketch framework (Charikar et al., 2004; Indyk & Woodruff, 2005) can be used to achieve streaming algorithms that compute (1 approoitiiiiiiioo of the F, frequency moment in Ö( 2/pp poly(e)) space (Charikar al., 2004; Indyk & Woodruff, 2005; Andoni et al., 2011). The bound has since been proved tight up to polylogarithmic factors (Chakrabarti
"Texas A&M University. E-mail: adsohame gma com.
Carnegie Mellon University. E-mail: shalinipanthang 04 040 40gmail com.
$ Rensselaer Polytechnic Institute. E-mail: chon. wang research@gaall. com.
8 Carnegie Mellon University and Google Research. E-mail: dwoodrufscs cma, edu.
Texas A&M University. E-mail: samsonzhoue gmaai con.
' Throughout, use Ō(-) and (2-)) hide polylogarithmic terms unless specified otherwise.

---

Published as a conference paper at ICLR 2026
et al., 2003; Bar- Yossef al., 2004; Woodruff, 2004; Woodruff & Zhou, 2021b; Braverman et al., 2024a). As such, for very large p. any streaming algorithm would essentially need Q(()) space. The conceptual message is quite pessimistic, and we would naturally wonder whether some beyond-worst case analysis could be considered to overcome the space lower bound.
algorithms. Learning-augmentedd algorithms have become a popular frame- work to circumvent worst-case algorithmic hardness barriers. These algorithms leverage the predictive power of modern machine learning models to obtain some additional "hints".
searning-augmeenn
algorithms have been applied to problems such as frequency estimation (Hsu et al., 2019; Jiang et al., 2020; Chen et al., 2022; Aamand et al., 2025), metric clustering (Ergun et al., 2022; Huang et al., 2025), graph algorithms (Braverman et al., 2024b; Cohen-Addad et al., 2024; Dong et al., 2025; Braverman et al., 2025), and data structure problems (Lin et al., 2022; Fu et al., 2025). Notably, Jiang al. (2020) showed that for the F', frequency moment problem with p > 2, with the presence of a natural and practical heavy-hitter oracle, we can obtain (1 + -aaapooxiimttoon algorithms with oracle.
0(n1/221/p/ p/lyyyy) space space bound impossible without the Searning-augmeet Jiang et al. (2020) also obtained improved space bounds for related problems such as the rectangle F, frequency moments and cascaded norms, highlighting the effectiveness of sarning-augmentee
oracles.
Time-decay streams. The results in Jiang al. (2020) and related work (Hsu et al., 2019; Chen et al., oracles
2022: Aamand et al., 2025) gave very promising messages for using in streaming frequency estimation. On the other hand, almost all of these results only focus on estimating the frequencies of the entire stream. As such, they do not account for the recency effect of data streams. In practice, recent updates of the data stream are usually more relevant, and older updates might be considered less important and even invalid. For instance, due to popularity trends, recent songs and movies usually carry more weight on entertainment platforms. Another example of the recency effect is privacy concerns. To protect user privacy, the General Data Protection Regulation (GDPR) of the European Union mandates user data to be deleted after the "necessary" duration (GDPR16). Furthermore, some internet companies, like Apple Inc. (2021), Facebook (2021). Google LLC (2025), and OpenAl (2024) have their own policies on how long user data can be retained.
The dime-decay framework in the stream model is great candidate that captures the recency effeect. In this model, apart from the data stream, we are additionally given a function w supported on [o, 1] that maps the importance of the stream updates in the past. In particular, at each time step t, we will apply w on a previous time step L' < to potentially discount the contribution of the previous update, i.e., w(() < w1) for 7 > 1 2 Our goal is to compute a function (e.g.. F7)) of the frequencies with the weighted stream after the update at the I-th time for / E [m]. In general, algorithms for standard data streams do not directly imply algorithms in the time-decay model. Therefore, it is an interesting direction to ask whether the learning aannnngted heavy-hitter oracle could be similarly helpful for frequency estimation in time-decay models.
Typical time-decay models include the polynomial decay model (Kopelowitz & Porat, 2005; Cormode et al., 2007; 2009; Braverman et al., 2019), where the importance of the updates decays at a rate of 1/r* for some fixed constant 8, and the exponential decay model (Cohen & Strauss, 2003; Cormode et al., 2008; 2009; Braverman et al., 2019), where the decay is much faster as a function of 1/s" for some fixed constant The study of frequency estimation often appears in conjunction with the time decay model. In addition to the space bound studied by, e.g., Kopelowitz & Porat (2005); Braverman et al. (2019), several papers have approached the problem from the practical perspective (Xiao et al., 2022; Pulimeno et al., 2021). However, to the best of our knowledge, the general time-decay streaming model has not been well studied in the learning-auge -aummented setting.
A notable special case for the time-decay framework is the diding-window stream model (Datar al., 2002; Lee & Ting, 2006a;b; Braverman & Ostrovsky, 2007; Crouch et al., 2013; Braverman et al., 2015; 2016; 2021; 201 Sa; 2020; Woodruff & Zhou, 2021a; Borassi et al., 2020; Epasto et al., 2022; Jayaram et al., 2022; Blocki et al., 2023; Woodruff & Yasuda, 2023; Woodruff et al., 2023; Cohen-Addal et al., 2025; Braverman et al., 2026). Here, we are given a window size W, and the time-decay function becomes binary: wn(t)) = 1 if t' is within a size-W W window (i.e., t' > t W + 1), and w(t') 0 otherwise. For this special application, Shahout et al. (2024) studied the learning-
Here, step t' uses wo(t t' + 1) as the input. In this way, vr could be defined as a non-increasing function, ie.. w(t t + 1) = w(1).
2

---

Published as a conference paper at ICLR 2026
augmented Window Compact Space-Saving (WCSS) algorithm in Hliding-window streams. Although a pioneering work with competitive empirical performances, the WCSS algorithm in Shahout et al. (2024) suffers from two issues: i). it does not give any formal guarantees on the space complexity; and it). for technical reasons, the paper deviates from the heavy-hitter oracle as in Jiang et al. (2020), and instead used "next occurrence" oracle that is less natural and arguably harder to implement. Specifically, the hard instances in existing lower bounds for streaming algorithms involve identifying Ly heavy-hitters and approximating their contributions to the F', moment (Woodruff & Zhou, 2021b). Since the "next occurrence" oracle of Shahout et al. (2024) does not perform this task, it is unclear how their approach could be used to improve standard streaming and sketching techniques. Furthermore, it is unclear how their algorithm could be extended to the general time-decay models as we study in the paper. As such, getting results for general time-decay algorithms would imply improved results for the sliding-windov model, which renders the open problem more appealing.
Our results. In this paper, we answer the open question in the affirmative by devising near-optimal algorithms in the time-decay model (resp. the sliding-window model) for the H' frequency estimation problem and related problems. Our main results can be summarized as follows (all of the bounds apply to polynomial decay, exponential decay, and the sliding-window window settings).
Fp frequency: We give a learning augmented algorithm that given the heavy- oracle and the frequency vector x in the stream, computes a (1 + a)aaproxxiottion of the F3 frequency
||x||² Ei= |x1 in ((" 1//2-1//
c+tt .p' +2) space.
Rectangle Fg frequency: When the universe is [A]" and stream elements update all coordinates in hyperrectangles, the F,. frequency moment problem for the stream is called rectangle Fp frequency. We give a learning-augmented algorithm that computes a (1 + ->aappoxxiittonnnn of the rectangle F, frequency in Ö - 1/p)
gx poly( (2e space with heavy-hitter oracles.
(k: ccscaaded norm: As a generalization of the F3 frequency moment problem, when the frequency data is given as an n x d matrix X and the stream updates each coordinate Xij- we define f(X) (Ei (E)= |X,, ll/)/////
the (kt, pcascadde norm (k-norm of algorithm that computes (1 + e)-
the p-norms of the rows). We give a approximation of the (k: (t.p))caccceed norm in space Öz. (n fh. dd )) We use (. (-) to hide polynomial terms of (kp)*P, ,,, e, and logn." n.
By a lower bound in Jiang et al. (2020), any augmente streaming algorithm that obtains a (1 + approximaaiio for the Fp moment would require 1/21// / space. Since the streaming setting can be viewed as a special case for the time-decay model, our algorithm for Fp frequency is optimal with respect to the exponent n.
Our techniques. Our approach is fundamentally different from previous work in -arnuinng--mmeeteedd sliding-windee window algorithms, e.g., Shahout et al. (2024). In particular, we considered an approach that directly transforms streaming algorithms into time-decay algorithms. Crucially, we observe that many approaches in the time-decay streaming literature are based on smoothness of functions (e.g., Braverman & Ostrovsky (2007); Braverman et al. (2019)). Roughly speaking, these approaches follow a framework to maintain multiple copies of the streaming algorithm on different suffixes, and delete the copies that are considered "outdated".. The correctness of time-decay streams could follow if the function satisfies some "smoothness" properties. We derived several white-box adaptations of the algorithms under this framework. We show that as long as the geariing-augmente suffix-compatinn
oracle is i.e., it is able to predict the heavy hitters of suffix streams [t. m) as well, the -anmenn-d setting in the same way as the setting without the
framework would work in the oracle. As such, we could apply the streaming augmine- algorithm in Jiang et al. (2020) to obtain the desired time-decay algorithms.
We remark that another valid option would be to generalize the difference estimator framework of Woodruff & Zhou (2021a) to incorporate advice. Although this approach gives better dependencies in E, the overall algorithm is quite involved and not as easily amenable to implementation, which in some sense is the entire reason incorporate machine learning advice in the first place. We thus focus on practical implementations with provable theoretical guarantees.
For the polynomial and exponential models, the computation of the (k, p)-cacaaded norm requires row arrival. For the sliding-window window streams, the updates can be the points.
3

---

Published as a conference paper at ICLR 2026
Task
Space Bound
Model
Remark
0(12/2-1/2/64) 0(1)/2-1///22fp)
Streaming
Jiang et al. (2020)
Fp Frequency
Any
Lower bound, Jiang et al. (2020)
(p > 2)
not specified
Sliding Window
Shahout et al. (2024)
Ó(112-11/8 ppto///4t))
General Time-decay
This work, Theorem
(e.g.. Sliding Window)
Rectangle F, Frequency
0(Ad(1/2-1/p) poly(H.d)
Streaming
Jiang et al. (2020)
(/Ad1/2-1/pl.pol//
General Time-decay
This work, Theorem 5
(e.g., Sliding Window)
p)asccCddd
Ö(n'- d
Streaming
Jiang et al. (2020)
Norm
Ok.(nn - .d +)
General Time-decay
This work,
(e.g., Sliding Window)
Theorem 6
Table I:
Summary of the results and their comparisons with existing work. The theorem pointers directed to the sliding- window algorithms as an illustration.
Experiments. For the special case of fliding-windowd streams, we conduct experiments for learning- augmented Fe frequency estimation. We implement multiple suffix-coppatble heavy-hitter oracles, such as the count-sketch algorithm (Charikar et al., 2004): this allows to compute heavy hitters for different suffixes of streams with minimal space overhead. We tested the F, frequeney algorithms based on Algorithm and the implementations in Alon al. (1999) (AMS algorithm) and Indyk oracles. The datasets we tested on
& Woodruff (2005) with and without the Seaningg-uugment include a synthetic dataset sampling from binomial distributions and the real-world internet datasets of CAIDA and AOL. Our experiments show that the learning-augmencee approach significantly boost the performance the frequency estimation algorithms, and, at times, produce results extremely close to the ground-truth. Furthermore, approach is fairly robust against distribution shifts over updates, while other heuristic approaches like scaling would induce performance degradation when the distribution changes."
PRELIMINARIES
The time-decay and sliding-window models. We specify the time-decay model and related notation. We assume the underlying data x E Z to be a frequency vector, where each coordinate x; stands for the frequency of the corresponding item. The frequency vector is initialized as 0", and at each time, the vector is updated as (i, A) such that x; < X; + A, for some A > O, so that all updates can only increase the coordinates of the frequency vector. We assume in this paper without loss of generality that = 1. Let m be the total number of updates in the stream, which we assume to be upper bounded by most some polynomial in the universe size In the time-decay model, additionally given a weight function w R R200 and an update at time t e [m] contributes weight w(m vm(m-t+> (++1) 1) to the weight of coordinate E [m]. Here, w is non-increasing function with w(1) and & > is some parameter that is fixed before the data stream begins. We have w((T) = 1/7* for polynomial decay and w(T) s" for exponential decay, respectively. The underlying weighted frequency vector of the f-th time for all E [n] is defined as x Eee(t)a w(t
1).
In the special case of the sliding-window model, we are additionally given window size W. At each step E (W L, m], we define W. the frequency vector over the last W update steps. Let f: R + R be given function, and our goal is to output f(x for all t E (W - 1,m
'The codes for the experiments are available learning baarning-aan auggggtugmeneddeeee decay
4

---

Published as a conference paper at ICLR 2026
Apart from the subvectors x W which we aim to compute, also define xfiitz the vector obtained by accounting for all the updates from step 1 to tz. In particular, x l and x/1-m represent the frequency vectors with the updates from the start of the stream to t and from till the end of the stream, respectively.
The functions to compute. We aim to compute the following objective functions (defined as mappings IK" R) in the sliding-windov window streaming model.
The Fy frequency function: f(x) |x| Ix;
The rectangle Fp frequency function: this is special case for the Fp frequency problem, where we assume x E [A]" for some integer A.
Furthermore, we also study the cascaded norm function for high-dimensional frequencies, i.e., the input "frequency" is a n x d matrix X, where each row corresponds to a generalized no- tion of frequency. The (k, -cascaded norm function f Raxd + R is defined f(X) k/p) 1/k
EL (Et= (x,)") X. is given in the stream. We can define the corresponding inputs for time-decay and sliding- window models analogously.
In the streaming model, at each time t, an update on coordinate
The Beeriing-augmeneed framework. We work with where we assume an oracle that could predict whether is heavy hitter. Depending on the function f. we have multiple ways of defining heavy hitters as follows.
streaming algorithms,
Definition (Heavy-hitter oracles). We say an element x; is a heavy hitter with the following rules.
(a). If f is Fp frequency, we say that x; a heavy hitter if xx,"" > 1 v
|xx[
(b). If ff rectangle Freqqueency in [ we say that x; is heavy hitter |x;|" > ||x||/ /A//2
(c). If f is (k:, p)-caccaded norm, we say that X.5 is heavy hitter if n p/2k), where 13 is the vector norm of the vector from the elements in X.
|X,]|² > |X (d'
heavy hitter oracle O is learning- augmeented oracle that, upon querying x,, answers whether x; satisfies the heavy hitter definition. We say that O is a deterministic oracle if it always correctly predicts whether x; is heavy hitter. contrast, we say that O is a stochastic oracle with success probability 1 1 if for each coordinate x,, the oracle returns whether x; is a heavy hitter independently with probability at least 8.
For the purpose of time-decay algorithms, we also need the oracle to be suffix compatible, i.e., able to return whether x; is heavy hitter for all suffix streams [t ml. E (0, m 1]. We formally define such oracles as follows.
Definition SSuffix-compatibel heavy-hitter oracles). We say a heavy hitter oracle O is a determin- istic (resp. randomized) suffx-coopaatie learning-auge augmented oracle if for each suffix of stream m] for E (0, m 1] and each frequency vector x(t m), O is able answer whether x(t m); is a heavy hitter (resp. with probability at least 1 5).
Additional discussions about suffix-coppatibe heavy-hitter oracles. Learning-augmented algo- rithms with heavy-hitter oracles were explored by Jiang et al. (2020). Our setting is consistent with theirs, and similar to Jiang et al. (2020), such oracles are easy to implement for practical purposes. In Appendix D. we provide general framework for the learning of such oracles.
We note that Shahout et al. (2024) discussed certain difficulties for using bloom filters to obtain predictions for every window. We emphasize that the suffix-con confiiiicomaiiiiliity property does not require the prediction for every window, but rather only the suffixes of the streams (only m - W + such windows). This is a much more relaxed setting than the issues discussed in Shahout et al. (2024). Furthermore, our experiments
Section show that the suffix-compatible oracles can be easily learned via small part of the streaming updates.
3 ALGORITHM AND ANALYSIS FOR THE BLIDING-WINDOL MODEL
We first discuss the special case of clean and easy to present. For this setting, take advantage of the smooth histogram framework
algorithms since the algorithm and analysis are
5

---

Published as a conference paper at ICLR 2026
introduced by Braverman & Ostrovsky (2007). At a high level, function f is said to be smooth if the following condition holds. Let X and Xg be two frequency vectors for elements data streams A and B, where B is suffix of A. If f(xA) and f(xg) are already sufficiently close, then they remain close under any common suffix of updates, i.e., by appending C' to both A U C' and B BUG and getting new frequency vectors XAuC and Buc, the difference hetween (uC) and f(xBUC) remains small. Braverman & Ostrovsky (2007) already established the smoothness of Fp frequencies, and we further prove the smoothness properties for rectangle F6 frequencies and cascaded norms.
We now discuss the framework in more detail, starting with the introduction of the notion of common suffi--augmented frequency vectors.
Definition 3 (Common suffix- -alim--td frequency vectors). Let X and X8 be frequency vectors obtained from stream A with suffix B. Furthermore, let x be the frequency vector of common suffix C' of A and B. We say that XAUC and XBuc are a pair of common suffx-augmented frequency vectors if XAUC X, + X and XBUC Xg + XC-
In other words, let A, B, C' be the streaming elements of X, xB, and xc, respectively, In Definition we have A C B, and the streaming elements of XAUC and BBCC are A UUG C and B U C. We are now ready formally define (a, -smmoohh functions as follows.
Definition ((a, 3mmmoohhh functions, Definition of Braverman & Ostrovsky (2007)). A function f: IR" + E for frequency vectors is (a, -moooh if the following properties hold.
f(x) > 0 for any frequency vector x. f(x) < poly(n) for some fixed polynomial.
Let x be a frequency vector obtained from a suffix of XA, we have
(1) f(xA)= > f(xB).
(2) For any E (0, 1), there exits a = =(f,s) and 3 = =(f.)) such that
0 8 & a
If fxx)) > (1 (xx), then for any common suffix- frequency vectors
XAJC and XBUC as prescribed in Definition 3, there is f(xnuc) > (1 - af (xLA)).
Using the definition of (a,, -smoothh functions, we are able to derive the following framework that transform streaming algorithms to sliding- window algorithms in the augginnted regime. Lemma 3.1. Let f be an (a, B--moothh function, and let ALG be any
streaming
algorithm that queries the heavy-hitter oracle O with the following properties:
ALG outputs f'(x) such that (1 E) f(x) < (x(x & (1 ()) f(x) by the end of the stream with probability at least - 6;
satisfies the cuffi-compatiblee property as prescribed by Definition 2; and
ALC uses g(e, 8) space and performs h(c, 8) operations per stream update.
Then, there exists a sliding-window streaming algorithm ALG' that computes a (1 + (a + e))- approximation of the Alding-windoww with probability least 8 using O (gle, loggn space and O MMe.8))ogg logn B
B
operations per stream update, where 8'
8.9
log m
We defer the discussion and the proof for Lemma 3.1 Appendix A. Next, we show how the framework in Lemma 3.1 to obtain learning-augmented sliding-window algorithms. We remark that the bound provided by the framework is independent of the window size W. As such, our bounds in this section do not include the W parameter. Limited by space, we only present our results for Fp frequency moment estimation this section, and defer the results for rectangle Fp frequency moment estimation and cascaded norms to Appendix A.
Our learning- augmented sliding window algorithm for F, estimation for p >> 2 has the following guarantees with both perfect and erroneous oracles.
-agmented F, frequency moment algorithm). There exists a sliding-window window streaming algorithm that, given a stream of elements in a sliding window, a fixed parameter p 2 and deterministic suffix-compatible heavy-hitter oracle O (as prescribed by Defini- tion 2), with probability at least 99/100 oulputs a (1 + -ppprooximation of the Fp frequency
Theorem
1/-1//r p2+P loog n log( space.
in O g040

---

Published as a conference paper at ICLR 2026
Theorem 2
Fp frequency algorithm with stochastic oracles). There exists sliding-wing window streaming algorithm that, given a stream of elements in a sliding window, a fixed parameter 2, and stochastic suffix-compatible heavy-hitter oracle O with success probability 1 ô (as prescribed by Definition 2), with probability at least 99/100 100 outputs a (1 + ouppussa(++)-apppoooiiiii appproxiimaaoon of the Fp frequency moment space
(n5)t-1/x
ghop ppL loog log(()) bits if = Q(1/vm)
0
1//21//1 p2+ log log(?) bits if = 0(1/v))
For any constant and the space bound for the sliding-windee window Fp frequency moment estimation problem becomes (221/22)/p) for any learnin--augmen probability. This bound is optimal even in the streaming setting by Jiang et al. (2020); such, we Fp frequency estimation problem.
oracle with a sufficiently high success
obtain a near-optimal algorithm for the
At high level, the algorithm is an application of the learning- augmenned Fp frequency streaming algorithm in Jiang et al. (2020) to the framework we discussed Lemma 3.1. The guarantees of the algorithm in Jiang et al. (2020) can be described follows.
Lemma 3.2 (Jiang et al. (2020)). For any given stream, a fixed parameter > 2, and stochastic heavy-hitter oracle O with success probability 1 - ò, with probability at least 99/100, 100, Algorithm computes (1 appppooxinitionn of the Fp frequency using space
((( (n8)'-1/ log" n2) bits i (n)
0 1//2-/// log" n) bits i = O(1/vn).
To apply the reductions of Proposition 2 (presented in the Appendix A), need to understand the smoothness of the F2 frequency function, which a standard fact established by previous results. Lemma 3.3 (Braverman & Ostrovsky (2007)). The Fp frequeny function is (=. /p") - smooth.
Finalizing the proof of Theorems I and 2. We apply Lemma 3.1 to the algorithm of Lemma 3.2 with the smoothness guarantees as Lemma 3.3. For the success probability, we argue that the algorithm in Lemma 3.2 could be made succeed with probability at least 8 with (llo((1/)) multiplicative space overhead. This can be accomplished by the classical median trick: we run (1 /8) copies of the streaming algorithm, and take the median of the frequency output. By Chernoff bound argument, the failure probability is at most
Let 3 _" /p"; for the deterministic oracle case, could use g n//221// logg and failure probability = =0(3/ log n) to obtain that the space needed for the streaming algorithm is at most
g(E,6") 0 n 122/2/1/p
n 122111/
logg n log(n/B)
p. log" log(p/E))
g
Therefore, the space we need O (g(e,
(g(e, (0(e,00 8*) log
o
(22//
1/2 1/2 z+ty
DP log n log(()) as oracle, simply replace the
desired. Finally, for the case with the randomized 1/2-11/2 term in the bound with (n5)1-1/p, which would give the desired statement.
4 THE ALGORITHMS AND ANALYSIS FOR GENERAL TIME DECAY MODELS
In this section, deseribe algorithms for the general time-decay setting, where an update at time /' E [m]] contributes weight w(t - l' + 1) to the weight of coordinate in E [n) at time I. The underlying weighted frequency vector x" step i. is defined
Σ PE
w(t - 11)
The formal definition of the time-decay model and functions could be found in Section 2. Given non-decreasing function G IR =0 with G(O) 0, we define G-moment estimation as the
7

---

Published as a conference paper at ICLR 2026
problem of estimating
G(x) G(x)) iE(m)
When the context is clear, we also use the lower-case the input to the function G.
We introduce general framework that transforms a linear sketch streaming algorithm for the problem of G-moment estimation into time decay algorithm for G-moment estimation.
Definition 5 (Smoothness in time-decay models). Given e > 0, the weight function w and the G-moment function G are said be (E,2, -2).oothhhh if:
(1) G((1 + +)) G(x) f G(x:) for all > 1.
(2) There exists integer my 0 such that Eieim, w(i) and G(z + + v) G(x)
e. G(1) for all > In other words, all updates stream of length that arrived more than my previous timesteps can be ignored.
The next theorem provides a framework for polynomial-decay and exponential-decay models; we defer its proof to Appendix B.
Theorem 3. Given a streaming algorithm that provides (1 + appproxximatio to G-moment estimation using a linear sketch with k rows, functions G and w that satisfy the (E,v, -mmoothhsssss condition (Definition 5), there exists algorithm for general time-decay that provides (1 + e)-
approximation to G-moment estimation that uses at most O ( log n log bits of space.
Furthermore, the statement holds true for learning- aageinntegmmmeeeedddeeee algorithms as long as the oracle O is suffix-compatible.
We can apply Theorem on the F, moment estimation for the polynomial-decay model. We have described in Section 3 the algorithm for Fp estimation (Proposition 3), and we could apply Theorem to Proposition 3 to obtain the following result.
Theorem Given constant p > an accuracy parameter (0, 1), and heavy-hitter oracle O for the data stream, there exists one-pass algorithm that outputs (1 + apprrooxiinaio to the bits space.
rectangular Fp moment in the polynomial decay model that uses δ (A00/2-1/1)) 2244/9
EMPIRICAL EVALUATIONS
Experimental setup. To demonstrate the practicality of our theoretical results, compared non- augmented sliding window algorithms with their augmented counterparts. We implemented Alon al. (1999)'s algorithm for norm estimation, which we refer as AMS, and Indyk & Woodruff (2005)'s subsampling (SS) algorithm for f3 norm estimation. We utilized three different oracles for our augmented algorithms: Charikar et al. (2004)'s CountSketch (CS) algorithm, ChatGPT/Google Gemini Large Language Model (LLM), and an LSTM trained for heavy hitter prediction. We refer to the augmented algorithms as AMSA and SSA, respectively.
Datasets. We tested our implementations on three datasets:
(1) A synthetic, skewed rundom-integr distribution generated by sampling binomial distribu- tion with p 2 //, where q the desired number of heavy hitters and is the number of distinct integer values, i.e. the universe size.
(2) CAIDA dataset which contains 12 minutes of IP traffic; each minute contains about 30M IP addresses. We used subsets of the first minute test implementations. Each IP address was converted to its integer value using Python's 's ipaddress library.
(3) AOL dataset 6, which contains 20M user queries collected from 650k users. Each query associated with anonymous user id: used subset of these ids to test our implementations.
"https://www kwg.wwwwwwkwa.oooooo..../......e wtt.e//aaaaeeee///eeeee////////a
sessi on- col 1ect -on-500t
8

---

Published as a conference paper at ICLR 2026
Limited by space, only show the results for the weal-world CAIDA and AOL datasets, and defer the results for the synthetic datasets and provide additional experiments details in Appendix C.
Computing devices. We implemented our experiments in Python 3.10.18. The experiments were performed on an Apple MacBook Air M2 with 16GB of RAM. Experiments on CAIDA that varied window sizes took 1 1000 1400 minutes. Experiments that varied sample selection probabilities took 400 600 minutes. The runtimes were similar for the AOL dataset.
5.1
AMS AND LEARNING-AUGMENTT AMS ALGORITTMS
AMSAJAMS Estimation (n-1c6)
ANSAINYS Estimation on CAUAA (1-1e6)
Oreend Tull
ABDA
2.4
20303
Ramm
20000
20000
13209
10203
3321
200000
EX000
8B2090
200003
200333
ADERED
HAROSD
SOCEED
(b)
Fig. 1:
Experiments for le norm estimation on CAIDA. Note on the notation: the variable n in figures refers to stream length (which is other places of the paper).
Figure la compares the estimation results from our two algorithms to the actual &g norm over various timesteps. Note that n refers to stream length (not universe size) in Figure la, Figure 3a, and Figure Sa. The "timesteps" on the axis correspond to window sizes: estimates starting timestep 0 consider all 1M stream items, i.e. W = m, while subsequent estimates use the most recent 1M timestep values. In other words, W
f,, where f; is timestep and m is stream length. As seen in Figure 1a, AMSA estimates are much closer to the ground truth than AMS estimates over all selected window sizes, indicating that the augmented algorithm consistently produces more accurate estimate. This is further validated by Figure 1b, which plots the ratio of estimates to the ground truth over various window sizes. As shown, AMSA estimates are within factor of 1.2 over all window sizes, while AMS estimates vary between factors of about 1. 1.25 and 2.3. Additionally, AMSA estimates deviate from the ground truth by a somewhat consistent margin, while AMS estimations seem to get closer to the ground truth as the window size decreases, indicating that the augmented algorithm is more precise over a variety of window sizes. AMSA's precision is confirmed by the flatness of its error curve in Figure 1b over all window sizes, especially when compared to the AMS error line.
5.2 SS AND LEARNING-AUGMER
SS ALGORITHMS
MUL fre wed trieel Vison beickl
442 cnd 1LLTMM tel metion
3000
bew
3000
2010
X008
150
Dalintse LUP Oreil
140
Scmale Scentee Prtuliia
(b)
(c)
Fig. 2: Experiments for l3 estimation on CAIDA using multiple oracles
Figure 2a compares the estimation results from SSA and SS to the actual Eg norm over various window sizes. All three oracles provide useful augmentation, allowing SSA to estimate norms much

---

Published as a conference paper at ICLR 2026
closer to the ground truth than the baseline SS algorithm over all window sizes. Like for AMSA, the SSA error curve is closer to I and flatter than the SS error curve, indicating that SSA is more accurate and precise than its -on-angmetted counterpart.
Figure 2c compares the estimation results from SSA and SS to the actual &3 norm over various sample selection probabilities. Again, all three oracles help augment the baseline algorithm, providing estimation closer to the ground truth across all selection probabilities. Using a higher selection probability roughly corresponds higher memory usage since more elements must be stored in the estimate sample. The SSA estimation performs particularly well for very low memory usage and largely outperforms SS for higher memory usage, meaning that augmentation is beneficial even when the baseline algorithm has larger estimate sample sizes.
514,5 Istienat ADL (09)
504/55 Eitmmation brer AOL (e
564/55 w.w.ootionn ACL (nw2 de e55 Wwd De
Drimetes
300
625
<30
0.55
1,0
122
130
1.5
206
(a)
(b)
Fig. 3: Experiments for la estimation on AOL
Figure 3a provides the estimation results from SSA and SS the actual fy norm over various window sizes for the AOL dataset, second real-world dataset. The x-axis is converted from timesteps to window sizes and log-scaled for better interpretability; the y-axis is also log sealed. Combined with Figure 3b, we see that SSA is more accurate than SS for W > 125, 000. However, given its flat error curve and close estimates, SS seems to be a more reliable estimate for the AOL dataset than for the CAIDA dataset. We suspect that SSA is not as advantageous over SS because the AOL dataset is more uniform than the the CAIDA dataset. Nevertheless, SSA remains more accurate compared SS in this setting. Figure 3c compares the estimation results from SSA and SS to the actual l norm over various sample selection probabilities. As seen in the figure, SSA provides more accurate estimates of the &a norm than SS for especially small sample selection probabilities. As the probabilities increase, SS benefits from increased sample sizes, ultimately providing better estimates of the l norm. Cumulatively, SSA provides more accurate estimates over most of the sample selection probabilities, but especially for lower probabilities, indicating that it is more beneficial in low space settings.
ACKNOWLEDGMENTS
David Woodruff is supported in part Office Naval Research award number 4000142112647 and Simons Investigator Award. Samson Zhou is supported in part by NSF CCF-2335411. Samson Zhou gratefully acknowledges funding provided by the Oak Ridge Associated Universities (ORAU) Ralph E. Powe Junior Faculty Enhancement Award.
REFERENCES
Anders Aamand, Justin Y. Chen, Siddharth Gollapudi. Sandeep Silwal, and Hao Wu. Learning- augmented frequent directions. In The Thirteenth International Conference on Learning Represen- tations, ICLR 2025, 2025.
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Comput. Syst. Sci., 58(1):137-147. 1999.
Eiman Alothali, Hany Alashwal, and Saad Harous. Data stream mining techniques: a review. TELKOMNIKA (Telecommunicattin Computing Electronics and Control), 17(2):22-7377 2019.
10

---

Published as a conference paper at ICLR 2026
Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Streaming algorithms via precision sampling. In IEEE 52nd Anmual Symposium on Foundations of Computer Science, FOCS 2011, pp. 363-372, 2011.
Martin Anthony and Peter L. Bartlett. Neural Network Learning Theoretical Foundations. Cam bridge University Press, 2002.
Apple Inc. Differential privacy overview, 2021.
Ziv Bar- Yossef,,f Thathachar S Jayram, Ravi Kumar, and D Sivakumar. An information statistics approach to data stream and communication complexity. Journal of Computer and System Sciences, 68(4):702-732, 2004.
Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. Differentially private Iz- heavy hitters in the sliding window model. In The Eleventh International Conference on Learning Representations. ICLR, 2023.
Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghad- dam. Sliding window algorithms k-clustering problems. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurlPS, 2020.
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, and Jiapeng Zhang. A new information complexity measure for multi-pass palli--psssan streaming with applications. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, STOC, pp. 1781-1792, 2024a.
Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. 48th Anmual IEEE Symposium Foundations of Computer Science (FOCS 2007), pp. 283-293, 2007.
Vladimir Braverman and Rafail Ostrovsky. Approximating large frequency moments with pick- and-drop sampling. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 42-57, 2013.
Vladimir Braverman, Jonathan Katzman, Charles Seidell, and Gregory Vorsanger. An optimal algorithm for large frequency moments using o (1'(1-2/k) bits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), pp. 531-544, 2014.
Vladimir Braverman, Harry Lang, Keith D. Levin, and Morteza Monemizadeh. Clustering sliding windows in polylogarithmic space. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, pp. 350-364, 2015.
Vladimir Braverman, Harry Lang, Keith D. Levin, and Morteza Monemizadeh. Clustering problems sliding windows. In Proceedings of the Twenty-Seventh Annual ACM- Symposium Discrete Algorithms, SODA, pp. 1390, 2016.
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 7:1-7:22,
201 la.
Vladimir Braverman, Emanuele Viola, David P. Woodruff, and Lin F. Yang. Revisiting frequency moment estimation in random order streams. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, volume 107 of LIPles, pp. 25:1-25:14 2018b.
Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou. Improved algorithms for time decay streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, A APPROX/RANDOM 2019, volume 145 of L.PIcs, pp. 27:1-27:17, 2019.
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In st IEEF Annual Symposium Foundations of Computer Science, FOCS, pp. pp. 517-528, 2020.
11

---

Published as a conference paper at ICLR 2026
Vladimir Braverman, Viska Wei, and Samson Zhou. Symmetric norm estimation and regression sliding windows. In Computing and Combinatorics 27th International Conference, COCOON, Proceedings, 2021.
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning-auuean augmented maximum independent set. In Approximation. Randomization. and Combinatorial Optinization. Algorithms and Techniques, APPROX/RANDOM 2024, volume 317 of L.Plcs, pp. 24:1-24:18 2024b.
Vladimir Braverman, Jon C. Ergun, Chen Wang, and Samson Zhou, clustering. In Forty-Second International Conference Machine Learning (ICML.) 2025, 2025.
hierarchical
Vladimir Braverman, Sumegha Garg, Chen Wang, David Woodruff, and Samson Zhou. Online learning with limited information in the sliding window model. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, 2026.
Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi multi-party communication complexity of set disjointness. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), pp. 107-117, 2003.
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton Finding frequent items in data streams. Theor. Comput. Sci., 312(1):3-155 2004.
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 in graph streams. In The Tenth International Conference on Learning Representations, ICLR 2022, 2022.
Xu Chen, Junshan Wang. and Kunqing Xie. Trafficstream: A streaming traffic flow forecasting framework based graph neural networks and continual learning. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, pp. 3620-3626. ijcai.org, 2021.
Edith Cohen and Martin Strauss. Maintaining deca-ing stream aggregates. In Frank Neven, Catriel Beeri, and Tova Milo (eds.), Proceedings of the Tienty-Seconee ACM SIGACT-SIGMOD. SIGART Symposium on Principles of Database Systems, pp. 223-233. ACM, 2003.
Vincent Cohen-Addad, Tommaso d' d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. approximation algorithms for maximum cut and related problems. In Ad- vances Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024.
Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Qiaoyuan Yang, Yubo Zhang, and Samson Zhou. Fair clustering in the sliding window model. In The Thirleenth International Conference on Learning Representations, ICLR, 2025.
Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Algorithms,, 55(1):58-75, 2005.
Graham Cormode, Srikanta Tirthapura, and Bojian Xu. Time-decaying sketches for sensor data aggregation. In Indranil Gupta and Roger Wattenhofer (eds.), Proceedings the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, pp. 215-224, 2007.
Graham Cormode, Flip Korn, and Srikanta Tirthapura. Exponentially decayed aggregates data streams. In Gustavo Alonso, José A. Blakeley, and Arbee I.. P. Chen (eds.), Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, pp. 1379-1381, 2008
Graham Cormode, Srikanta Tirthapura, and Bojian Xu. Time-decayed correlated aggregates over data streams. Stat. Anal. Data Min., 2(5-6))294-310, 2009.
Michael S. Crouch, Andrew McGregor, and Daniel M. Stubbs. Dynamic graphs in the window model. In Algorithms- ESA st Annual European Symposium. Proceedings, pp. 337-348, 2013.
12

---

Published as a conference paper at ICLR 2026
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics sliding windows. SIAM J. Comput., (116):179--813,, 2002.
Yinhao Dong, Pan Peng, and Ali Vakilian.
streaming algorithms for approxi- mating MAX-CUT. 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, volume 325 of LIPles, pp. 44:1-44:24 2025.
Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong. Improved sliding window algorithms for clustering and coverage via bucketing- -based sketches. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 3005-3042, 2022.
Jon C. Ergun, Zhili Feng. Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augaae augmented k-means clustering. In The Tenth International Conference on Learning Representations, ICLR 2022, 2022.
Facebook. http://wwww.facccooo.oooo///////
2021.
Chunkai Fu, Brandon G. Nguyen, Jung Hoon Seo, Ryan Zesch, and Samson Zhou. Learning- augmented search data structures. In The Thirteenth International Conference on Learning Representations, ICLR 2025, 2025.
Mohamed Medhat Gaber, Arkady Zaslavsky, and Shonali Krishnaswamy. Mining data streams: a review. ACM Sigmod Record, 34(2):18-26 2005.
Joao Gama and Mohamed Medhat Gaber. Learning from data streams: processing techniques in sensor networks. Springer Science & Business Media, 2007.
GDPRI6. Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation). 2016.
Google LLI.C How google retains data we collect. Google, 2025.
Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Learning- augmented algorithms for online linear and semidefinite programming. In Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, 2022.
Chen-Ye Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR 20/9, 2019.
Junyu Huang, Qilong Feng, Ziyun Huang, Zhen Zhang, Jinhui Xu, and Jianxin Wang. New algorithms for the souming-augmentt k-means problem. In The Thirteenth International Conference on Learning Representations (ICLR 2025). 2025.
Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 202-208, 2005.
Piotr Indyk, Shyam Narayanan, and David Woodruff. Frequency estimation with one-sided error. In Proceedings of the 2022 ACM-SIAM Symposium Discrete Algorithmss, SODA 2022, pp. 695-707, 2022.
Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for wasserstein barycen- ter. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pp. 15582-15594, 2021.
Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Truly perfect samplers for data streams and sliding windows. In PODS '22: International Conference on Management of Data, pp. 29-40, 2022.
T. S. Jayram and David Woodruff. The data stream space complexity of cascaded norms. 50th Annual IEEF Symposium Foundations of Computer Science, FOCS 2009, pp. 765-774, 2009.
13

---

Published as a conference paper at ICLR 2026
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. Leaming-augmentt augmented data stream algorithms. In 8th International Conference on Learning Representations. ICLR 2020, 2020.
Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff. Fast moment estimation in data streams in optimal space. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, pp. 745-754, 2011.
Tsvi Kopelowitz and Ely Porat. Improved algorithms for polynomial decay and time-decay with additive error. In Theoretical Computer Science, 9th Italian Conference, ICTCS 2005, volume 3701, pp. 309-322, 2005.
Lap-Kei Lee and H. F. Ting. Maintaining significant stream statistics over sliding windows. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 724 724-732, 2006a.
Kep-Kei Lee and H. F. Ting. A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGAN Symposium on Principles of Database Systems, pp. 290-297, 2006b.
Ping Li. Estimators and tail bounds for dimension reduction in la (0 < & 2) using stable random projections. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 10-19, 2008
Honghao Lin, Tian Luo, and David P. Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, ICML 2022, 2022.
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. Journal of Machine Learning Research, 18(160):1-25, 2018.
OpenAI. https//opennai.com/entttrpppsssp
2024.
Marco Pulimeno, Italo Epicoco, and Massimo Cafaro. Distributed mining of time-faded heavy hitters. Inf. Sci., 545:633-666 66233-6662222 2021.
Rana Shahout, Ibrahim Sabek, and Michael Mitzenmacher. dearning-augmentt frequency estimation in sliding windows. In 32nd IEEE International Conference on Network Protocols, ICNP 2024, pp. 1-6, 2024.
Srikanta Tirthapura and David P. Woodruff. Rectangle-efficien aggregation in spatial data streams. In Proceedings of the s1 ACM SIGMOD-SIGACT-SIGAART Symposium on Principles of Database Systems, PODS, pp. 283-294, 2012.
David P. Woodruff. Optimal space lower bounds for all frequency moments. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA 2004, pp. 167-175, 2004.
David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 4622-4666, 2023.
David Woodruff and Samson Zhou Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium Foundations of Computer Science, FOCS 2021, pp. 1183-1198 196, 2021a
David P. Woodruff and Samson Zhou Separations for estimating large frequency moments on data streams. In 48th International Colloquium on Automata, Languages, and Programmingg ICALP 2021, volume 198 of LIPIcs, pp. 112:1-112:21, 2021b.
David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k-clustering in the sliding window model. In Advances Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS, 2023.
Qingjun Xiao, Haotian Wang, and Guannan Pan. Accurately identify time-decaying heavy hitters by decay-aware cuckoo filter along kicking path. 30th JEEE/ACM International Symposium on Quality of Service, IWQoS 2022, pp. 1-10, 2022.
14

---

Published as a conference paper at ICLR 2026
Chenliang Xu, Caiming Xiong, and Jason Corso. Streaming hierarchical video segmentation. In Computer Eision-ECCy 2012: 12th European Conference on Computer Vision, pp. 626-639, 2012.
A MISSING DETAILS OF SECTION
A.1 THE BLIDING-WINDOY FRAMEWORK AND THE PROOF OF LEMMA 3.1
Braverman & Ostrovsky (2007) gave reduction from sliding-window streaming algorithms the vanilla streaming (approximate) algorithms for (a, 3)-mmooth functions. The statement for such reductions is as follows.
Proposition 1 (Exact algorithms, Theorem of Braverman & Ostrovsky (2007)). Let f be (a. smooth function, and let ALG be a streaming algorithm that outputs f(x) by the end of the stream, where is the frequency vector the stream. Suppose ALG g space and performs operations per streaming update.
Then, there exists sliding- Aliding-window streaming algorithm ALG' that computes a apprrxxmttiiniiii of the Aliding-windowy using ( (g+log log space and O blogg operations per streaming update.
Proposition takes exact and deterministic streaming algorithms. It turns out that the framework much versatile, and could obtain similar results using approximate and randomized streaming algorithms. The new statement is as follows.
Proposition 2 (Approximate algorithms, Theorem 2 & 3 of Braverman & Ostrovsky (2007)). Let be (a, B) -m-oohhh function, and let ALG be streaming algorithm that outputs f((x) such that (1
J(x) & (x) & (1 +e) f(x) by the end of the stream with probability at least where x is the frequency vector of the stream. Suppose ALG uses g(e, 6) space and performs h(s, 8) operations per stream update.
=) s)
Then, there exists dliding-window streaming algorithm ALG' that computes (1 (a e))- approximation of the sliding-windows with probability at least 1 8 using O (ats, ("l+, n)-
space and O (h(e,6") )log operations per stream update, where 8'
58
Tog n
ALG(t))
ALG
ALG(t)
ALG
Stream
Active elements in sliding window
Fig. 4: Example of smooth histogram framework. Here (LG((2) and ALG(fa) sandwich the active elements and are thus good approximations of the sliding window.
At a high level, the algorithm of Braverman & Ostrovsky (2007) uses the idea of smooth histograms. The algorithm constructs smooth histograms by rumning the streaming algorithms with different starting times and discarding the redundant copies. An overview of the algorithm is given in Algorithm and an illustration is given in Figure
The algorithm for the framework prescribed in Propositions and 2. Input: stream of elements with m updates; window size W. Input: a streaming algorithm ALG with g(5,5) space and h(s,)) 5) update time Maintain set A of surviving copies of ALG
Algorithm 1.
For each update E [m]:
(1) Initiate a new copy of ALG (call it ALG(!) starting with the t-th update.
15

---

Published as a conference paper at ICLR 2026
Update all ALG E A with (t, (z)
Pruning:
(a) Starting from the algorithm ALG(O E A with the smallest index t.
(b) While & <:
Find the largest index & such that ALG > (1 3) ALG(O. ii. Prune all algorithms in with indices (e, k: 1].
Let l <- and continue the loop.
iv. Break the loop if there is surviving copy between é and t.
Output ALG(s), for the largest remaining index t, with t, < m - W +
Lemma 3.1. Let f be an (a, -mmooth function, and let ALG be any algorithm that queries the heavy-hitter oracle O with the following properties:
streaming
ALG outputs fx) such that (1 (1-E) f(x) < f'xx) & (1+ f(x) by the end of the
stream with probability at least 1 ò;
O satisfies the suffix-coll coftitiblm property prescribed by Definition 2; and
ALG uses g(e, 8) space and performs his, 6) operations per stream update.
Then, there exists a sliding-windod streaming algorithm ALG' that computes a (1 (a + s))- approximation of the diddnggwindows windows with probability least 1 5 using O [a(e. llgg
space and O hle.8') logn) operations per stream update, where 8' log n B
8,9
Proof. The correctness of the reductions in Proposition and Proposition 2 relies on the smooth histogram properly approximating the function on the sliding window.
Let W be the window size and to = m W + be the starting index of the active window. The goal estimate f on the stream suffix starting at t", The algorithm maintains a set of active instances A (ALG(t)) ALC(t2), ..... ALG(t)) with start times < 1/2 <... < lk-
Because the algorithm only deletes instances that are redundant via pruning, there exist two adjacent instances in A, denoted ALG(t) and ALG 1), that "sandwich" the true window start time, i.e., ty+1-
t, <
Let s(t) denote the suffix of the stream starting time t. Observe that S(t)) s(t)) 2 s(tn)), By the hypothesis of suffix-comin cuffix-comaatibiliit,y the oracle O provides valid advice to both ALC(t) and ALG(+++), Consequently, these instances correctly output values by ~ f(S(4) and 0j41 s f(S()+1)).
The pruning condition in Algorithm ensures that if both instances remain A, then Uj+1 > (1 - 3) ey. Since f is (a, 3m-otot and monotonic, the condition f({(+++)) > (1 (S(()) combined with the sandwiching property 5(t,) 2 5(()) 2 5(6+1) implies that the value uy is
(1 + approxxmatai of the true window value f(s((")).
Therefore, the coffiiiccmmaaiiiliityy ensures the individual instances are correct, and the smooth histogram ensures the output instance ALG!!() is an accurate approximation.
Finally, for the space complexity and the number of operations, argue that only keep O logg) copies of ALG. Note that we delete the copies such that ( > (1 :)) ALG(f) and the total number of updates can only be m = poly(n). Therefore, the total number of maintained copies can 53 be at most Oloo - (m)) = 0 log We scale = log to ensure the success probability, and we Olog n) space overhead for each copy of the algorithm maintain the time stamps. Combining the above bounds gives us the desired space and operation complexity.
16

---

Published as a conference paper at ICLR 2026
A.2 MISSING DETAILS OF THE SLIDING- WINDOW Fp ALGORITHM
We provide a brief description of the algorithm as in Algorithm 2, which, in turn, uses the following result black-box.
Proposition 3. [Alon al. (1999); Indyk & Woodruff (2005); Andoni et al. (2011)) There exists randomized algorithm such that given IR" stream of updates, computes (1 + e)- approximation of | with probability at least 99/ using space O 0 12/0
-logg n) space.
g244/F
The algorithm for learning-augmented streaming F, moment. Input: x given stream of updates
Algorithm 2.
Input: independent copies ALG; and ALG2 for the algorithm in Proposition 3.
For each element update on x;:
(1) Query whether is heavy hitter, i.e., |x,] 1
|xx
vn
If Yes, use ALG1 for items with predictions [x
|x
vn
Otherwise, compute the F, frequency of the non-heavy hitters follows.
(a) Sample x, with probability 1/Vn.
Let be the frequency vector obtained from the sampled non-heavy hitter elements.
(c) Compute the Fp frequency of x using ALG2 and re-weight with Summing up the results of ALG1 and ALG2 to output.
A.3 RECTANGLE F3 FREQUENCY FOR p
We now move to algorithm statements for deterministic and stochastic oracles follows.
rectangle Fy. frequency algorithms for 3 2. We combine the
Theorem There exists a sliding-windee window streuming algorithm that, given a stream of elements from
[A]á in sliding window, fixed parameter p > 2, and stochastic suffix-coppatible heavy-hitter oracle O with success probability 1 (as prescribed by Definition 2), with probability at least 99/ 100 outputs a (1 apprroxiitttio of the rectangle F, frequency in space
0
p8 1/2
poly(E, d, log A)) bits if 221/Vn).
goop
0 'p polyy d, log A) bits if = 0(1/m) glop
Furthermore, assuming the deterministic oracle, the sliding- window algorithm most O 0(440/2-1 A40/221//)) pp poly(E,d, log time to process each item.
Proof. The theorem statement before the "furthermore" part follows directly from Theorem 2. In particular, note that the rectangle F,. frequency problem could be framed as F, frequency with n & Ad, and plugging in the number would immediately lead to the desired space bounds.
For the process time, Jiang et al. (2020) has (1 = appppxxxiee algorithm for the rectangle Fp norm with per-update processing time O A 4411/2-1/p)
poly d, log A) time (without the p² p²/EP terms) and success probability 99/100. We could use the median trick to boost the success probability 5 with ((log(1/5) space overhead and no time complexity overhead (we could process copies of algorithms in parallel). Therefore, applying Proposition 2 with the same smoothness guarantees as Lemma 3.3 (rectangle Fb is a sub-family Ép frequencies) leads to the desired 0 A 11/2211/9) pd po d, log A) processing time in the wriddo model.
A.4 CAASCADDD NORMS
We now move the results for the learning-augee augmented sliding-windows window ccascaded norm algorithm. The guarantees of the algorithm follows.
17

---

Published as a conference paper at ICLR 2026
Theorem 6. There exists sliding- wrddingwwindowwooo streaming algorithm that, given X d matrix X represented as a stream of insertions and deletions of the coordinates Xa.g. fixed parameters k ?
p > 2, and (deterministic) suffix-compatble heavy-hitter oracle O with probability at least 99/100 oulputs a (1 + appproxximmto of the (k, p) -cascaded norm in space Onn - - - poly( logn)).
For any constant choices of p. k, and bound asymptotically matches the optimal memory bound for the learning-augmented streaming algorithm. Our algorithm takes advantage of the framework of Jayram & Woodruff (2009) and Jiang et al. (2020) with the smooth histogram framework as in Propositions 1 and 2. The algorithm for streaming involved. As such, we provided sketch in Algorithm 3, and refer keen readers to Jayram & Woodruff (2009) and Jiang et al. (2020) for more details. In what follows, we use (X) to denote the vector Fp norm of the elements in X.
cascaded norm is quite
Algorithm& 3.
streaming (k, (k,p)-cascade caaccded norm.
Input: n x d matrix X the input; parameters k and p Input: a heavy hitter oracle predicting whether [X 1 > |X|| /(d//2 (//////122222111111"1"1""""1 -222/22)
Parameters:
Q Onnn-1/kk that T (nd Q) d3/2 n 1222/
Levels é [O(log n)]; layers t [O(log n/))]: Te = =T/2'.
Parameters Ç, 77, 0, for layering and sampling (as per Jayram & Woodruff (2009)).
Apply count-sketch type of algorithms (e.g.. the algorithm of Proposition 3) during the stream maintain elements that sampled by the level-wise pre-processing step.
Level-wise processing for level E [O n)]:
(1) Sample each row with probability 1/2'; let ( be the resulting matrix.
(2) Divide the entries in x() among layers: each layer contains the elements with magnitude in ((r))
(3) A layer t is contributing if [S,(X (1())))))) > (x(X()) where S,(X are entries in layert.
(4) Further divide the elements contributing layers into heavy hitters and non-heavy hitters. This results in contributing layers with entirely heavy hitters non-heavy hitters.
(5) For each contributing layer t:
(a) If it is formed with non-heavy hitters (light elements) and entries N, is more than B, (QIS,(X(())) (x()) (F,,))))FFFF((("
down sample with rate 0Q (b) Let j be the parameter such that (X(()())))22 & Be () Sample each entry of the layer with rate 1/2 obtain Y, as the resulting matrix.
(6) Aggregate all Y, elements (using the count-sketch algorithm) as the pre-processed
vector (+)
Adding up all (() to get and perform "L, "appsamplngg process on Y in the same manner of Jayram Woodruff (2009) to obtain Y. Compute F& (P,,(Y) (Y)) the estimation.
Jiang al. (2020) provided the guarantees for Algorithm with the heavy-hitter oracle for vanilla streaming algorithms.
Lemma A.1 (Jiang et al. (2020)). Let > O and k > > 2 be given parameters. Furthermore, let X an n x d matrix given as a siream of insertions and deletions of the coordinates X.,j- Then, Algorithm 3 outputs a (1 + -ppproxiimtti of the (k, (kuscccddd norm with probability at least 99/100 using O t th dà p
space.
Next, we need to bound the smoothness of the (k, p) casccdded norm. In what follows, we write the (k, ccsscdde norm function for "norm of norms", i.e. in the form of Fx(F,(X))
18

---

Published as a conference paper at ICLR 2026
Ei=1 (E)- (()))))))))))))) 1/R
for 3 p 2 Our technical lemma for the smoothness of such
functions is follows.
Lemma A.2. For any constants 3 p 2 2, the (k, p) cascaded norm (x(Fx(X)) is (e, /k)- smooth.
Proof. Let X A be a matrix obtained by suffix of updates of X R Furthermore, let X be a common suffix of X and X We also partition the updates in = A AU(B \ A), and B A could be empty 1. and X A) be the updates of the vector in the i-th row of sets. We further let x,, (resp. X X
X. We lower bound the value of (Fx (Fx((((XX))) "))" follows.
(FA(F((X"))) 1))*
()()))))
1/2)
x + x 23)
)0))
1/p) k
Σ
X
P + Σ
x
BBA 1
(by superadditivity for p > 1)
1=1
k/p
k/p)
Σ
x 1p
+
Σ
x
B3 a
(by superadditivity for k: > p)
(F((F((X*))) * + (F((E(()))))
Therefore, for any (possibly empty) X if FFF and (x((F(X²)) are B-close, meaning
(x)))(x))) > (1 -3 (x we have that
(F((3((BAA))) < -(M(XXX)))
< (1- (1- -FF(---))
kB (F)((
(by Bernoulli's inequality)
Taking the 1/k-th exponent, we obtain Ps. (F, (X & (1:) Fx(P((XB)).
We now introduce the common suffix X. and lower bound the value of FF (XL))) as follows.
By Minkowski's inequality, since k 2 p 2 2, we have that
(XFF((B & (F, (UC)) + FA(FF(X
As such, since X is non-negative frequency matrix, we have that Fv (1,((X))) & (L(PI(XBL))) Therefore, we could obtain
Fa (x AUG
> (LC -A(FF(XX1A)
()(F(( - (KB) Fa(F((X"))
> (1 (K3) FF(FF(X
By setting 3= g*/Ri, we have (k:3)//4 = E, which leads to Ex(F,(XAUC) AUC) > (1 - e) FF(FF
which is the desired property for (e, e smoothhesss
19

---

Published as a conference paper at ICLR 2026
Finalizing the proof of Theorem 6. We again apply Proposition 2 (with Lemma 3.1) to the algorithm of Lemma A.I. By Lemma A.2, the (k: p)-ccccdded norm is (e, -smooth.
With the same median trick we used in the proof of Theorem we could show that we only need (llog(16)) multiplicative space overhead on the space to ensure Algorithm 3 succeeds with probability least 1 8. Therefore, by setting 3 =
.े. we could obtain
g(=, 8') - 0 n # d poly (1
F logn log(n/3)
< 0 n1 1 # .d poly
log
Therefore, the space we need is
gle, (((e, 8'))
log n2
1-
d poly
This gives the bound as desired by the theorem statement.
B MISSING DETAILS IN SECTION 4
We give the missing details of Section 4 in this section, including the proof of Theorem 3 and the results. We start with the re-statement of Theorem' 3. The algorithm for the framework is shown in Algorithm 1.
Algorithm 1 Framework for time decay G-moment estimation.
Input: Sketch matrix A E &x for G-moment estimation with post- pest-processing function f(-),
accuracy parameter (0,
1: Let v, 1/ my be defined as in Definition 5
2: Maintain linear sketch with A for each block B3 of size
3: for each time E [m]] do
4: u 0
5: for each block B; do
6:
Let Av, be the linear sketch for block B; Let f; be the largest timestep in block B;
7:
8:
if - + > my then
9:
Delete block B;
10:
else all weights in blocks B, and By are within vI+ then Merge blocks B, and B,
11:
12:
else
13:
w. VT+J w(m to
14:
11 4- 11 + w/ Av;
15:
return f(u)
Theorem 3. Given a streaming algorithm that provides a (1 + e)aaprooximation to G-moment estimation using a linear sketch with lo rows, functions G and that satisfy the (e, 1) smoothness condition (Definition 5), there exists algorithm for general time-decay that provides (1 + +)-
approximation to G-moment estimation that uses at most O log n logog t bits of space.
Furthermore, the statement holds true for auggentte algorithus as long as the oracle O is suffix-compatible.
Proof. Consider a fixed [n] and all times ta...... ................................ & t with updates a. Then the weight of at time t is EjE(+) w(t - ta, + 1). Let w/ be the weight assigned to time by the linear sketch. We claim that
Σ w lag +1 & jE(r)
w' laz + $ Σ w(t lag + 1).
V++
jEIr]
jE(r]
20

---

Published as a conference paper at ICLR 2026
Consider a fixed block B, Firstly, note that by definition of my and by construction, the weights of all indices each block are within a multiplicative factor of vI+ 17. All elements in block B, assigned weight wi to be गाम times the weight of the most recent item in B;. Thus, we have vI+ 77 w(t - ta, +) & / & w(t - ta, + +1) for any update ta, to a within block B, Finally, for any update ta in block that does not have a sketch must satisfy t ta, + e ny. By definition, the weights all such updates is at most v. Hence, we have
1
Σ jE(r
w'(t= ta; + +1)
Σ /EIr]
w' (t taj +1) Σ w(t ta; + 1),
v1 + 7
jC[r]
as desired.
Let ((:a)) be the weight of coordinate E [n] implicitly assigned through this process. By definition of 1) and v, it then follows that (1 - 1) G(x,)) & G(x,) & G(zz). Summing across all i E [n]] we we have
Σ (1-1)) 4) Σ G(a,) < G(a,) & iE(n]
G(a.).
kE(M)
kE(M)
Thus, it suffices to obtain a (1 + + -approximation the G-moment of the frequency vector weighted by w'. Since A is linear sketch and w v; precisely the frequency vector of block B; weighted by w', then this is exactly what the post-processing function f achieves. Therefore, correctness of the algorithm holds.
It remains to analyze the space complexity. Each linear sketch A V, uses O (k log bits of space assuming all weights and frequencies can represented using O (logn) bits of space. This can be optimized for specific functions wi()) and G(-), which we shall do for specific applications. In general, observe that we maintain at most three blocks containing weights within a multiplicative factor of
(1 + 1)) The smallest weight of index in block is at least I+7 2 2. while we have w(1) 1 by assumption. Therefore, the number of blocks is at most 3 (1)
2 since w is non non-increasing.
Hence, the algorithm uses at most O log log ) bits of space.
Finally, the "furthermore" part of the statement regarding the suffix-compatble oracles follows from the same argument as we made in Lemma 3.1.
We now present the results for the time-decay models in order. We first consider the polynomial decay model, where we have w(t) +. for some fixed parameter rectangular moment estimation, and cascaded norms, we have that the G-moment is still preserved within a factor of (1 + E) even when the coordinates are distorted up to factor of (1 + O (e)).
0. For F, moment estimation.
Lemma B.1. For the polynomial decay model w(t) gu. it suffices to set 17 O (E) and
Proof. We provide the proof for the G-moment function for the F, problem, G(x) |a||.. The statements for cascaded norm and rectangular moment estimation follow analogously.
First, note that for 7) Toúp O (e), have (1 + 1/) 1 < f. Thus, it follows that for G(xx) = |a| and for all 2 1, we have
c(11+m)x)
G(zz)
for 17 = T = (s), as desired.
Second, note that G(1) 1 and since p 2, the expression (x + v)P x" is maximized at z m. On the other hand, we have for v 100pmr (m + v)2 - m2 < 4. and thus
- -)
< G(1).
for all x E m.) desired. In this case, set m,, 1- 2/s which may may not be larger than m, but the latter case does not matter, since there will be no blocks that have been stored for m 1 steps.
21

---

Published as a conference paper at ICLR 2026
Recall that in the standard streaming model, Fp moment estimation be achieved using the following guarantees:
Proposition 3. [Alon et al. (1999); Indyk & Woodruff (2005); Andoni et al. (2011)) There exists
randomized algorithm such that given IR" as stream of updates, computes (1 E)- n
approximation of |x| with probability at least 99/100 using space O
0(n'-2/r 1-2ppp
5214/F -log" n.) space.
By applying Theorem 3 to Proposition 3, we have the following algorithm for Pp moment estimation in the polynomial- model.
Theorem 7, Given a constant p > 2 and an accuracy parameter & E (0, 1), there exists a one-pass algorithm that outputs (1 + appproxiimatn to the Fs moment in the polynomial-dest model that uses O
1-220 bits of space.
624475
By comparison, using the approach of Jiang et al. (2020), we have the following guarantees:
Theorem 8. Given constant > 2, an accuracy parameter E (0, 1), and heavy-hitter oracle O for the data stream, there exists a one-pass algorithm that outputs (1 + -a-apprxximmtion to the Fp moment the polynomial- model that uses
1/2211/p) 22447
bits of space.
Similarly, we can use the following linear sketch for rectangular F, moment estimation:
Proposition 4. Tirthapura & Woodruff (2012) Given a constant p > 2 and an accuracy parameter & E (0,1), there exists a one-pass algorithm that uses linear sketch and oulputs (1 + e)-
approximation to the rectangular Fo moment in the streaming model that uses Ō space.
Adll 2/v)
bits of
g2 4/2
By applying Theorem 3 to Proposition 4, framework achieves the following guarantees for rectangular Fp moment estimation in the polynomial-decay model.
Theorem 9. Given a constant p > 2 and an accuracy parameter & E (0, 1), there exists a one-pass algorithm that outputs a (1+E) aaprrxxiiaioiioi the rectangular Fp moment in the polynomial-decay model that uses δ A4012/p) 2444/p
bits of space.
By comparison, using the approach of Jiang al. (2020), we have the following guarantees (restated from Section 4):
Theorem Given a constant p > 2, an accuracy parameter E (0, 1), and a heavy-hitter oracle O for the data stream, there exists one-pass algorithm that outputs (1 + apparooxiimaoo the bits of space.
rectangular Fp moment in the polynomial-dess model that uses Ō A ((1/2-11/))
2241/0
Similarly, consider the exponential decay model, where we have w(t) s for some fixed parameter E (0, 1]. For Fp moment estimation, rectangular moment estimation, and cascaded norms, we have that the G-moment is still preserved within a factor of (1 + e) even when the coordinates are distorted up to factor of (1 O (E)).
Lemma B.2. For the exponential decay model w(t) st, it suffices set 1
O (s) and O (+)
Proof. We again consider the G-moment function for the Fp problem, G(z) | as the the proofs
for cascaded norm and rectangular moments are similar. First, for = 1000 = O (=), we have
(1 + 1)) 5 Therefore, for G(z) |æ| and all > G((1 m)))) G(x) < & G(x), as required.
Second, recall that G(1) 1. Since p 2 2, the quantity (x uP xd achieves its maximum over mm at x = m. For = T00pm we have (m + v)P m & 5. Thus, for every x E [1,m], G(r + +) G(x) < G(1. Importantly, this value of y means can set my O (logn).
Therefore, by applying Theorem 3 to the relevant statements, we obtain the following results for F, moment estimation in the exponential-decay model.
22

---

Published as a conference paper at ICLR 2026
Theorem 10. Given constant p >> 2 and an accuracy parameter E (0, 1), there exists one-pass algorithm that outputs (1 (1+ approximaato to the Fp moment in the exponential-dee decay model that uses δ
2/v bits of space.
Theorem 11. Given constant > 2, an accuracy parameter e E (0, 1), and a heavy-hitter oracle O for the data stream, there exists one-pass algorithm that outputs (1 + a)approoximation the Fp moment in the exponential-dece model that uses O 22/22 1/2
bits of space.
g2447p
Similarly, we obtain the following results for rectangular Pp moment estimation in the exponential- decay model.
Theorem 12. Given a constant p > 2 and an accuracy parameter & E (0, 1), there exists one-pass algorithm that outputs a (1+E) approxxmaton to the rectangular Fp moment in the exponential-decat (29p)
model that uses
bits of space.
6244/P
Theorem 13. Given constant 2, accuracy parameter E. (0, 1). and a heavy-hitte oracle O for the data stream, there exists one-pass algorithm that outpuis + "approximatiin the bits of space.
reclangular Fp moment in the exponential-decay model that uses Ô (A00/2-1/p) T214
We remark the main difference between behaviors of our framework in the polynomial-dece model and in the aaponential-decat model. Intuitively, the framework will create logarithmic number of large blocks in the polynomial-decay model, because the stream progresses, it takes significantly larger number of updates for the weight to decrease by factor of (1 + 7). In contrast, the framework will create logarithmic number of small blocks in the exponential-decat model, but then the blocks will be truncated after O (log n.) updates.
C ADDITIONAL DETAILS FOR THE EXPERIMENTS
When implementing our experiments, we experimentally chose multiple parameters for our augmented and non-au con-augmented algorithms. This section provides details and justifications for these parameters and presents additional experiments.
C.I ORACLES & TRAINING
To demonstrate that a heavy-hitter oracle feasible, we used several oracles in our experiments. All three oracles were used for experiments on the CAIDA dataset, while only the Count-Sketch oracle was used for the other datasets. Each oracle was trained on a data stream prefix and was asked to identify items that would be heavy hitters in the stream suffix.
Count-Sketch oracle. For our first oracle, we implemented the well-known Count-Sketch algo- rithm Charikar al. (2004) for finding heavy-hitters on a data stream. The prefix sketching results became our heavy hitters for the suffix. For the synthetic and CAIDA datasets, we used 100K length prefix, repeated the algorithm times, used 300 hashing buckets, and set 0.1. We changed the prefix to 10K for the AOL dataset but maintained the other parameters.
LLM oracle. For our Large Language Model (LLM) oracle, we provided the same 100K CAIDA prefix to ChatGPT and Google Gemini and used the following prompt:
Given this stream subset, predict 26 ip addresses that will occur most frequently the future data stream
ChatGPT and Google Gemini predicted identical heavy hitters, a single LLM oracle. Since Count-Sketch identified 26 heavy hitters, we specifically asked for 26 ip addresses ensure reasonable comparison between the oracles. The LLM and Count-Sketch algorithms agreed on the identities of 10/26 heavy-hitters
combined their results into
LSTM oracle. For our LSTM oracle, trained heavy-hitter predictor the same 100K CAIDA prefix. The LSTM consisted of an embedding layer that embedded the universe to 32 dimensions, a single LST layer with embedding dimension 32 and hidden dimension 64, and fully connected
23

---

Published as a conference paper at ICLR 2026
output layer. The predictor trained for 50 epochs with Binary Cross-Entropp Entropy (BCE) Loss using Adam Optimizer with learning rate 0.001. The batch size was set to 64.
C.2 AMS AND LEARNING-AUGMENTIO AMS
We implemented Alon et al. (1999)'s algorithm, which we call AMS, as a baseline for lo norm approximation on the CAIDA dataset. We augmented the baseline algorithm with heavy-hitters from the oracles to compare the algorithmss' performance. To convert the streaming algorithms into sliding window ones, we tracked multiple instances of each algorithm. Each instance started at different timestep to account for different sliding window of the data stream. Relying on Braverman & Ostrovsky (2007), when two instances' le norm approximation was within a factor of two, we discarded one instance and used the other to approximate the discarded instance's ' sliding window. We allowed a maximum of 20 algorithm instances. Each instance of the algorithm contained 11 estimates (obtained with different seeds), so we estimated the l2 norm as the median of these estimates. For our hash function, we implemented a seeded hashing mechanism in which the hash output is determined by evaluating a low-degree polynomial over the input domain with coefficients derived from pseudo- random generator. Specifically, we initialized NumPy's default random number generator with seed value then sampled four integer coefficients over the range [0, p). where is a large prime (default 231 1). Note that the seed is set to the repetition number. Our input stream item value was coerced to an integer and substituted into a polynomial of degree three, with each term computed modulo p to avoid overflow and maintain arithmetic within a finite field. The polynomial was evaluated incrementally, applying modular reduction at each step, and the final result was mapped into an output space of size via an additional modulo operation. We mapped the final value to {-1, 13 by multiplying this output by two and subtracting one.
C.3 SS AND LEARNING-AUGMENTI SS
For higher order norm estimation, we implemented Indyk & Woodruff (2005)'s selective subsampling (SS) algorithm. Like before, we created an augmented version of the algorithm and compared its performance to the baseline on the CAIDA, AOL, and synthetic datasets. We used the same histogram mechanism to create a sliding window version of both algorithms. We repeated both algorithms 15 times: each timestep instance of the algorithm held 3 sets of 5 estimates (obtained with different seeds) for the same window. We obtained our l norm estimate by first taking the mean of each of the 5 estimates, then taking the mean of the remaining 3 values. Again, we allowed a maximum of 20 algorithm instances. For our hash function, we took as input a seed and the stream item value, concatenated them into canonical string representation, and computed SHA-256 cryptographic hash over this composite input. Note that the seed was obtained by taking the sum of the stream item value and the repetition number. The resulting 256-bit digest was interpreted as a large integer and used to initialize a local instance of Python's 's pseudorandom number generator. A single uniform variate in the interval [0, 1) was then produced. If the hash value was below sample selection probability, which we set to 9sea
T00 and qss = 1
To. we sampled the stream item, which effectively
defined our bucket count.
C.4 EXPERIMENTS ON ADDITIONAL. DATASETS
C.4.1 SYNTHETIC DATASET
Figure 5a compares the results from the estimation algorithms, SSA and SS, the actual la norm over multiple window sizes for our synthetically generated dataset described in Section 5. Additionally, we include "SSA Scaled" and "SS Scaled", which are obtained by scaling the estimates for W m (the largest window size) by W. to estimate smaller window sizes. These methods aim to create natural heuristies to transform vanilla streaming algorithms into rescaling to estimate smaller window should work well if the distribution remains unchanged over the stream. However, our synthetic data deliberately includes a distribution shift to analyze if our augmented algorithm, SSA, provides benefits when distribution changes occurs. As seen in Figure 5a, the non- aunaeueented algorithms. SS and SS- SS-Scaled, are significantly further from the ground truth than the augmented-algoritme algorithms, SSA and SSA-Scaled. This is supported by the error curves in Figure 5b, which show that the gap between the augmented and non-augmented algorithms increases as the window size shrinks, highlighting that an adversarial distribution shift causes the algorithms to lose
ones. Intuitively, simply
24

---

Published as a conference paper at ICLR 2026
SSA/SS Estimetion (n=2.0++05)
SSA/SS Estimation Error (n=2.0e+05)
X
95A Estimation
SSA Estmaaiin
2SA Sealed
SSA Sealed
21000
Est
Scaled
30030
10
Esteated Norm
25000
20000
X
21000
25000 50000
15000 100000 225000 150020 175003 200000 Stariing I Timecip
25000 50000 75000 200000 125000 150000 175000 200000
Scarting Timrestap
(a)
(b)
Fig. 5: Experiments for estimation synthetic data
aceuracy. Between SSA and SSA-scaled, SSA provides an estimate much closer the ground truth across window-sizes.
Estimated (.=3.p--)ccacccaeee 3)-cascaded Narm per timestep In=11.0 -
[k=3,pm 33.ccssadd Norm Error (n=1.0a-D4]
-750
remmmeed 0k cancadee hoom
2250
2000
Eommstes se--cascdddddeeme
55A Eshmattin 53 Estimation
300
6000
8000
10000
2000
1000
6000
8000
10309
starting Tumestup
Starting Timestep
(b)
Estimated (k=S.ppd)cccccteed Norm per timestsp
X
SGA
3750
Estintter plocescavee Norm Ground Thath
Ground
Palmattd P..l aalcerrace hore
3500
-300
X
Latimation
2000
4000
6000
30c0
10000
2000
4000
5000
8000
10000
sharting Timecieg
Grertin Timechep
(C)
(d)
Fig. 6: Experiments for (k.p))cascadee norm estimation on synthetic data
Figure 6 compares the results from the estimation algorithms, SSA and SS, to the actual (k, p)- cascaded norm over multiple window sizes for our synthetically generated dataset. Across all window sizes shown in Figure 6a and Figure 6c, SSA. the augmented algorithm, provides much higher quality estimate than SS. As shown in Figure 6b and Figure 6d, the ratio between the SSA estimate and ground truth value remains nearly constant across all window sizes. Conversely, the SS estimate
25

---

Published as a conference paper at ICLR 2026
seems to degrade exponentially with increased window size. Moreover, compared to its estimate for (k: = 3. p.p = 3), SS provides an estimate that is twice as bad for (A: = 5. = 5) 5)-cascaded norms, while SSA remains about equal. This highlights that SSA is relatively stable for higher order norms, while SS degrades more noticeably. Together, the plots suggest that augmenting the baseline algorithm with heavy hitters provides useful information for obtaining higher quality estimates of the (t,p))cascade' norm over various window sizes. In addition to estimation quality, we also monitored the memory usage and running time of the two algorithms. For (A 5.P p -ccasadde norm estimation, SSA consumed 68.86 MB of RAM while SS consumed 74.63 MB of RAM, which aligns well with our expectation that the augmented algorithm will consume less memory. The trend is similar for (k: = 3. p -ccacadee norm estimates as SSA consumed 1 112.32 MB of RAM, while SS consumed 1 117.27 MB of RAM. Additionally, for (A: = p, = 5) SSA ran for 40.3s while SS ran for 63.5s, and for (k 3, p 3) SSA ran for 40.1s while SS ran for 61.8s. For both settings, the CountSketch oracle itself used 65.96 MB of RAM. Put together, these results show that SSA can provide higher quality estimates of the (k, casscded norm using less memory than SS while running slightly faster than SS.
D THE HEAVY-HITTER ORACLE AND LEARNING THEORY
In this section, we discuss the theoretical aspect of the implementation of the heavy-hitter oracle using the Probably Approximately Correct (PAC) learning framework. The framework helps to demonstrate that a predictor of high quality can be learned efficiently, given that the input instances are from fixed probability distribution. The discussion of implementing oracles for learning- augmenned algorithms enjoys a long history, see, e.g., Izzo et al. (2021); Ergun et al. (2022); Grigorescu et al. (2022); Braverman et al. (2025), and adapt this framework for the purpose of our heavy-hitter oracles.
Initially, we assume underlying distribution, denoted as D, from which the input data (frequency vectors of x) is sampled. This setup is standard for solving the frequency estimation problem with or without the learning-augmented oracles. The machine learning model for the oracle would perform well as long as no generalization failure or distribution shift occurs.
Our objective is then efficiently derive a predictor function from given family of possible functions F. The input for any predictor f consists of frequency vector of x. and the output of the predictor is a vector {0, 13" indicating whether each x; is heavy hitter. We then introduce loss function L: f x G - R, which quantifies the accuracy of a predictor f when applied to a specific input instance x. One could think of L as the function that accounts for the incorrect predictions when compared to the actual heavy-hitter information.
Our goal is to learn the function f E F that minimizes the following objective expression:
min E [T(](x))]- JEF X
Let f" represent optimal function within the family F, such that f argmin E [L(f(x)) is x~D function that minimizes the aforementioned objective. Assuming that for every frequency vector and every function f E J, we can compute both fx) and L(((x)) in time T(n), we can state the following results using the standard empirical risk minimization method.
Theorem 14. An algorithum exists that utilizes poly (T(n), 2) samples and outputs a function ff such that with probability at least 99/190 99/100, we have
E
[((()))
< min E [L(f()))] +e. X
x
In essence, Theorem 14 is PAC-style result that provides a bound on the number of samples required to achieve a high probability of learning an approximately optimal function.
In what follows, we discuss the proof of Theorem 14 in more detail. We first define the pseudo- dimension for class of functions, which extends the concept of VC dimension to functions with real-valued outputs.
Definition 6 Essuud-dimension e.g., Definition 9 in Lucic et al. (2018)). Let X be a ground set, and let F be set of functions that map elements from X' to the interval [0, 1]. Consider a fixed set
26

---

Published as a conference paper at ICLR 2026
S= {x ",, C X, set of real numbers R 72 ....... ,rn). any function f E F, the subset S = {r, E 5 f(x,) ) 2 r. is known as the induced subset of S (determined by the function f and the real values R). We say that the set S along with its associated
where each r; [0. 1]. Fix
values R is shattered by FF if the count of distinct induced subsets is [[5 I E F) | = 2". Then, the pseudo-dimension of F is defined the cardinality of the largest subset of X that can be shattered by F (or it is infinite if such a maximum does not exist).
By employing the concept of pseedo-dimenn dimension, we can now establish a trade-off between accuracy and sample complexity for empirical risk minimization. Let H. be the class of functions formed by composing functions in F with L; that is, H == {Lof: E F}. Furthermore, through normalization, can assume that the range of L in the range of [0, 1]. A well-known generalization bound is given as follows.
Proposition (Anthony & Bartlett (2002)). Ler D be distribution over problem instances in X, and let H be a class of functions h X + [0, 1] with a pseudo dimeeddn dy. Consider t independent and identically distributed (i.id.) samples X1. X drawn from D. Then, there exists universal constant oo such that for any > 0, ift > E2,, then for all h E H. we have that with probability least 99 100:
h(x:) [h(x)]
x
The following corollary is an immediate consequence derived by applying the triangle inequality on Proposition 5.
Corollary 15. Let Xx be set of independent samples (frequency vectors) drawn from D. and let h E H be a function that minimizes? i Ei= h(x;). If the number of samples is selected as specified in Proposition 5, Le.,, & 2 Co dy then with a probability of at least 99/100, we have
[(x))
E x
[x^ + 2E.
X
Finally, we could relate the pseudo-dimension with VC dimension using standard results.
Lemma D.1 (Pseudo-dimension and VC dimension, Lemma 10 in Lucic et al. (2018)). For any H. let By, be the indicator function of the threshold function, i.e., Br y) sgn(h((x) y).
Then the ggeudo-diennsn of H equals the VC-dimension of the sub-class Bu = {B, h E H).
Lemma D.2 (Theorem 8.14 in Anthony & Bartlett (2002)). Let T Ra x R + {0, 1}, defining the class
T= (a+ T(0, x) e R*).
Assume that any function T can be computed by an algorithm that takes as input the pair (0, x) E Ra x R2 and produces the value T(0, x)) after performing no more than of the following operations:
arithmetic operations +, /// real numbers,
comparisons involving >, 3, <, E, =, andd outputting the result of such comparisons,
outputting 0 or
Then, the VC dimension T is bounded by O + Pogaa.
By Lemma D.1 and Lemma D.2, we could straightforwarddy bound the VC dimension of the concept class F. which, in turn, bounds the pseudo-dimension of the concept class F. This completes the last peice we need to prove Theorem
Proof of Theorem 14. From Lemma D.I and Lemma D.2, we obtain that the pseudo-dimensinn of J
bounded by O(n² (n)) by using a = n and = (n)). This bound could in turn be bounded (ol)( As such, by Corollary 15, only need poly(T(n))/e² samples. We assumed fxx and (x)) can be computed in time T(n), and applying any poly-time ERM algorithm gives us the total running time of poly(T(n)) 1/e), as desired.
27

---

Published as a conference paper at ICLR 2026
It is important to note that Theorem 14 is generic framework for every function within the family of oracles under consideration can be computed efficiently, then Theorem 14 ensures that polynomial number of samples will be adequate to learn oracle that is nearly optimal.
oracles. If
28


Reviews:
[{"review_id": "afWOWXJNWH", "reviewer": "Reviewer_cfdo", "summary": "This paper brings machine-learning hints to streaming algorithms that forget old data. It targets sliding windows and decay models where recent items count more. With a predictor that flags large coordinates, the authors obtain accurate frequency and norm estimates using memory that grows slowly with data size and error tolerance. Theory shows the method is close to the best possible, and tests on internet traffic traces cut error by twenty to fifty percent versus standard sketches.", "questions": "See above weakness.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Novel and timely problem formulation: First learning-augmented guarantees for time-decay streams. Captures privacy-driven data deletion (GDPR) and recency-weighted analytics, motivating practical relevance.\n\n2) Theoretically strong results: General reduction shows any ($\\alpha$, $\\beta$)-smooth function enjoys a black-box sliding-window lift while preserving approximation and randomised guarantees; rectangle and cascaded norms benefit for free\n\n3) Experimental validation on real data: CAIDA traces (30 M IPs) show AMSA (augmented AMS) keeps relative error ≤1.2× across window sizes while AMS drifts up to 2.3×. Distribution-shift experiment on synthetic data demonstrates >2× error gap between SSA and SS when stream distribution changes, confirming robustness claim. Code released aiding reproducibility.", "weaknesses": "1) Limited empirical scope: Only l2 and l3 norms are evaluated; rectangle and cascaded-norm algorithms lack any implementation or micro-benchmark, leaving practical impact uncertain.\n\n2) Expand empirical coverage: Include CPU-time and peak RAM tables for each dataset to confirm the claimed overhead.\n\n3) Strengthen statistical reporting: Release full parameter files (hash seeds, repetition counts, bucket sizes) to facilitate exact reproduction.", "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": "", "extra_scores": {}}, {"review_id": "lW0Qtlsmd2", "reviewer": "Reviewer_szXb", "summary": "This paper presents a learning-augmented framework for frequency moment estimation, applicable to both sliding-window and time-decay models. The authors design and employ a suffix-compatible heavy-hitter oracle tailored for time-decay settings. In the sliding-window case, the proposed algorithm achieves a space complexity that even meets the lower bound for streaming algorithms. Beyond sliding windows, the paper studies the more general time-decay model and provides rigorous space complexity guarantees. Experiments on both real-world and synthetic datasets demonstrate the practical efficiency of the proposed approach.", "questions": "- The proposed algorithms depend on the suffix-compatible property of the oracle. In practice, if the oracle's predictions are inaccurate, could this undermine the suffix-compatible property and compromise the guarantees on space complexity?\n- As shown in Figs. 2(c) and 4(c), increasing the sampling probability of SSA yields little improvement in accuracy. What could explain this limited effect?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The extension of learning-augmented frequency moment estimation to general time-decay settings is novel and appealing.\n- The paper provides space complexity bounds for several common estimation tasks—including $F_p$ moments, rectangular moments, and cascaded norms—under two decay models, filling an existing theoretical gap.\n- The experiments convincingly show that the learning-augmented approach significantly improves estimation accuracy under the sliding-window model.", "weaknesses": "- The experimental evaluation does not include direct comparisons with other learning-augmented sliding-window algorithms, such as Shahout et al. (2024), and lacks empirical validation in more general time-decay environments. \n- The discussion on training suffix-compatible heavy-hitter oracles is insufficient. Although the PAC learning framework and Theorem 14 address the learnability of general heavy-hitter oracles, the paper does not examine specific training strategies or conditions that guarantee the suffix-compatible property, which is crucial for ensuring correctness in time-decay models.", "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": "", "extra_scores": {}}, {"review_id": "iYOtW0pXle", "reviewer": "Reviewer_zdR7", "summary": "*I reviewed a previous version of this paper for NeurIPS'25 where I had some relatively big concerns about the technical novelty of the paper, as well as some concerns about the proof of the main theorem (which is four lines in the appendix and very sketchy, and not entirely easy to verify). Unfortunately, it seems to me that these concerns are still largely unaddressed. In addition, my (more minor) comments on parts of the paper that were mathematically unclear or imprecise have not been addressed either.  Below is my previous review of the paper with minor updates:*\n\nThe paper falls in the line of research of algorithms with predictions where algorithms are equipped with advice or predictions. Given recent developments in machine learning it is often too pessimistic to run a worst-case algorithm and not leverage predictable structures of the input. The line of research seeks to bridge algorithms and ML by obtaining provably improved algorithms with accurate predictions while also maintaining worst case guarantees.\n\nSpecifically, the paper considers $p$-moment estimation as well as sketching rectangle $F_p$ frequencies and cascaded norms in time-decay models, e.g., the sliding window model. There is an arriving stream of elements over a universe of size $n$ and a corresponding frequency vector $x$, and the goal is to maintain a small sketch of $x$ which captures important statistics of $x$ -- in this paper it's $\\ell_p$ moments for $p\\geq 2$. In the general time-decay model, there is a weight function $w$ that at any point of time $t$ weights all arrivals of each element $i$ based on how far back these arrivals occurred. The frequency of $i$ at time $t$ is the sum of these weights, and the idea is that elements that arrived very far back in time are less relevant and can get weighted less.\nAs a special case, in the sliding window model, there is a window of the last previous $W$ updates, and instead of maintaining a sketch of the full stream, we at any point of time want to be able to approximate the moments of the frequency vector corresponding to the last $W$ updates. The paper considers the well studied prediction model introduced in [HIKV'19] where the algorithm has access to a heavy-hitter oracle which can predict whether an arriving element has frequency above a certain threshold  (which depend on the problem at hand). For moment estimation, it is well-known that standard learning augmented algorithms can achieve $\\tilde O(n^{1/2-1/p})$ space while approximating  the frequency moments, which improved upon the bound of $\\tilde O(n^{1-1/2p})$ in the classic model. The paper proves similar bounds in time-decay, e.g., the sliding window model (but with worse exponential dependencies on $p$ and the approximation parameter $\\varepsilon$).\n\nOne update that has been made to the paper since I last reviewed it is a framework for general time-decay models  which requires a generalization of the idea of $(\\alpha,\\beta)$-smooth functions from Braverman and Ostrovsky [BOO7].  Albeit the proofs in the appendix are somewhat sketchy, this is a nice addition to the paper since my last review.", "questions": "*Mainly copied from my NeurIPS review.*\n\nl98-l99: Can such formal guarantees be given? What are the challenges in proving such formal guarantees. This seems relevant.\n\nl267-l269: The notation $x_A$ is not properly defined.\n\nl278-l279:  This property is not clear when frequencies of stream elements can be negative. I would have liked a more precise discussion of which model you consider.\n\nAlgorithm 1: Notation like $ALG^k\\geq something$ is not really meaningful, and I suppose it refers to the output of the algorithm. Also, the algorithm doesn't describe how it returns estimates, e.g. of a moment.\n\nl781-786: This is (still) very sketchy and I don't know what sentences like \"as long as we could maintain the smooth histogram\" and \"... every copy of the algorithm can get the oracle advice it needs,...\" means in a formal sense. While you mention it, it is also (still) not clear to me how suffix-compatibility is actually used. This is essentially the proof of the main result of the paper, and needs to be written in a way that can be verified.\n\nTheorem 3 is for general decay models, but when you prove the following many theorems on page 20, it is unclear how you use polynomial and exponential decay.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Moment estimation is an important problem sketching problem and I find it well-motivated in the learning augmented-framework. It is well-studied in several past works. The sliding window model is also natural since it captures the idea that we may often be more interested in statistics of the most recent data. I like specifically about the paper, that they generalize the framework of Braverman and Ostrovsky [BOO7] to more general time-decay functions.", "weaknesses": "(1) I found that the paper lacked technical novelty. It heavily relies on the smooth histogram algorithm from Braverman and Ostrovsky [BOO7] which turns a classic sketching algorithm into an algorithm in the sliding window model with little overhead. The paper shows that the learning augmented algorithm from [JLL+20] fits the framework from [BO07] in a white-box fashion, they argue that the sliding-window algorithm from [BOO7] retains two properties captured in Proposition 1 and 2 even for the learning-augmented versions. The proof of this fact is 4 lines in the appendix (and it is quite sketchy, so additionally it was unclear to me why it is actually true). It seems to me that the rest of the paper just applies known bounds and techniques from past work. This main issue with the paper seems to be similar for $F_p$ frequencies and cascaded norms estimation, although I haven't read those parts of the appendix in detail.\n(2) While the paper does obtain a good polynomial dependence on $n$, the dependence on $\\varepsilon,p$ seem to become quite bad.\n(3) Parts of the paper is poorly written and it is hard to follow precisely what the authors are claiming. I will give details below.", "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": "", "extra_scores": {}}, {"review_id": "B7Ps2QLCZA", "reviewer": "Reviewer_oP5F", "summary": "This paper studies learning-augmented streaming algorithms under time-decay weighting, including polynomial decay, exponential decay, and sliding-window streams. In this model, the streaming algorithm is allowed to access a suffix-compatible heavy-hitter oracle which can predict the heavy hitters of suffix streams.\n\nThe paper extends the framework of Jiang et al. (2020), which used a learned heavy-hitter oracle to improve space bounds for frequency moment estimation, to the more general time-decay setting. The authors propose a smoothness-based reduction that converts learning-augmented streaming algorithm into a learning-augmented time-decay algorithm with nearly the same asymptotic space complexity. Then they obtain: \n\n1. $F_p$ estimation: using $\\tilde{O}(n^{1/2-1/p}/\\epsilon^{4+p})$ space, matching known lower bound in the exponent $n$.\n2. Rectangular $F_p$ frequency and cascaded norms: analogous extensions of Jiang et al. (2020) to time-decay models.", "questions": "Can the suffix-compatible oracle assumption be relaxed, e.g. learned online during streaming (without access to full suffixes and without prior knowledge of the stream length)?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. It is well-motivated to study the learning-augmented streaming under time-decay weighting.\n2. The paper proposes a unified reduction framework from streaming to time-decay models, and obtains near optimal algorithm for fundamental frequency estimation problems.", "weaknesses": "1. Major concern: the paper assumes the existence of a suffix-compatible heavy-hitter oracle but provides few details in the main context on how such an oracle is learned or implemented in practice. It is unclear whether the oracle requires prior knowledge of the stream length $m$, whether it learns online or offline, and what access it has to the stream data.\n2. Minor issues: \n   1. The citation command \\citep and \\citet are used inpropritory at times, e.g. line 90.\n   2. In the equation of line 197, \"$i_{t}=i$\" => \"$i_{t'}=i$\".", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)