Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

David P. WoodruffCarnegie Mellon University.
E-mail<EMAIL_ADDRESS>
Samson ZhouCarnegie Mellon University.
E-mail<EMAIL_ADDRESS>
In the adversarially robust streaming model, a stream of elements is presented to an algorithm and is allowed to depend on the output of the algorithm at earlier times during the stream. In the classic insertion-only model of data streams, Ben-Eliezer et al. (PODS 2020, best paper award) show how to convert a non-robust algorithm into a robust one with a roughly $1/\varepsilon$ factor overhead. This was subsequently improved to a $1/\sqrt{\varepsilon}$ factor overhead by Hassidim et al. (NeurIPS 2020, oral presentation), suppressing logarithmic factors. For general functions the latter is known to be best-possible, by a result of Kaplan et al. (CRYPTO 2021). We show how to bypass this impossibility result by developing data stream algorithms for a large class of streaming problems, with no overhead in the approximation factor. Our class of streaming problems includes the most well-studied problems such as the $L_2$-heavy hitters problem, $F_p$-moment estimation, as well as empirical entropy estimation. We substantially improve upon all prior work on these problems, giving the first optimal dependence on the approximation factor.

As in previous work, we obtain a general transformation that applies to any non-robust streaming algorithm and depends on the so-called twist number. However, the key technical innovation is that we apply the transformation to what we call a difference estimator for the streaming problem, rather than an estimator for the streaming problem itself. We then develop the first difference estimators for a wide range of problems. Our difference estimator methodology is not only applicable to the adversarially robust model, but to other streaming models where temporal properties of the data play a central role. To demonstrate the generality of our technique, we additionally introduce a general framework for the related sliding window model of data streams and resolve longstanding open questions in that model, obtaining a drastic improvement from the previous $1/\varepsilon^{2+p}$ dependence for $F_p$-moment estimation for $p \in [1,2]$ and integer $p > 2$ of Braverman and Ostrovsky (FOCS, 2007), to the optimal $1/\varepsilon^2$ bound. We also improve the prior $1/\varepsilon^3$ bound for $p \in [0,1)$, and the prior $1/\varepsilon^4$ bound for empirical entropy, obtaining the first optimal $1/\varepsilon^2$ dependence for both of these problems as well. Qualitatively, our results show there is no separation between the sliding window model and the standard data stream model in terms of the approximation factor.

§ INTRODUCTION

Efficient computation of statistics over large datasets is increasingly important.
Such datasets include logs generated from internet traffic, IoT sensors, financial markets, and scientific observations.
To capture these applications, the streaming model defines an underlying dataset through updates that arrive sequentially and describe the evolution of the dataset over time.
The goal is to approximate statistics of the input using memory, i.e., space complexity, that is significantly sublinear in the input size $n$, while only making a single pass over the data.

Adversarially robust streaming model.
In the adversarially robust streaming model, the input is adaptively chosen by an adversary who is given unlimited computational resources and may view the outputs of the streaming algorithm at previous times in the stream.
The goal of the adversary is to design the input to the streaming algorithm so that the algorithm eventually outputs an incorrect answer.
One application of the model is to recommendation systems, where a large set of possible items arrives in a data stream and the goal is to produce a list of fixed size, i.e., a cardinality constraint, so as to maximize a predetermined function, e.g., a submodular function representing a user's utility [22, 67, 6].
However, the set of items might subsequently be modified by an honest user based on their personal preferences, e.g., to avoid items they already have.
Similar notions of adversarial robustness have been the recent focus of a line of work [57, 69, 48, 77, 21, 75, 26, 17, 46].

The work of [49] showed that no linear sketch can approximate the $L_2$-norm within a polynomial multiplicative factor against such an adversary.
Linear sketching is a widely used technique for turnstile streams, in which positive and negative updates are possible.
The work of [49] also connected their result to differential privacy, showing that they rule out algorithms for answering more than a polynomial number of queries while satisfying differential privacy.

On the positive side, [17] gave a general framework in the adversarially robust setting when the updates are in the standard insertion-only model of data streams, meaning that previous stream updates cannot later be deleted.
In this model, there is an underlying vector $x$ that is initialized to $0^n$ and at the $t$-th time step, it receives an update of the form $x_i \leftarrow x_i + \Delta_t$ for some positive integer $\Delta_t$.
It is promised that all cooordinates of $x$ are bounded by a polynomial in $n$ throughout the stream.
The framework of [17] gives algorithms for a number of problems, and for this discussion, we illustrate the shortcomings of their results for the $F_p$-moment estimation problem.
Here, the goal is to output a number that is a multiplicative $1 \pm \varepsilon$ approximation to $F_p(x) = \sum_{i=1}^n x_i^p$.
The work of [17] achieves an adversarially robust algorithm with $\tO{\frac{\log n}{\eps^3}}$ bits[We use the $\tO{\cdot}$ notation to omit logarithmic terms, i.e., $\tO{f}=\O{f\polylog f}$ for any function $f$ of $n$ and $\frac{1}{\eps}$.] of memory for $p\in[0,2]$ and $\tO{\frac{n^{1-2/p}}{\eps^3}}$ bits for $p > 2$.

Subsequently, [46] improved the space dependence to $\tO{\frac{\log^4 n}{\eps^{2.5}}}$ for $F_p$-moment estimation for $p\in[0,2]$ and $\tO{\frac{n^{1-2/p}}{\eps^{2.5}}}$ for $p>2$.
Their technique showed that differential privacy can be used to protect the internal randomness of algorithms against the adversary to a useful extent, despite the general negative results concerning differential privacy pointed out by [49] for linear sketches.

The algorithms above should be compared to the best known algorithms in the standard non-robust data stream model, which achieve $\O{\frac{\log n}{\eps^2}}$ memory for $p \in [0,2]$ [61, 60, 59] and $\tO{\frac{n^{1-2/p}}{\varepsilon^2}}$ memory for $p > 2$ [41, 43].
Notably, the dependence on the approximation factor $\varepsilon$, is $1/\eps^{2.5}$ in the robust setting but only $1/\eps^2$ in the non-robust setting.
Similar gaps exist for the important $L_2$-heavy hitters problem, where the space bounds of [17] and [46] are $\tO{\frac{\log n}{\varepsilon^3}}$ and $\tO{\frac{\log^4 n}{\varepsilon^{2.5}}}$ bits, respectively, while the non-adversarial insertion-only streaming space complexity is $\tO{\frac{\log n}{\varepsilon^2}}$ bits [9, 8].
The study on the dependence of the approximation parameter $\varepsilon$ for problems in the data stream literature has a long and rich history, including work on frequency moments and cascaded norms [66, 87], multipass and distributed functional monitoring [84, 85, 45, 86], low rank approximation [33, 83, 25], sparse recovery [79, 74], subspace embeddings [72], and support vector machines [1].
As discussed in [52, 82], for reasonable values of $n$ and $\varepsilon$ (e.g., $n = 2^{32}$ and $\varepsilon = 10\%$), the storage bound of a streaming algorithm is often dominated by the polynomial dependence on $1/\varepsilon$.
If one wants even better approximation quality, e.g., $\varepsilon = 1\%$, then a large polynomial dependence on $1/\varepsilon$ constitutes a severe drawback of existing algorithms.
In [14], for distinct element estimation it was explicitly posed if one could obtain a $\frac{1}{\varepsilon} \cdot \textrm{polylog}(n)$ space algorithm or if an $\Omega(1/\varepsilon^2)$ space algorithm was best possible.
This was later resolved in [52, 82] for the non-robust data stream model.
However, we are now faced with the analogous question for adversarially robust algorithms, not just for distinct element estimation, but for almost all streaming problems of interest:

Do we need to pay a polynomial in $\frac{1}{\varepsilon}$ overhead in the adversarially robust model for all of the well-studied streaming problems above?

Recent work by [58] gave a further separation between adversarial and oblivious streams by introducing a streaming problem for which there exists an oblivious streaming algorithm that uses only polylogarithmic space but any adversarially-robust streaming algorithm must use polynomial space.
In fact, they show that in general there must be an $\Omega(\sqrt{\lambda})$ blowup in the memory required of an adversarially robust algorithm over its non-robust counterpart, where $\lambda$ is the so-called flip number and indicates roughly how many times a function can change by a $(1+\varepsilon)$-factor; for a more precise description see sec:prelim.
As the flip number is $\Omega(1/\varepsilon)$ for insertion streams, while the optimal non-robust streaming algorithm has a $\Theta(1/\varepsilon^2)$ dependence, this suggests that one does need to pay $\Omega(1/\varepsilon^{2.5})$ space to solve the above streaming problems in the adversarially robust model.
Surprisingly, we will show this is not the case, and the lower bound of [58] does not apply to all of the well-studied streaming problems above.

Sliding window model.
A related data stream model where temporal properties play a central role is the sliding window model.
The streaming model does not capture applications in which recent data is considered more accurate and important than data that arrived prior to a certain time.
For a number of applications [7, 68, 78, 81], the unbounded streaming model has performance inferior to the sliding window model [35], where the underlying dataset consists of only the $W$ most recent updates in the stream, for a parameter $W>0$ that denotes the window size of the active data.
All updates before the $W$ most recent updates are expired, and the goal is to aggregate information about the active data using space sublinear in $W$.
Observe that for $W>m$ for a stream $u_1, u_2, \ldots, u_m$ of items of length $m$, the active data is the entire stream, and for an underlying vector $x$ of the data, we have $x_i=|\{t\,:\,u_t=i \textrm{ and } t\ge m-W+1\}|$ for each $i\in[n] = \{1, 2, \ldots, n\}$.
Thus, the sliding window model is a generalization of the streaming model where $W$ can be less than $m$.
It is especially relevant in time-sensitive applications such as network monitoring [30, 27, 32], event detection in social media [76], and data summarization [31, 37], and has been subsequently studied in a number of additional settings [64, 65, 23, 36, 24, 19, 20, 13, 10, 12].

Returning to our running example of $F_p$-moment estimation, the best known algorithms in the sliding window model have a $1/\eps^{2+p}$ dependence on the approximation factor $\eps$, for every $p \geq 1$, in their space complexity [23].
Surprisingly, there has been no progress on this problem since then.
Since the sliding window model generalizes insertion-only streams, which have $F_p$-moment estimation algorithms with a $\O{\frac{1}{\eps^2}}$ dependence on $\eps$, the longstanding open question is:

Do we need to pay a polynomial in $\frac{1}{\varepsilon}$ overhead in the sliding window model for well-studied streaming problems, such as estimating the frequency moments?

The work of [23] introduces the smooth histogram approach for solving problems in the sliding window model.
For a function $f$, given adjacent substreams $A$, $B$, and $C$, an $(\alpha,\beta)$-smooth function demands that if $(1-\beta)f(A\cup B)\le f(B)$, then $(1-\alpha)f(A\cup B\cup C)\le f(B\cup C)$ for some parameters $0<\beta\le\alpha<1$.
Intuitively, once a suffix of a data stream becomes a $(1\pm\beta)$-approximation for a smooth function, then it is always a $(1\pm\alpha)$-approximation, regardless of the subsequent updates that arrive in the stream.
Here, a suffix of length $t$ of a stream is defined to be the last $t$ updates of the stream.

The workof [23] develops a general algorithm for smooth functions and shows, for example, that $F_p$-moment estimation is sufficiently smooth, resulting in a $1/\varepsilon^{2+p}$ dependence for $F_p$-moment estimation for every $p \geq 1$, a $1/\varepsilon^3$ bound for $0 < p < 1$, and a $1/\varepsilon^4$ bound for estimating the empirical entropy.
Unfortunately there are examples where this smoothness is best possible for all of these functions, suggesting that there is a gap between the sliding window model and data stream models.
Surprisingly, we will show this is not the case, and we will give the first general technique for the sliding window model that goes beyond the smooth histogram approach, which has been the standard paradigm for nearly 15 years.

§.§ Our Contributions

We show that there is no loss in $\frac{1}{\eps}$ factors, up to logarithmic factors, over the standard model of data streams for all of the aforementioned central data stream problems, in either the adversarially robust streaming model or the sliding window model.
Our results hold for $F_p$-moment estimation for $p \in [0,2]$ and integers $p > 2$, $L_2$-heavy hitters, and empirical entropy estimation, and we give a general framework that can be applied to other problems as well.

Our techniques introduce the following crucial concept, which surprisingly had not been considered for data streams before:

Given frequency vectors $u$ and $v$, an accuracy parameter $\eps>0$, a failure probability $\delta\in(0,1)$, and a ratio parameter $\gamma\in(0,1]$, a $(\gamma,\eps,\delta)$-difference estimator for a function $F$ outputs an additive $\eps\cdot F(u)$ approximation to $F(u+v)-F(u)$ with probability at least $1-\delta$, given $F(u+v)-F(u)\le\gamma\cdot F(u)$ and $F(v)\le\gamma F(u)$.

A difference estimator provides a path for obtaining an approximation algorithm, as follows:
Given a monotonic function $F$, frequency vectors $u,v_1,\ldots,v_k$, a $\left(1+\frac{\eps}{2}\right)$ multiplicative approximation to $F(u)$, and $\left(\gamma_i,\eps_i,\frac{1}{3k}\right)$-difference estimators to $F(u+v_1+\ldots+v_i)-F(u+v_1+\ldots+v_{i-1})$ for $i\in\{1,\ldots,k\}$ (and $v_0=0$) such that $\prod_{i=1}^k(1+\gamma_i)\le 2$ and $\sum_{i=1}^k\eps_i\le\frac{\eps}{4}$, then their sum gives a $(1+\eps)$-approximation to $F(u+v_1+\ldots+v_i)$ with probability at least $\frac{2}{3}$.

Moreover, even if multiple copies of the difference estimators are run simultaneously, the space dependency can still be $\frac{1}{\eps^2}$:
Suppose each $\left(\gamma_i,\eps,\frac{1}{3k}\right)$-difference estimator uses space $\frac{\gamma_i}{\eps^2}\cdot S$ and $S$ is a monotonic function in $k:=\O{\log n}$, $\frac{1}{\eps_i}$, and the input size.
If $\gamma_i\le\frac{1}{2^i}$ and there are $N_i\le 2^i$ instances of $\left(\gamma_i,\eps,\frac{1}{3k}\right)$-difference estimators, then the total space is at most $\O{\frac{S\log n}{\eps^2}}$.

While one can construct a difference estimator for $F(v+w_t)-F(v)$ by using separate sketches for $F(v+u)$ and $F(u)$, this defeats the whole point!
Indeed, while approximation to $F(v+u)$ and to $F(u)$ with additive error $\frac{\eps}{2}\cdot F(v+u)$ can be used to provide an approximation to $F(v+u)-F(u)$ with additive error $\frac{\eps}{2}\cdot F(v+u)$, the space required for these approximations is simply the space required for $(1+\eps)$-approximations, so we are not utilizing the property that $F(v+u)-F(u)\le\gamma\cdot F(u)$ to obtain more space efficient algorithms.
Thus, we first need to develop difference estimators for all of the above problems. It turns out that difference estimators
for the frequency moments $F_p$ can be used as building blocks for many other streaming problems, so these will be our focus. We show:

There exist difference estimators for the $F_p$-moment problem for $p\in[0,2]$ and integers $p>2$.
In particular, the difference estimator uses:

* $\O{\frac{\gamma}{\eps^2}\left(\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta}\right)+\log n}$ bits of space for the distinct elements problem, $F_0$.

(See lem:diff:est:F0.)

* $\O{\frac{\gamma\log n}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$ bits of space for $F_2$.
(See lem:diff:est:F2.)

* $\O{\frac{\gamma^{2/p}\log n}{\eps^2}(\log\log n)^2\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$ bits of space for $F_p$ with $p\in(1,2)$.
(See lem:diff:est:Fp:smallp.)

* $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}$ bits of space for $F_p$ for integer $p>2$.
(See lem:diff:est:Fp:largep).

We define the quantity $1+\frac{\eps}{\gamma}$ to be the effective accuracy of the difference estimator, since it effectively serves as the multiplicative error if $F(v+u)-F(u)=\gamma\cdot F(u)$.
The key property of our $(\gamma,\eps,\delta)$-difference estimators that we shall exploit is that their space complexity has dependency $\frac{\gamma^C}{\eps^2}$ for some constant $C\ge 1$.
For example, for $\gamma=\O{\eps}$, the space dependence is only $\frac{1}{\eps}$, which allows us to use $\O{\frac{1}{\eps}}$ copies of the $(\gamma,\eps,\delta)$-difference estimators.
Intuitively, because the difference is small, e.g., $\eps\cdot F(v)$, we can avoid using a $\frac{1}{\eps^2}$ space dependence to get an additive $\eps\cdot F(v)$ approximation to the difference.
We develop several unrelated corollaries along the way which may be of independent interest, e.g., we show in thm:smallp:strong:track that Li's geometric mean estimator gives strong-tracking for $F_p$-moment estimation for $p\in(0,2)$, offering an alternative to the algorithm of [11]. We also derandomize our algorithm using a generalization of a pseudorandom generator that fools half-space queries [42, 56], and the argument may be useful for other models where temporal properties play a role.

Using our concept of difference estimators, we develop quite general frameworks for both the adversarially robust streaming model and the sliding window model.

§.§.§ Our Results for Adversarially Robust Streams.

We first present a space-efficient framework for adversarially robust streaming algorithms, provided there exists a corresponding difference estimator and strong tracker, i.e., a streaming algorithm that is correct at all times in the stream (see, e.g., [9, 8, 11, 18] for examples of strong trackers).

Let $\eps,\delta\in(0,1)$ be given constants and $F$ be a monotonic function with $(\eps,m)$-twist number $\lambda$.
Suppose there exists a $(\gamma,\eps,\delta)$-difference estimator that uses space $\frac{\gamma}{\eps^2} S_F(m,\delta,\eps)$ and a strong tracker for $F$ that uses space $\frac{1}{\eps^2} S_F(m,\delta,\eps)$, where $S_F$ is a monotonic function in $m$, $\frac{1}{\delta}$, and $\frac{1}{\eps}$.
Then there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$ approximation to $F$ that succeeds with constant probability and uses $\tO{\frac{\lambda}{\eps}\cdot S_F(n,\delta',\eps)}$ space, where $\delta'=\O{\frac{1}{\poly\left(\lambda,\frac{1}{\eps}\right)}}$.
(Informal, see thm:framework:flip.)

The space required for our algorithms is parameterized by the $(\eps,m)$-twist number $\lambda$, which captures the number of times a given function on a subsequent substream is at an $\epsilon$ fraction of the given function on the prefix (see def:twistnumber for a formal definition).
Thus the twist number is related to the flip number $\psi$ used in [17, 46], which captures the number of times a given function on a stream changes by a factor of $(1+\eps)$ (see def:flipnumber for a formal definition) – indeed, for insertion-only streams, these two quantities are equivalent.
[58] recently showed a lower bound of a $\sqrt{\lambda}$ space blow-up in insertion-only streams for particular problems; our results are the first to show that this $\sqrt{\lambda}$ overhead can be bypassed for a large class of important streaming problems, such as moment estimation, heavy hitters, and entropy, since $\lambda=\O{\frac{1}{\eps}\log n}$ in these problems.
frame:robust breaks the lower bounds of [58] by requiring the existence of a difference estimator, which does not hold for their lower bound instance.

Often, $\lambda$ is bounded by $\O{\frac{1}{\eps}\log n}$ for insertion-only streams of length $m \leq \poly(n)$.
For a variety of specific problems, we can further optimize our results to altogether avoid the $\log n$ overhead implied by frame:robust:

frame:robust can be further optimized to give an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation to:

* The distinct elements problem, $F_0$, on insertion-only streams, using $\tO{\frac{1}{\eps^2}+\frac{1}{\eps}\log n}$ bits of space.

(See thm:robust:opt:F0.)

* The $F_p$-moment estimation problem for $p\in(0,2]$ on insertion-only streams, using $\tO{\frac{1}{\eps^2}\log n}$ bits of space.

(See thm:robust:opt:F2 and thm:robust:opt:Fp:smallp.)

* The Shannon entropy estimation problem on insertion-only streams, using $\tO{\frac{1}{\eps^2}\log^3 n}$ bits of space.
(See thm:robust:entropy.)

* The $F_p$-moment estimation problem for integer $p>2$ on insertion-only streams, using $\tO{\frac{1}{\eps^2}n^{1-2/p}}$ bits of space.

(See thm:robust:opt:Fp:largep.)

* The $L_2$-heavy hitters problem on insertion-only streams, using $\tO{\frac{1}{\eps^2}\log n}$ bits of space.

(See thm:robust:opt:HH.)

* The $F_p$-moment estimation problem on turnstile streams, using $\tO{\frac{\lambda}{\eps}\log^2 n}$ bits of space for $p\in[0,2]$.

(See thm:robust:turnstile:Fp.)

|c|c|c|c|Problem     [17] Space     [46] Space     Our Result
Distinct Elements     $\tO{\frac{\log n}{\eps^3}}$     $\tO{\frac{\log^4 n}{\eps^{2.5}}}$     $\tO{\frac{1}{\eps^2}+\frac{\log n}{\eps}}$
$F_p$ Estimation, $p\in(0,2]$     $\tO{\frac{\log n}{\eps^3}}$     $\tO{\frac{\log^4 n}{\eps^{2.5}}}$     $\tO{\frac{\log n}{\eps^2}}$

Shannon Entropy     $\tO{\frac{\log^6 n}{\eps^5}}$     $\tO{\frac{\log^4 n}{\eps^{3.5}}}$     $\tO{\frac{\log^3 n}{\eps^2}}$
$L_2$-Heavy Hitters     $\tO{\frac{\log n}{\eps^3}}$     $\tO{\frac{\log^4 n}{\eps^{2.5}}}$     $\tO{\frac{\log n}{\eps^2}}$
$F_p$ Estimation, integer $p>2$     $\tO{\frac{n^{1-2/p}}{\eps^3}}$     $\tO{\frac{n^{1-2/p}}{\eps^{2.5}}}$     $\tO{\frac{n^{1-2/p}}{\eps^2}}$
$F_p$ Estimation, $p\in(0,2]$, dynamic streams     $\tO{\frac{\psi\log^2 n}{\eps^2}}$     $\tO{\frac{\log^3 n\sqrt{\psi\log n}}{\eps^2}}$     $\tO{\frac{\lambda\log^2 n}{\eps}}$

Adversarially robust streaming algorithms using optimized version of frame:robust. $\psi$ is the flip number for [17, 46] and $\lambda$ is the twist number for our result.

The results achieved by thm:main:adv:robust achieve the optimal $\tO{\frac{1}{\eps^2}}$ dependence for these fundamental problems, and match the corresponding best non-adversarial algorithms in the insertion-only streaming model up to polylogarithmic factors.
In particular, our results show that no loss in $\frac{1}{\eps}$ factors is necessary in the adversarially robust model.

For turnstile streams with twist number $\lambda$, we achieve dependence $\tO{\frac{\lambda\log^2 n}{\eps}}$, which improves upon the result of [17] if $\lambda=\psi$ for the flip number $\psi$.
For $\lambda=\psi=o\left(\frac{\log^3 n}{\eps^2}\right)$, our result also improves upon the algorithm of [46].
We summarize these results in fig:robust:results.

§.§.§ Our Results for the Sliding Window Model.

We next modify the difference estimators from thm:diff:est to develop a general framework for algorithms in the sliding window model, substantially improving upon the smooth histogram framework, and resolving longstanding questions on moment and entropy estimation algorithms in this model.
Existing moment and entropy estimation sliding window algorithms crucially rely on the concept of smoothness, discussed above, which quantifies the ability of a suffix of a stream to diverge from the entire stream under worst-case updates to the stream; see sec:sliding for a formal definition.
A framework of [23] converts streaming algorithms into sliding window algorithms with an overhead in terms of the smoothness of the function to be approximated, provided that the function is monotonic, polynomially bounded, and smooth.
We first give a framework showing that the space complexity of these functions need not depend on the smoothness parameter.

Our framework again makes use of difference estimators, but in this case they are what we call
suffix pivoted difference estimators. These difference estimators handle streams in which the “larger”
frequency vector arrives after the “smaller” frequency vector,
whereas the opposite is true for the difference estimators required for the adversarially robust streaming model.
This is because in the sliding window model, we use difference estimators to
“subtract off” terms that have expired, whereas in the adversarially
robust streaming model we use difference estimators to “add in” terms that have recently appeared.
Consequently, we must now develop suffix pivoted difference estimators for a wide range of problems, though fortunately
they turn out to be related to the difference estimators we have already developed. A more formal
description is given below, but the general theorem for our framework is given here:

Let $\eps,\delta\in(0,1)$ be constants and $F$ be a monotonic and polynomially bounded function that is $(\eps,\eps^q)$-smooth for some constant $q\ge 0$.
Suppose there exists a $(\gamma,\eps,\delta)$-suffix pivoted difference estimator that uses space $\frac{\gamma}{\eps^2} S_F(m,\delta,\eps)$ and a streaming algorithm for $F$ that uses space $\frac{1}{\eps^2} S_F(m,\delta,\eps)$, where $S_F$ is a monotonic function in $m$, $\frac{1}{\delta}$, and $\frac{1}{\eps}$.
Then there exists a sliding window algorithm that outputs a $(1+\eps)$ approximation to $F$ that succeeds with constant probability and uses $\frac{1}{\eps^2}\cdot S_F(m,\delta',\eps)\cdot\poly\left(\log m,\log\frac{1}{\eps}\right)$ space, where $\delta'=\O{\frac{1}{\poly(m)}}$.
(Informal, see thm:sw:framework.)

We can also optimize frame:sw to improve logarithmic factors, and obtain the following results for important streaming problems:

Let $\eps,\delta>0$ be given.
Then frame:sw can be optimized to obtain sliding window algorithms that output a $(1+\eps)$-approximation to:

* The $F_p$-moment estimation problem for $p\in(0,2]$, using $\tO{\frac{1}{\eps^2}\log^3 n}$ bits of space.
(See thm:sliding:main.)

* The $F_p$-moment estimation problem for integers $p>2$, using $\tO{\frac{1}{\eps^2}\,n^{1-2/p}}$ bits of space.
(See thm:sliding:largep.)

* The Shannon entropy estimation problem, using $\tO{\frac{1}{\eps^2}\log^5 n}$ bits of space.
(See thm:sw:entropy.)

Thus, our results show that no loss in $\frac{1}{\eps}$ factors is necessary in the sliding window model, bypassing previous
algorithms that were limited by the smooth histogram framework.
The previous framework of [23] has an $\tO{\frac{\log^3 n}{\eps^3}}$ space dependence for $p\in(0,1]$, a $\tO{\frac{\log^3 n}{\eps^{2+p}}}$ space dependence for $p\in(1,2]$, an $\tO{\frac{n^{1-2/p}}{\eps^{2+p}}}$ space dependence for $p>2$, and an $\tO{\frac{\log^5 n}{\eps^4}}$ space dependence for entropy estimation using known techniques [47].
We note that there are specialized algorithms for the distinct elements and $L_2$-heavy hitters prolems in the sliding window model that also achieve the optimal dependence on the approximation factor [13], so we do not state our results for those problems in this model. We summarize our sliding window model results in fig:sliding:results.

|c|c|c|Problem     [23] Space     Our Result
$L_p$ Estimation, $p\in(0,1)$     $\tO{\frac{\log^3 n}{\eps^3}}$     $\tO{\frac{\log^3 n}{\eps^{2}}}$
$L_p$ Estimation, $p\in(1,2]$     $\tO{\frac{\log^3 n}{\eps^{2+p}}}$     $\tO{\frac{\log^3 n}{\eps^{2}}}$
$L_p$ Estimation, integer $p>2$     $\tO{\frac{n^{1-2/p}}{\eps^{2+p}}}$     $\tO{\frac{n^{1-2/p}}{\eps^{2}}}$
Entropy Estimation     $\tO{\frac{\log^5 n}{\eps^4}}$     $\tO{\frac{\log^5 n}{\eps^{2}}}$

Sliding window algorithms using optimized version of frame:sw.

§.§ Overview of Our Techniques

Given a function $F$ and a frequency vector $v$ implicitly defined through a data stream, we first suppose there exists a $(\gamma,\eps,\delta)$-difference estimator $\calB$ for $F$ and a streaming algorithm $\calA$ that gives a $(1+\eps)$-approximation to $F(u)$.
For the purposes of the following discussion, and to build intuition, it suffices to assume that the space dependence on $\eps$ for $\calB$ and $\calA$ is $\tO{\frac{1}{\eps^2}}$; we shall thoroughly describe our difference estimators for specific functions $F$ below.

Stitching together sketches.
We first describe our new sketch stitching paradigm that breaks down the stream into contiguous blocks of updates, which can then be combined to approximate $F(v)$ as in the proof of frame:stitch.

Observe that $F(v)=F(u)+(F(v)-F(u))$ for any frequency vector $u$.
Similarly, $F(v)=F(u_1)+\sum_{k=1}^{\beta} (F(u_{k+1})-F(u_k))$ for any frequency vectors $u_1,\ldots,u_{\beta}$, provided that $v=u_{\beta+1}$.
Hence, if we had $(1+\eps)$-approximations to $F(u_1)$ and each of the differences $F(u_{k+1})-F(u_k)$, then we could add these estimates to obtain a $(1+\eps)$-approximation to $F(v)$.
In particular, if we view $u_1,\ldots,u_{\beta}$ as the frequency vectors induced by the prefixes of the stream of length $t_1<\ldots<t_{\beta}$, respectively, then we can view the approximation to $F(u_1)$ and each $F(u_{k+1})-F(u_k)$ as a sketch of how much a consecutive block of updates in the stream contributes to $F$.
Here, recall that a prefix and suffix of length $t$ of a stream are respectively defined to be the first and last $t$ updates of the stream.
The difference estimator $\calB$ will be used to sketch each difference $F(u_{k+1})-F(u_k)$ and $\calA$ will be used to sketch $F(u_1)$.
We can then “stitch” the value of $F$ on the stream by adding the estimates of each sketch, as in the proof of frame:stitch, where a much weaker additive error suffices for approximating each of these differences.
Observe that the frequency vectors $u_1,\ldots,u_{\beta}$ are unconstrained in this setting; we now describe a natural choice for these frequency vectors based on their contributions to the value of $F$ on the stream.

Granularity change.
Suppose $v \succeq u$, that is, for all $j$, $v_j \geq u_j \geq 0$. Let $i$ be the smallest positive integer such that $F(v)\le 2^i$, and let $t$ be the first time for which $F(u)\ge 2^{i-1}$ for the frequency vector $u$ induced by the prefix of the stream of length $t$.
Since $F(v)-F(u)\le\frac{1}{2}\cdot F(v)$, the sum of a $\left(1+\frac{\eps}{2}\right)$-approximation to $F(u)$ and a $(1+\eps)$-approximation to $F(v)-F(u)$ is a $(1+\eps)$-approximation to $F(v)$.

More generally, suppose we break down the stream into the earliest times $t_1,t_2,\ldots,t_\beta$ for which the corresponding frequency vectors $u_1,u_2,\ldots,u_\beta$ induced by the prefix of the stream of lengths $t_1,t_2,\ldots,t_\beta$, respectively, satisfy $F(u_1+\ldots+u_i)\ge\left(\frac{1}{2}+\ldots+\frac{1}{2^i}\right)\cdot F(v)$ for each $i\in[\beta]$.
Then if we have a $\left(1+\frac{2^k\eps}{\beta}\right)$-approximation to $F(u_{k+1})-F(u_k)$ for each $k\in[\beta]$, where we use the convention that $v=u_{\beta+1}$, then their sum is a $(1+\eps)$-approximation to $F(v)$.
Intuitively, $F(u_{k+1})-F(u_k)$ is at most $\frac{1}{2^k}\cdot F(v)$, so we only require a $\left(1+\frac{2^k\eps}{\beta}\right)$-approximation to $F(u_{k+1})-F(u_k)$.
For the purposes of this discussion, we informally call the difference estimator with effective accuracy $\left(1+\frac{2^k\eps}{\beta}\right)$ a level $k$ estimator.
We can thus maintain sketches of different qualities for each of these blocks of the stream and stitch together the outputs to estimate $F(v)$.

Finally, note that for $\beta$ roughly equal to $\log\frac{1}{\eps}$, we have $F(u_{\beta+1})-F(u_\beta)=\O{\eps}\cdot F(v)$.
Thus even if we always output zero for the level $\beta$ estimator, we can incur at most an additive error of $\O{\eps}\cdot F(v)$.
Hence, it suffices to set $\beta$ to be roughly $\log\frac{1}{\eps}$.
We stress this is not a hierarchical blocking strategy to organize existing sketches - the sketches in the hierarchy are not sketches of the function $F$ applied to a vector. That is, we are not sketching the difference $v-u$ and estimating $F(v-u)$, but rather we are sketching $u$ and $v$ to estimate $F(v)-F(u)$; sketching such differences in the required amount of space was unknown and already makes filling in a sketch at a single node in the hierarchy challenging.

We now describe applications to the adversarially robust streaming and sliding window models.

[->] (0,-1) – (9.9,-1);
at (-1,-1)Stream:;
[decorate,decoration=brace] (9.9,-1.1) – (0,-1.1);
at (5,-1.3)$F(v)$;

[shading=radial, inner color = white, outer color = green!50!, opacity=1] (0,0.25) rectangle+(6,0.25);
(0,0.25) rectangle+(6,0.25);
[decorate,decoration=brace] (0,0.6) – (6,0.6);
at (3,1.1)Streaming algorithm,;
at (3,0.75)accuracy $\eps$;
[decorate,decoration=brace] (6,-0.1) – (0,-0.1);
at (3,-0.5)$F(u_1)$;

[shading=radial, inner color = white, outer color = red!50!, opacity=1] (6,0.25) rectangle+(2,0.25);
(6,0.25) rectangle+(2,0.25);
[decorate,decoration=brace] (6,0.6) – (8,0.6);
at (7,1.1)Difference estimator,;
at (7,0.75)accuracy $2\eps$;
[decorate,decoration=brace] (8,-0.1) – (6,-0.1);
at (7,-0.5)$F(u_2)-F(u_1)$;

[shading=radial, inner color = white, outer color = red!50!, opacity=1] (8,0.25) rectangle+(1,0.25);
(8,0.25) rectangle+(1,0.25);
[decorate,decoration=brace] (8,0.6) – (9,0.6);
at (8.5,1.9)Diff. est.,;
at (8.5,1.55)acc. $4\eps$;
(8.5,1.3) – (8.5,0.8);
[decorate,decoration=brace] (9,-0.1) – (8,-0.1);
at (8.5,-0.85)$F(u_3)-F(u_2)$;
(8.5,-0.7) – (8.5,-0.25);

[shading=radial, inner color = white, outer color = red!50!, opacity=1] (9,0.25) rectangle+(0.5,0.25);
(9,0.25) rectangle+(0.5,0.25);
[decorate,decoration=brace] (9,0.6) – (9.5,0.6);
at (9.25,1.1)Diff. est.,;
at (9.25,0.75)acc. $8\eps$;
[decorate,decoration=brace] (9.5,-0.1) – (9,-0.1);
at (9.25,-0.5)$F(u_4)-F(u_3)$;

[shading=radial, inner color = white, outer color = red!50!, opacity=1] (9.5,0.25) rectangle+(0.4,0.25);
(9.5,0.25) rectangle+(0.4,0.25);
[decorate,decoration=brace] (9.5,0.6) – (9.9,0.6);
at (9.7,1.9)Diff. est.,;
at (9.7,1.55)acc. $16\eps$;
(9.7,1.3) – (9.7,0.8);

Stitching together sketches and changing granularities.
The difference estimators $\calB$ are in red and the streaming algorithm $\calA$ is in green.
Observe that if $F(u_i)-F(u_{i-1})\approx\frac{1}{2^i}\cdot F(u_i)$, then the sum of the estimates is a $(1+\O{\eps})$-approximation to $F(v)$.

Robust framework challenges.
The challenge in implementing the described approach in the adversarially robust streaming model is that once the output of a subroutine is revealed to the adversary, the input can now depend on previous inputs as well as the internal randomness of any subroutine possibly learned by the adversary.
To circumvent this issue, the framework of [17] only reveals a new output when the internal estimate formed by various subroutines has increased by a power of roughly $(1+\eps)$.
Thus, [17] requires maintaining $\O{\frac{1}{\eps}\log n}$ separate algorithms and repeatedly switching to new, previously unused sketches, which is a technique called sketch switching.
Each sketch has a $\frac{1}{\eps^2}$ space dependence, for an overall $\frac{1}{\eps^3}$ space dependence, which is prohibitive.
Another technique, called computation paths in [17], instead sets the failure probability of a non-adaptive streaming algorithm to be $n^{-\O{(\log n)/\varepsilon}}$, but suffers a similar overall $\frac{1}{\eps^3}$ space dependence.

Adversarial inputs are problematic for several reasons. First, the correctness of a difference estimator can only be analyzed and ensured on a non-adaptively chosen stream. Second, for constant $k$, the level $k$ estimator handles a block of the stream that contributes a constant factor to the value of $F(v)$, and hence, the level $k$ estimator will cause the overall estimate to increase by a factor of $(1+\eps)$ multiple times, thus potentially compromising its internal randomness. We now describe how we overcome these issues and our general framework.

Framework for adversarial robustness.
We only estimate $F(u)$ to high accuracy, where $u$ is a frequency vector induced by the prefix of the stream at the first time $F(u)\ge 2^{i-1}$, for an integer $i$, and where the vector $v$ of subsequent stream updates satisfies $F(v)\le 2^i$.
We observe that before $u$ can grow to $u_1$, where recall $F(u_1) \geq \frac{1}{2} \cdot F(v)$, $u$ must first grow to a frequency vector $w_1$ for which $F(w_1)\approx(1+\eps) F(u)$.
Instead of maintaining a level $1$ estimator for $w_1$, it suffices to maintain a level $\beta$ estimator for the difference $F(w_1)-F(u)$, where $\beta=\O{\log\frac{1}{\eps}}$ as before.
That is, since $F(w_1)-F(u)$ is small, it suffices to maintain only a constant factor approximation to the difference.
Once the stream reaches the time with underlying frequency vector $w_1$, we approximate $F(w_1)$ by stitching together sketches and then discarding our sketch for $F(w_1)-F(u)$.

By similar reasoning, before $w_1$ can grow to $u_1$, it must first grow to a frequency vector $w_2$ for which $F(w_2)\approx(1+2\eps) F(u)$.
We maintain a level $\beta-1$ estimator for $F(w_2)-F(u)$, reveal the output once the stream reaches the time that induces $w_2$, and then discard our sketch since its randomness has been compromised.

It is crucial that we next consider $w_3$ to be the first frequency vector for which $F(w_3)\approx(1+3\eps) F(u)$, rather than say, for which $F(w_3)\approx(1+4\eps) F(u)$.

Indeed, if we were to use a single difference estimator to track a block of the stream in which $F$ increases from $(1+2\eps)F(u)$ to $(1+4\eps)F(u)$, then we cannot reveal the output of the difference estimator when the stream hits $(1+3\eps)F(u)$ without compromising its randomness.
However, if we do not reveal the output, then we also might no longer have a $(1+\eps)$-approximation to the value of $F$ when the prefix of the stream reaches value $(1+3\eps)F(u)$.

Therefore, let $w_3$ be the first frequency vector for which $F(w_3)\approx(1+3\eps) F(u)$.
Instead of estimating $F(w_3)-F(u)$ directly, we note that $F(w_3)-F(w_2)\approx\eps F(u)$.
Hence, we estimate $F(w_3)$ using a level $\beta$ estimator for $F(w_3)-F(w_2)$ and the previous level $\beta-1$ estimator for $F(w_2)-F(u)$.
Note we have not changed any coordinates of $w_2$, so that the level $\beta-1$ estimator remains correct for $F(w_2)-F(u)$ even though its output has been revealed.

We now see that if $w_k$ is the first frequency vector for which $F(w_k)\approx(1+k\eps) F(u)$, then we use level $j$ estimators corresponding to the nonzero bits in the binary representation of $k$.
Intuitively, the binary representation can be thought of as encoding into the correct path to stitch together sketches from a binary tree on the stream, where the stream is partitioned according to the value of each difference estimator rather than the length of the stream.
See fig:tree for an example.
It follows that we need roughly $2^{k}$ instances of the level $k$ estimator, for $k\in[\beta]$, where $\beta$ is roughly $\log\frac{1}{\eps}$.
As a level $k$ estimator requires effective accuracy roughly $\left(1+2^k\eps\right)$, we will not quite achieve a geometric series, but the total space will increase by at most $\polylog\frac{1}{\eps}$ factors.

Hence, the total dependence on $\eps$ in the space is $\tO{\frac{1}{\eps^2}}$, as desired.

[->] (0,-0.2) – (7.4,-0.2);
at (-1,-0.2)Stream:;
[decorate,decoration=brace] (7.4,-0.3) – (0,-0.3);
at (3.7,-0.5)$v$;

[shading=radial, inner color = white, outer color = green!50!, opacity=1] (0,0.25) rectangle+(4,0.25);

(4,0.25) rectangle+(1,0.25);

(5,0.25) rectangle+(1,0.25);
[shading=radial, inner color = white, outer color = red!50!, opacity=1] (6,0.25) rectangle+(1,0.25);

(7,0.25) rectangle+(1,0.25);
at (9.5,0.25+0.1)accuracy $4\eps$;

[shading=radial, inner color = white, outer color = red!50!, opacity=1] (4,0.6) rectangle+(2,0.25);

(6,0.6) rectangle+(2,0.25);
at (9.5,0.6+0.1)accuracy $2\eps$;

(4,0.95) rectangle+(4,0.25);
at (9.5,0.95+0.1)accuracy $\eps$;

The outputs of the difference estimators in red are stitched together to form an estimate for $F(v)$. The partitions of the stream are determined by the output of the difference estimators (rather than the length of the stream).

Optimized space.
It is possible to optimize the space usage of our framework using standard ideas for streams, used also in [17]:
(1) instead of maintaining $\O{\log n}$ instances of $\calA$, it suffices to maintain only $\O{\log\frac{1}{\eps}}$ instances at a given time, since we can drop a prefix of the stream if it only contributes a $\poly(\varepsilon)$ fraction towards the value of $F$
(2) if $\calB$ and $\calA$ have the strong-tracking property, then we can avoid a union bound over $\O{m}$ possible frequency vectors $u$ and $v$ and instead union bound over $\poly\left(\log n,\log\frac{1}{\eps}\right)$ instances of the algorithm.
To utilize (2), since our framework cannot use existing sketches, we need to show strong tracking holds for our difference estimators.

Sliding window framework challenges.
Recall that only the most recent $W$ updates in a stream of length $m$ form the underlying dataset in the sliding window model.
Because expirations of old updates are performed implicitly and the algorithm does not know when the stream will end, it is challenging to design algorithms in the sliding window model.

A natural approach is to adapt the smooth histogram approach discussed above [23].

The smooth histogram maintains a number of timestamps throughout the stream, along with sketches for the suffixes of the stream starting at each timestamp.
The timestamps maintain the invariant that at most three suffixes produce values that are within a $(1-\beta)$ factor of each other, since any two of the sketches always output values that are within a $(1-\alpha)$ factor afterwards.
Unfortunately, the smooth histogram incurs a very large overhead due to the smoothness parameter of the function.
For example, [23] showed that $F_p$ is $(\eps,\O{\eps^p})$-smooth for $p\ge 1$, so $\O{\frac{1}{\eps^p}\log n}$ instances of $F_p$ streaming algorithms must be maintained.
Each algorithm has space dependency $\frac{1}{\eps^2}$, for a total of $\frac{1}{\eps^{2+p}}$ dependency, which is prohibitive
for large $p$.

Another approach specifically for the $F_p$-moment estimation problem that one could try is to generalize the streaming algorithm of [53], which is based on subsampling the universe at multiple rates and using $(1+\eps)$-approximations to the heavy hitters in each subsampled level.
The challenge with this approach is that efficient heavy hitter algorithms in the sliding window model [13] do not give $(1+\eps)$-approximations to the frequency of the heavy hitters and are inherently biased due to items falling outside of a window, and so it is not clear how to produce $(1+\eps)$-approximations without incurring additional large $\O{\frac{1}{\eps}}$ factor overheads.

Framework for sliding windows.
To adapt our techniques to the sliding window model, we first observe that since prefixes of the stream may expire, we need a good approximation to the suffix of the stream rather than to the prefix.
Thus, we separately run streaming algorithms $\calA$ on various suffixes of the stream similar to the smooth histogram framework.
However, instead of maintaining separate instances of the streaming algorithm $\calA$ each time the value of $F$ on a suffix increases by a smoothness parameter, we maintain instances each time the value roughly doubles.
By a standard sandwiching argument, we maintain an instance of $\calA$ starting at some time $t_0\le m-W+1$, whose output is within a factor $2$ of the value of $F$ of the sliding window.
That is, the value of $F$ induced by the suffix of the stream starting at $t_0$ is at most twice the value of $F$ on the sliding window.
Since $\calA$ gives a $(1+\eps)$-approximation to the value of $F$ on the suffix starting at $t_0$, in order to obtain a $(1+\eps)$-approximation we then need to remove the additional contribution of the updates between times $t_0$ and $m-W+1$, the latter being the starting time of the sliding window.
Here we can again partition these elements into separate blocks based on their contribution to the value of $F$.
We can maintain separate sketches for these blocks, with varying granularities, and stitch these sketches together at the end.
See fig:sliding for intuition.

[->] (0,-0.25+0.125+0.0625) – (10,-0.25+0.125+0.0625);
at (-0.75,-0.25+0.125+0.0625)Stream:;
at (-2,-0.25+0.125+0.0625)$F(u)$;

(4.75,-0.5+0.25+0.0625) rectangle+(5.25,0.25);
at (8,-0.375-0.125)Sliding window (active elements);

[shading=radial, inner color = white, outer color = green!50!, opacity=1] (0,0.25) rectangle+(10,0.25);
(0,0.25) rectangle+(10,0.25);
at (-0.75,0.25+0.125)$F(v)$;

[shading=radial, inner color = white, outer color = green!50!, opacity=1] (5,0.5) rectangle+(5,0.25);
(5,0.5) rectangle+(5,0.25);
[shading=radial, inner color = white, outer color = green!50!, opacity=1] (7.5,0.75) rectangle+(2.5,0.25);
(7.5,0.75) rectangle+(2.5,0.25);
[shading=radial, inner color = white, outer color = green!50!, opacity=1] (8.75,1) rectangle+(1.25,0.25);
(8.75,1) rectangle+(1.25,0.25);

at (3,1.1)Streaming algorithms,;
at (3,0.75)accuracy $\eps$;

at (-0.75,-1+0.125)$F(v)-F(u_1)$;
[shading=radial, inner color = white, outer color = red!50!, opacity=1] (0,-1) rectangle+(2.5,0.25);

(2.5,-1) rectangle+(2.5,0.25);

at (-0.85,-1.25+0.125)$F(u_1)-F(u_2)$;

(0,-1.25) rectangle+(1.25,0.25);

(1.25,-1.25) rectangle+(1.25,0.25);
[shading=radial, inner color = white, outer color = red!50!, opacity=1] (2.5,-1.25) rectangle+(1.25,0.25);

(3.75,-1.25) rectangle+(1.25,0.25);

at (-0.85,-1.5+0.125)$F(u_2)-F(u_3)$;

(0,-1.5) rectangle+(0.625,0.25);

(0.625,-1.5) rectangle+(0.625,0.25);

(0.625*2,-1.5) rectangle+(0.625,0.25);

(0.625*3,-1.5) rectangle+(0.625,0.25);

(0.625*4,-1.5) rectangle+(0.625,0.25);

(0.625*5,-1.5) rectangle+(0.625,0.25);
[shading=radial, inner color = white, outer color = red!50!, opacity=1] (0.625*6,-1.5) rectangle+(0.625,0.25);

(0.625*7,-1.5) rectangle+(0.625,0.25);

at (8.5,-1.25+0.1)Difference estimators,;
at (6.5,-1+0.1)Accuracy $2\eps$;
at (6.5,-1.25+0.1)Accuracy $4\eps$;
at (6.5,-1.5+0.1)Accuracy $8\eps$;

[shading=radial, inner color = white, outer color = blue!50!, opacity=1] (0.625*7,-0.375-0.25) rectangle+(4.75-0.625*7,0.25);
at (0.625*7-0.55,-0.375-0.125)Error:;
at (0.625*7-2.3,-0.375-0.125)$F(u_3)-F(u)$;
[<-] (0.625*7-1.2,-0.375-0.125) – (0.625*7-1.4,-0.375-0.125);

The streaming algorithm (in green) and difference estimators (in white/red) can be used to estimate the $F_p$ value of the sliding window up to a small error caused by the elements in blue by subtracting the red estimates of the difference estimators from the estimate of the smallest suffix that contains the active elements in the sliding window.

Suffix-pivoted difference estimators.
A barrier in the sliding window model is that the difference estimator partitions the prefix of the stream rather than the suffix.
For example, compare the locations of the difference estimators between fig:stitch and fig:sliding.
In both the adversarially robust setting and the sliding window model, the difference estimator must approximate $F(v)-F(u)$ for frequency vectors $v\succeq u$.
However in the robust setting, $u$ is a fixed frequency vector induced by the prefix of the stream while in the sliding window model, $u$ is a growing frequency vector induced by the suffix of the stream, where we recall that a prefix and suffix of length $t$ are respectively defined to be the first and last $t$ updates of a stream.
Thus, we define a suffix-pivoted difference estimator to handle the case where the vector $u$ can change along with updates in the stream.
Fortunately, the fixed-prefix difference estimators that we have developed also function as suffix-pivoted difference estimators under this definition (we shall shortly demand a stronger definition).
We partition the stream to induce frequency vectors $v$ and $u_1$ so that $F(v+u_1)-F(u_1)\approx 2^k\cdot F(v+u_1)$ for a level $k$ suffix-pivoted difference estimator.
We maintain $\beta$ granularities, where $\beta$ is roughly a logarithmic function of the smoothness parameter that is generally $\O{\log\frac{1}{\eps}}$.
We thus obtain an additive $\O{\frac{\eps}{\beta}}\cdot F(v+u_1)$ error at each level $i\in[\beta]$, and summing the errors across all $\beta$ granularities, gives $\eps\cdot F(v+u_1)$ total additive error, i.e., $(1+\eps)$ multiplicative approximation to $F(v+u_1)$.

Issues with dynamic differences.
There is a subtle but significant issue with naïvely applying the $(\gamma,\eps,\delta)$-difference estimators in the sliding window model.
Recall that a level $k$ difference estimator guarantees an additive $\eps\cdot F(v+u_1)$ error to the difference $F(v+u_1)-F(u_1)$ provided that $F(v+u_1)-F(u_1)\le\frac{1}{2^k}\cdot F(v+u_1)$.
In the sliding window model, additional updates to the stream may arrive and induce a frequency vector $u_2$ for the same splitting time with $F(v+u_2)-F(u_2)\gg\frac{1}{2^k}\cdot F(v+u_2)$, which is too large for the accuracy of a level $k$ difference estimator.

Because of the smoothness parameter of an $(\eps,\eps^q)$-smooth function $F$, we observe that if the difference $F(v+u_1)-F(u_1)$ at some point is roughly $\eps^q\cdot F_2(v+u_1)$, then the difference $F(v+u_2)-F(u_2)\le\eps\cdot F(v+u_2)$ at any later point in the stream, regardless of subsequent updates.
Now the issue is that we maintain $\frac{1}{\eps^q}$ difference estimators corresponding to additive error $\eps^q\cdot F(v+u_1)$, but since each of these differences can eventually be as large as $\eps\cdot F(v+u_2)$, we potentially need higher accuracy for these differences, using space dependence $\frac{1}{\eps}$ for each difference estimator.
Unfortunately, this results in space dependence $\frac{1}{\eps^{1+q}}$.

For example, consider the $F_2$ moment function in fig:sw:bad and suppose $v=(0,1)$ and $u_1=\left(\frac{1}{\eps},0\right)$ so that $F_2(v+u_1)=\frac{1}{\eps^2}+1$ and $F_2(v+u_1)-F_2(u_1)=1\le\eps^2\cdot F_2(v+u_1)$.
Hence, we have $\gamma=\eps^2$ and allocate space proportional to $\frac{\gamma}{\eps^2}$ for the difference estimator for $v$.
We then have a number of updates so that $u_2=\left(\frac{1}{\eps},\frac{1}{\eps}\right)$.
Then $F_2(v+u_2)=\frac{2}{\eps^2}+\frac{2}{\eps}+1$ and $F_2(v+u_2)-F_2(u_2)=\frac{2}{\eps}+1\ge\frac{\eps}{2}\cdot F_2(v+u_2)$ for sufficiently small constant $\eps>0$.
Now we have $\gamma'\ge\frac{\eps}{2}$, so we should allocate space proportional to $\frac{\gamma'}{\eps^2}\approx\frac{1}{\eps}$ for the difference estimator for $v$, but we already only allocated space proportional to $\frac{\gamma}{\eps}\approx 1$.
Therefore, we do not have any guarantee that our difference estimator will be accurate!
Moreover, there can be $\O{\frac{1}{\eps^2}}$ such blocks $v$, so we cannot afford to allocate $\frac{\gamma'}{\eps^2}$ space for each block, which would result in space dependency $\frac{1}{\eps^3}$.

[shading=radial, inner color = white, outer color = green!50!, opacity=1] (0,0.25) rectangle+(2,0.25);
(0,0.25) rectangle+(2,0.25);

[decorate,decoration=brace] (2-0.1,-0.1) – (0,-0.1);
at (1,-0.5)$v$;
[shading=radial, inner color = white, outer color = red!50!, opacity=1] (2,0.25) rectangle+(2,0.25);
(2,0.25) rectangle+(2,0.25);

[decorate,decoration=brace] (4,-0.1) – (2+0.1,-0.1);
at (3,-0.5)$u_1$;

[shading=radial, inner color = white, outer color = green!50!, opacity=1] (5,0.25) rectangle+(2,0.25);
(5,0.25) rectangle+(2,0.25);

[decorate,decoration=brace] (7-0.1,-0.1) – (5,-0.1);
at (6,-0.5)$v$;
[shading=radial, inner color = white, outer color = red!50!, opacity=1] (7,0.25) rectangle+(4,0.25);
(7,0.25) rectangle+(4,0.25);

[decorate,decoration=brace] (11,-0.1) – (7+0.1,-0.1);
at (9,-0.5)$u_2$;

For $v=(0,1)$, $u_1=\left(\frac{1}{\eps},0\right)$, and $u_2=\left(\frac{1}{\eps},\frac{1}{\eps}\right)$, we have $F_2(v+u_1)-F_2(u_1)=\O{\eps^2}\cdot F_2(v+u_1)$ but $F_2(v+u_2)-F_2(u_2)=\Omega(\eps)\cdot F_2(v+u_2)$, so it is unclear which granularity should be assigned to the difference estimator for $v$.

Stronger suffix-pivoted difference estimators.
We thus define the suffix-pivoted difference estimators to give an $\eps\cdot F(v+u_2)$ approximation to an $(\eps,\eps^q)$-smooth function $F$, provided that $F(v+u_1)-F(u_1)\le\eps^q\cdot F(v+u_1)$ at some point in the stream with $u_1\preceq u_2$, even if $F(v+u_2)-F(u_2)=\eps\cdot F(v+u_2)$.
We give constructions of suffix-pivoted difference estimators under this stronger definition.
The main point is that we can now use roughly $2^k$ difference estimators with space dependence $\frac{1}{2^k\eps^2}$ at level $k$ for each $k$ up to roughly $\beta=\log\frac{1}{\eps^q}$, even if the difference eventually becomes a much larger fraction.
Moreover, the stronger guarantees of the suffix-pivoted difference estimators ensure that the additive error is still $\eps\cdot F(v+u_2)$, even if the difference eventually becomes a much larger fraction of what it was originally. Also, additive error $\eps \cdot F(v + u_2)$ is fine, because we only add up $\O{\log\frac{1}{\eps}}$ difference estimators, and can rescale $\eps$ by a $\log\frac{1}{\eps}$ factor.

This stronger definition may sound unachievable if $k=\log\frac{1}{\eps^q}$ since the space dependence is now $\frac{\eps^q}{\eps^2}$, which is even smaller than $1$. But for an important
class of functions we consider, namely $F_p$-moment estimation, where $q = p$, this
$\frac{\eps^p}{\eps^2}$ multiplies a much larger term, namely, $n^{1-2/p}$, and so the space
is still much larger than $1$. Interestingly, we are able to beat the usual $n^{1-2/p}$ space
lower bound for this problem by additionally removing global heavy hitters from all difference
estimators at a given level, which is a key idea.

In more detail, we give a suffix-pivoted difference estimator for $F_p$-moment estimation with $p>2$ where the space dependency is $\tO{\frac{\gamma}{\eps^2} n^{1-2/p}}$, which can still be much larger than $1$ if $\gamma=\eps^p$ and $n$ is large.
We still incur a $\frac{1}{\eps^p}$ space dependence due to running $\frac{1}{\gamma}=\frac{1}{\eps^p}$ different difference estimators at level $k=\log\frac{1}{\eps^p}$, but this multiplies  $\tO{\frac{\gamma}{\eps^2} n^{1-2/p}}$ which then becomes $\tO{\frac{1}{\eps^2} n^{1-2/p}}$, as desired.
As mentioned, we achieve space $\tO{\frac{\eps^p}{\eps^2} n^{1-2/p}}$ for each difference estimator at this level by running a single algorithm in parallel that uses $\tO{\frac{1}{\eps^2} n^{1-2/p}+\frac{1}{\eps^p}}$ space to remove $\O{\frac{1}{\eps^p}}$ global $L_p$ heavy hitters in the sliding window, i.e., the elements $i\in[n]$ with frequency $f_i^p\ge\eps^p\cdot F_p$, and can be seen as a variance reduction technique.
Thus after the global heavy hitters are removed, the usual $\frac{1}{\eps^2}\cdot n^{1-2/p}$ lower bounds no longer apply.

Thus, we suffer an additive $\O{\frac{1}{\eps^p}}$ term for finding heavy hitters, which is necessary of any algorithm, but it does not multiply the dominant $n^{1-2/p}$ term in our space bound.
For more details but still a high level overview, see the construction details later in sec:overview:de.
We thus obtain an additive $\O{\frac{\eps}{\beta}}\cdot F(v)$ error at each level, and summing the errors across all $\beta$ levels gives $\eps\cdot F(v)$ total additive error, i.e., $(1+\eps)$ multiplicative approximation to $F(v)$.

§.§ Difference Estimators

We now outline the ideas involved in developing our new difference estimators.
We describe our difference estimators for $F_p$-moment estimation, for both the adversarially robust and sliding window models; such estimators have applications to other streaming problems and can be used for estimating entropy and for finding the $L_2$-heavy hitters.
The high-level intuition for why difference estimators should be possible is that we leverage the fact that the difference is small into an estimator with significantly smaller variance.
Thus we can take the mean of a smaller number of independent estimators.

Difference estimators for $F_2$ moment estimation.
We approximate $F_2(v)-F_2(u)$ by noting that $F_2(v)=F_2((v-u)+u)=F_2(v-u)+2\ip{v-u}{u}+F_2(u)$.
Thus if $F_2(v)-F_2(u)\le\gamma F_2(u)$, then a $\left(1+\frac{\eps}{\gamma}\right)$-approximation to $F_2(v)-F_2(u)$ translates to additive error $\eps\cdot F_2(u)$.
We then show that if streaming algorithm $\calA$ gives a $(1+\eps)$ approximation to $F_2(u)$ and a $\left(1+\frac{\eps}{\sqrt{\gamma}}\right)$ approximation to $F_2(v-u)$, then it gives an approximation to $\ip{v-u}{u}$ with additive error at most $\frac{\eps}{\sqrt{\gamma}}\cdot\|v-u\|_2\|u\|_2\le\eps\cdot F_2(u)$, for $F_2(v-u)\le\gamma\cdot F_2(u)$, where recall $F_2(u) = \|u\|_2^2$.
Hence $\calB$ can be directly built from the sketches maintained by $\calA$ in the case of $p=2$, with a space dependence of $\frac{\gamma}{\eps^2}$.

To adjust our construction to handle suffix-pivoted difference estimators, the crucial observation is that if $F_2(v+u_1)-F_2(u_1)=\eps^2\cdot F_2(v+u_1)$, then for any vector $u_2\succeq u_1$, we still have $F_2(v)\le\eps^2\cdot F_2(v+u_2)$.
Thus if we decompose $F_2(v+u_2)-F_2(u_2)=F_2(v)+2\langle v,u_2\rangle$, then we can still obtain an additive $\eps\cdot F_2(v+u_2)$ estimation to the difference by using a constant number of rows in the sketch to estimate $\langle v,u_2\rangle$ because $F_2(v)$ is so small.
Intuitively the main idea is that although the difference has increased from $F_2(v+u_1)-F_2(u_1)$ to $F_2(v+u_2)-F_2(u_2)$, the difference between these differences is just the dot product $\ip{v}{u_2-u_1}$ and we can still use the same space to efficiently estimate the dot product because $\|v\|_2$ remains the same.

Difference estimators for $F_0$ estimation.
We remark that the $F_0$ estimator of [15] similarly maintains sketches that can be used to build a difference estimator for $F_0$ with a space dependence of $\frac{\gamma}{\eps^2}$.
The algorithm first subsamples each item in the universe with probability $\frac{1}{2^k}$ at a level $k$ so that the expected number of distinct items appearing throughout the stream at level $k$ is $\frac{1}{2^k}\cdot F_0$.
The algorithm then determines a level $k$ that contains $\Theta\left(\frac{1}{\eps^2}\right)$ distinct items throughout the stream, which the algorithm then rescales by a factor of $2^k$ to obtain an unbiased estimator to $F_0$; it can be shown the variance of this estimator is roughly $\eps^2\cdot(F_0)^2$.

To obtain a difference estimator for $F_0(v)-F_0(u)=\gamma F_0(u)$ with $v\succeq u$, we instead count the number of items in a level with $\Theta\left(\frac{\gamma}{\eps^2}\right)$ distinct items that appear in the prefix $u$ of the stream.
It then follows that the expected number of the distinct items in $v$ but not in $u$ is $\Theta\left(\frac{\gamma^2}{\eps^2}\right)$.
Hence, we obtain a $\left(1+\frac{\eps}{\gamma}\right)$-approximation to $F_0(v)-F_0(u)$ by first running the subsampling procedure on $u$ and counting the number of distinct items at some level $k$ with $\Theta\left(\frac{\gamma}{\eps^2}\right)$ items.
We then run the same subsampling procedure with the same randomness on $v-u$ by only counting the additional items that are occupied at level $k$, and rescaling this number by $2^k$. Note that additional items must only appear in $v$ but not $u$, which is exactly $F_0(v)-F_0(u)$.
Although level $k$ does not necessarily give a $(1+\eps)$-approximation to $F_0(v)-F_0(u)$, it does give a $\left(1+\frac{\eps}{\gamma}\right)$-approximation to $F_0(v)-F_0(u)$, which translates to an additive $\eps\cdot F_0(u)$ approximation to $F_0(v)-F_0(u)$ since $F_0(v)-F_0(u)\le\gamma F(u)$.

Difference estimator, $p\in(0,2)$.
Our difference estimators for $p\in(0,2)$ are more involved, and we obtain an optimal dependence on $\log n$ and $\frac{1}{\eps}$.
A natural starting point is the identity $F_p(v)-F_p(u)=F_p(u+(v-u))-F_p(u)$ and the expansion $F_p(u+(v-u))=\sum_{k=0}^{\infty} \binom{p}{k}\cdot\langle u^{p-k},v^k\rangle$, where $v^k$ denotes the coordinate-wise exponent of $u$.
We would like to approximate each term in the series to approximate the overall difference.
However, this approach fails for non-integer $p<2$, since coordinates of the frequency vector $u$ may be zero, so that $u^{p-k}$ is undefined for $k=2$, and there does not seem to be a simple fix.

Another natural approach is the $L_p$ strong tracking algorithm of [11], which generates $\O{\frac{1}{\eps^2}}$ random vectors $z_1,z_2,\ldots$ of $p$-stable random variables.
The estimate of $L_p(v)$ is then the median of the absolute values of the inner products $\langle z_1,v\rangle,\langle z_2,v\rangle,\ldots$.
However, it seems challenging to recover the difference $F_p(v)-F_p(u)$ from the inner products $\langle z_1,v\rangle,\langle z_2,v\rangle,\ldots$ and $\langle z_1,u\rangle,\langle z_2,u\rangle,\ldots$.

Instead, we consider a variant of Li's geometric mean estimator [63].
As in the strong $L_p$-tracker of [11], we generate $\O{\frac{\gamma\log n}{\eps^2}}$ random vectors $z_1,z_2,\ldots$ of $p$-stable variables.
For a fixed positive integer constant $q$, we form $y_1,y_2,\ldots$ so that each $y_i$ is the geometric mean of the absolute values of $q$ consecutive inner products $\langle z_{1+(i-1)q},v\rangle,\ldots,\langle z_{iq},v\rangle$.
The final output is the average of the estimators $y_1,y_2,\ldots$.
The key property of Li's geometric mean estimator is that $Z:=\prod_{j=1+(i-1)q}^{iq}|\langle z_j,v\rangle|^{p/q}-\prod_{j=1+(i-1)q}^{iq}|\langle z_j,u\rangle|^{p/q}$ is an unbiased estimate to $F_p(v)-F_p(u)$ whose behavior we can analyze.
Namely, we relate $Z$ to $\prod_{j=1+(i-1)q}^{iq}\left(1+\left(\frac{|\langle z_j,v-u\rangle|}{|\langle z_j,u\rangle|}\right)^{p/q}\right)$, which has small variance given $\frac{F_p(v-u)}{F_p(u)}\le\gamma$.
Thus we require a smaller number of independent estimators and obtain a more efficient difference estimator for $F_p(v)-F_p(u)$ for fixed $u$ and $v$ with constant probability.

To achieve an optimal dependence on $\log n$, we cannot afford to union bound over $\poly(n)$ possible frequency vectors $u$.
Instead we use an approach similar to the strong trackers of [9, 8, 11].
We set a constant $q$ and split the stream into roughly $\frac{1}{\eps^{q/p}}$ times $r_1,r_2,\ldots$ between which the difference estimator increases by $\eps^{q/p}\cdot(F_p(v)-F_p(u))$ and apply a union bound to argue correctness at these times $\{r_i\}$, incurring a $\log\frac{1}{\eps}$ term.
To bound the difference estimator between times $r_i$ and $r_{i+1}$ for a fixed $i$, we note that the difference estimator only increases by $\eps^{q/p}\cdot(F_p(v)-F_p(u))$ from $r_i$ to $r_{i+1}$, so that we still obtain a $(1+\eps)$-approximation to $F_p(v)-F_p(u)$ with a $\eps^{1-q/p}$-approximation to the difference.
We then bound the probability that the supremum of the error between times $r_i$ and $r_{i+1}$ is bounded by $\eps^{1-q/p}$ by applying known results from chaining [9, 8, 11], thus avoiding additional $\log n$ factors.
To derandomize our algorithm, we give a generalization of a pseudorandom generator that fools half-space queries shown by [42, 56].
Our result shows a high-probability derandomization of any algorithm that stores the product of a number of frequency vectors induced by the stream between fixed times, with a matrix of i.i.d. entries.
We then union bound over all possible stopping times to argue the correctness guarantees of our difference estimator still hold under the derandomization.
Interestingly, we do not guarantee the same output distribution as that of using independent $p$-stable random variables, yet we still have a correct algorithm in low memory.

We also show that Li's geometric estimator can be used as a strong tracker for $L_p$.

Our construction for the suffix-pivoted difference estimator is the same.
We note that upon a change of notation, the key property to efficiently estimate $F_p(v+u_1)-F_p(u_1)$ is that $F_p(v)$ is small.
Moreover, we can express the variance of Li's geometric estimator in terms of $F_p(v)$ so that smaller values of $F_p(v)$ correspond to smaller variance for the estimators and thus we can use a smaller number of independent copies.
For the suffix-pivoted difference estimator, it may be true that $F_p(v+u_2)-F_p(u_2)$ could be much larger than $F_p(v+u_1)-F_p(u_1)$ for some $u_2\succeq u_1$, but $F_p(v)$ will still be “small” provided that $F_p(v+u_1)-F_p(u_1)$ is “small”.
Hence, the variance for Li's geometric estimator will still be small despite the difference potentially being much larger.

Fixed-prefix difference estimator, $p>2$.
Our difference estimator $\calB$ for $F_p$ for integers $p>2$ does use the expansion $F_p(u+(v-u))-F_p(u)=\sum_{k=0}^{p-1}\binom{p}{k}\langle u^k,(v-u)^{p-k}\rangle$, where $u^k$ denotes the coordinate-wise $k$-th power of $u$.
To obtain an unbiased estimator of $\langle u^k,(v-u)^{p-k}\rangle$, suppose we sample a coordinate $a\in[n]$ with probability $\frac{u_a^k}{\|u\|_k^k}$ and set $Z$ to be the $a$-th coordinate of $(v-u)^{p-k}$, which we can explicitly track since the updates to the frequency vector $v-u$ arrive in the stream after the updates to $u$.
If we could obtain an unbiased estimate $Y$ to $\|u\|_k^k$, then the expected value of $YZ$ would be exactly $\langle u^k,(v-u)^{p-k}\rangle$.
One could try to output a coordinate $a\in[n]$ with probability $(1 \pm \varepsilon)\frac{u_a^k}{\|u\|_k^k}$.
Such “approximate” $L_p$-samplers exist for $p\le 2$ [71, 54, 56], though this would lead to an overall suboptimal dependence on $\varepsilon$.
We could also potentially use an efficient “perfect” $L_p$-sampler, which outputs a coordinate $a\in[n]$ with probability $\frac{u_a^p}{\|u\|_p^p}$.
Perfect $L_p$-samplers are known for $p\le 2$ [56].
Corresponding samplers for $p>2$ are currently unknown, though it may be possible to extend the $L_p$ samplers of [56] to $p>2$ and potentially obtain a difference estimator algorithm.

Instead, we use the perfect $L_2$-sampler of [56] to return a coordinate $a\in[n]$ with probability $\frac{u_a^2}{\|u\|_2^2} \pm \frac{1}{\poly(n)}$.
We also obtain unbiased estimates $X$ and $Y$ of $u_a^{k-2}$ and $\|u\|_2^2$ with low variance, respectively, by using a $\countsketch$ algorithm and our $F_2$ moment estimation algorithm.

Given $a\in[n]$, we then track the $a$-th coordinate of $(v-u)^{p-k}$ exactly.
We show that the product of these terms $X$, $Y$, and $(v-u)^{p-k}$ forms an unbiased estimate to $\langle u^k,(v-u)^{p-k}\rangle$.
Unfortunately, the variance of these estimates is still too large.
We thus also find approximate frequencies to the heavy-hitters of $u$, i.e., we estimate each $u_a$ such that $u_a\ge\frac{\eps}{16\gamma^{1-1/p}}\|u\|_p$ and track the corresponding $a$-th coordinate of $(v-u)^{p-k}$ exactly.
We remove these terms before we perform the perfect $L_2$ sampling, so that the resulting unbiased estimate to $\langle u^k,(v-u)^{p-k}\rangle$ has smaller variance.
We then show that taking the mean of enough repetitions gives a $(1+\eps)$-approximation to $\langle u^k,(v-u)^{p-k}\rangle$.
By repeating the estimator for each summand in $\sum_{k=0}^{p-1}\binom{p}{k}\langle u^k,(v-u)^{p-k}\rangle$, it follows that we obtain a $(\gamma,\eps,\delta)$-difference estimator for $F_p$.

Suffix-pivoted difference estimator, $p>2$.
Our construction for the suffix-pivoted difference estimator requires a bit more care.
We can again write $F_p(v)-F_p(u)=\sum_{k=1}^p\langle(v-u)^{p-k},u^k\rangle$.
However, we require $\O{\frac{1}{\eps^p}}$ difference estimators due to the smoothness parameter of $F_p$.
Namely, we implement suffix-pivoted difference estimators with $\gamma$ as small as $\eps^p$ whereas we previously implemented prefix-fixed difference estimators with $\gamma$ roughly as small as $\eps^2$.
Thus, we can no longer necessarily run a heavy-hitter algorithm that uses space proportional to $\O{\frac{\gamma^{2-2/p}}{\eps^2}}$ for each block of the stream corresponding to a difference estimator, since the quantity is no longer well-defined for $\gamma=\eps^p$.

On the other hand, the necessity to run separate heavy-hitter algorithms for each block in the fixed-prefix difference estimator originated from the adversarial robustness requiring fresh randomness in each block.
The sliding window model requires no such restriction and thus we instead we run a single heavy-hitter algorithm in parallel that uses space $\tO{\frac{1}{\eps^2}n^{1-2/p}}$ and simultaneously finds a list $\calH$ of all heavy-hitters in the sliding window.
In particular, $\calH$ will report an approximate frequency of each heavy-hitter in each block assigned to a difference estimator.
The main point is that $\tO{\frac{1}{\eps^2}n^{1-2/p}}$ space is used to identify the heavy-hitters but only $\O{\frac{1}{\eps^{p}}\log n}$ space is used to track their approximate frequency in each block.
Hence, the $\frac{1}{\eps^p}$ dependency is still present but it now multiplies a lower-order term.
We can then decompose the difference $\sum_{k=1}^p\langle(v-u)^{p-k},u^k\rangle$ into the amount contributed by the heavy items $\sum_{a\in\calH}\sum_{k=1}^p(v_a-u_a)^{p-k}u_a^k$ and the amount contributed by the items that are not heavy $\sum_{a\notin\calH}\sum_{k=1}^p(v_a-u_a)^{p-k}u_a^k$.
We show that to estimate $\sum_{a\in\calH}\sum_{k=1}^p(v_a-u_a)^{p-k}u_a^k$, it again suffices to estimate the value of $v_a-u_a$ and then subsequently read off the corresponding coordinate $u_a$.

It remains to estimate $\sum_{a\notin\calH}\sum_{k=1}^p(v_a-u_a)^{p-k}u_a^k$.
We use the same approach of perfect $L_2$ sampling coordinates from $v-u$ and reading off the corresponding coordinates in $u$, so that each perfect $L_2$ sample and the corresponding coordinate in $u$ forms an estimate of the inner product.
Crucially we can use a more refined level set analysis to upper bound the variance of the inner product estimate by $\tO{\frac{\gamma}{\eps^2}n^{1-2/p}}\cdot (F_p(v))^2$, even when $\gamma$ is as small as $\eps^p$.
Thus as before, smaller values of $F_p(v)$ correspond to smaller variance for the estimators and thus we can use a smaller number of independent copies of the inner product estimates.
Since each inner product estimate requires polylogarithmic space, it suffices to take the mean of $\tO{\frac{\gamma}{\eps^2}n^{1-2/p}}$ such inner product estimators to form our difference estimator.

Heavy hitters.
Our framework extends to an adversarially robust streaming algorithm for finding $L_2$ heavy hitters.
We first run the same $F_2$ moment estimation algorithm that stitches together sketches of different granularities, which partitions the stream of length $m$ is partitioned into $\beta$ blocks.
Observe that a heavy-hitter $i\in[n]$ with $f_i>\eps\cdot L_2(1,m)$ must have frequency at least $\frac{\eps}{\beta}\cdot L_2(1,m)$ in one of these $\beta$ blocks.
Now if $F_2(t_j,t_{j+1})=\frac{1}{2^k}\cdot F_2(1,m)$ for a block corresponding to time interval $[t_j,t_{j+1}]$ in which $i$ has frequency at least $\frac{\eps}{\beta}\cdot L_2(1,m)$, then $f_i^2\ge\frac{2^k\eps^2}{\beta^2} F_2(t_j,t_{j+1})$.
We can identify $i$ using a much higher threshold and thus much less space, i.e., space proportional to $\frac{\beta^2}{2^k\eps^2}$ rather than $\frac{\beta^2}{\eps^2}$.
Thus in parallel with our $F_2$ moment estimation algorithm, each time we run a difference estimator $\calB$ and an $F_2$-estimation algorithm $\calA$ with a specific granularity, we also run a heavy hitters algorithm with threshold corresponding to the same granularity of $\calB$.
For example, if the difference estimator on a block contributes $\frac{1}{2^k}\cdot F_2(1,m)$ to the overall $F_2$ moment, then we use a level $k$ difference estimator $\calB$ with effective accuracy $1+\frac{2^k\eps}{\beta}$ and we similarly run a heavy hitters algorithm to detect items that are $\frac{2^k\eps^2}{\beta^2}$-heavy with respect to $F_2$ on the block.

We then explicitly count each reported item to remove all items that may be heavy with respect to a single block, but not the overall stream, and obtain an accurate count for each heavy hitter.

§.§ Preliminaries

We use the notation $[n]$ to denote the set $\{1,\ldots,n\}$ for any positive integer $n$.
We use $\poly(n)$ to denote a constant degree polynomial in $n$.
When an event has probability $1-\frac{1}{\poly(n)}$ of occurring, we say the event occurs with high probability.
We use $\polylog(n)$ to denote a polynomial in $\log n$.

For a function $F$, let $F(t_1,t_2)$ denote the value of $F$ on the underlying frequency vector induced between times $t_1$ and $t_2$, inclusive.
In the basic insertion-only stream, the $t$-th stream update $u_t$ is an integer in $[n]$, where $t\in[m]$ for a stream of length $m$.
The updates implicitly define a frequency vector $f\in\mathbb{R}^n$ so that the effect of each update is to increase the value of a coordinate of $f$.
Thus, we have $f_i=|\{t\,:\,u_t=i\}|$ for each $i \in [n] = \{1, 2, \ldots, n\}$.
In the sliding window model, the frequency vector is induced by only the most recent $W$ updates in an insertion-only stream.
Hence if $W\ge m$ for a stream of length $m$, the model reduces to the insertion-only streaming model and if $W<m$, then $f_i=|\{t\,:\,u_t=i \textrm{ and } t\ge m-W+1\}|$ for each $i\in[n]$.
In turnstile streams, each update $u_t=(\Delta_t, i_t)$, where $\Delta_t\in\{-1,+1\}$ and $i_t\in[n]$.
Hence, each update either increases or decreases a coordinate of $f$.

For vectors $u$ and $v$ of length $n$, we use the notation $u\succeq v$ to denote that $u$ coordinate-wise dominates $v$, i.e., $u_i\ge v_i$ for all $i\in[n]$.

Let $\lsb(x,i)$ be the $i$-th least significant bit in the binary representation of $x$, when using $1$-indexing, e.g., we start counting indices from $1$ rather than $0$.
Let $\numbits(x)$ be the number of nonzero bits in the binary representation of $x$.
For example, $\lsb(6,1)=2$, $\lsb(6,2)=3$, and $\numbits(x)=2$, since $6=110_2$.
As another example, $\lsb(8,1)=4$ and $\numbits(x)=1$, since $8=1000_2$.

Frequency moments.
The space complexity of approximating the frequency moments $F_p$ is one of the oldest and most fundamental problems on streams, originating with the work of Alon, Matias, and Szegedy [5].
For example, the $F_2$-estimation problem corresponds to the size of a self-join [5] and tracking it with limited storage is essential [3].
Given $p,\eps>0$, the $p$-th frequency moment estimation problem is to approximate $F_p = \sum_{i\in[n]} f_i^p$ within a $(1\pm\eps)$ factor for a frequency vector $f\in\mathbb{R}^n$.
The complexity of this problem and the related $L_p$-norm estimation problem differs greatly for different values of $p$.
For $p>2$, [16, 29] show that for the streaming model, the memory required for $F_p$ estimation requires polynomial factors in $n$, whereas polylogarithmic space is achievable for $p\le 2$ [5, 51, 63, 60, 59, 11].

We note that $F_p$ estimation for fractional $p$ near $1$ is used for empirical entropy estimation [47], and $p=0.25$ and $p=0.5$ are useful for mining tabular data [28].
$L_1$-norm estimation is used in network traffic monitoring [38], low-rank approximation and linear regression [39], dynamic earth-mover distance approximation [50], and cascaded norm estimation [55].
$L_2$-norm estimation is used for estimating join and self-join sizes [3], randomized numerical linear algebra [34], and for detecting network anomalies [62, 80].
The values $p=3$ and $p=4$ also respectively correspond to the skewness and the kurtosis of a stream [5].

For a frequency vector $f$ with length $n$, we define $F_p(f)=\sum_{i=1}^n|f_i|^p$.
The $L_p$ norm[Observe that $L_p$ does not satisfy the triangle inequality for $0<p<1$ and thus is not a norm, but is still a well-defined quantity.] of $f$ is defined by $L_p(f)=(F_p(f))^{1/p}$.
We also use the notation $\|f\|_p$ to denote the $L_p$ norm of $f$.
The $F_p$-moment estimation problem is also often stated as the norm estimation problem, since an algorithm that outputs a $(1+\eps)$-approximation to one of these problems can be modified to output a $(1+\eps)$-approximation to the other using a constant rescaling of $\eps$ (for constant $p$); thus we use these two equivalent problems interchangeably.
The $L_2$-heavy hitters problem is to output all coordinates $i$ such that $f_i\ge\eps\cdot L_2$.
The problem permits the output of coordinates $j$ with $f_j\le\eps\cdot L_2$ provided that $f_j\ge\frac{1}{2}\cdot L_2$.
Moreover, each coordinate output by the algorithm also requires an estimate to its frequency, with additive error at most $\frac{1}{2}\cdot L_2$.

[17]
For $\eps>0$ and an integer $m>0$, the $(\eps,m)$-flip number of a sequence $y_1,\ldots,y_m$ is the largest integer $k$ such that there exist $0\le i_1<\ldots<i_k\le m$ with $y_{i_{j-1}}\notin[(1-\eps)y_{i_j},(1+\eps)y_{i_j}]$ for all integers $j\in[2,k]$.

For $\eps>0$ and an integer $m>0$, the $(\eps,m)$-twist number for a non-negative function $F$ on a stream of updates $1=u_1,\ldots,u_m$ is the largest integer $k$ such that there exist $0\le i_1<\ldots<i_k\le m$ with for each $j\in[2,k]$, either $F(u_1:u_{j-1})\notin[(1-\eps)F(u_1:u_j),(1+\eps)F(u_1:u_j)]$ or $F(u_{j-1}:u_j)\ge\eps F(1:u_{j-1})$.

Let $f^{(1)},\ldots,f^{(m)}$ be the frequency vectors induced by a stream of length $m$ and let $g:\mathbb{R}^n\to\mathbb{R}$ be a function on frequency vectors.
An algorithm $A$ provides $(\eps,\delta)$-strong $g$-tracking if at each time step $t\in[m]$, $A$ outputs an estimate $X_t$ such that

\[|X_t-g(f^{(t)})|\le\eps|g(f^{(t)})|\]

for all $t\in[m]$ with probability at least $1-\delta$.

[17]
For $p>0$, the $(\eps,m)$-twist number of $\|x\|_p^p$ in the insertion-only model is $\O{\frac{1}{\eps}\log m}$ for $p\le 2$ and $\O{\frac{p}{\eps}\log m}$ for $p>2$.

§ FRAMEWORK FOR ADVERSARIALLY ROBUST STREAMING ALGORITHMS

In this section, we describe a general framework for adversarially robust streaming algorithms, using the sketch stitching and granularity changing techniques.
We first require the following specific form of a difference estimator.

Given a stream $\calS$, a fixed time $t_1$, and a splitting time $t_2$ that is only revealed at time $t_2$, let frequency vector $v$ be induced by the updates of $\calS$ from time $t_1$ to $t_2$ and frequency vector $w_t$ be induced by updates from time $t_2$ to $t$ exclusive.
Given an accuracy parameter $\eps>0$ and a failure probability $\delta\in(0,1)$, a streaming algorithm $\calB(t_1,t_2,t,\gamma,\eps,\delta)$ is a $(\gamma,\eps,\delta)$-difference estimator for a function $F$ if, with probability at least $1-\delta$, it outputs an additive $\eps\cdot F(v)$ approximation to $F(v+w_t)-F(v)$ simultaneously for all $t\ge t_2$ with $F(v+w_t)-F(v)\le\gamma\cdot F(v)$ and $F(w_t)\le\gamma F(v)$ for a ratio parameter $\gamma\in(0,1]$.

We shall use the shorthand “difference estimator” terminology to refer to def:diff:est until sec:sliding; in sec:sliding we will introduce an additional notion of a difference estimator for when $F(v)$ can change.

It is easy to see that difference estimators offer an immediate means to approximation algorithms.

Since $F(u+v_1+\ldots+v_i)=F(u+v_1+\ldots+v_{i-1})+(F(u+v_1+\ldots+v_{i-1})-F(u+v_1+\ldots+v_i))$ and the difference is bounded by $\gamma_i\cdot F(u+v_1+\ldots+v_{i-1})$ by the definition of difference estimator, then we have the invariant $F(u+v_1+\ldots+v_i)\le(1+\gamma_i)F(u+v_1+\ldots+v_{i-1})\le 2F(u)$ for all $i\in\{1,\ldots,k\}$ by induction.
Thus the sum of the additive errors from each difference estimator is at most $\sum_{i=1}^k\eps_i\cdot F(u+v_1+\ldots+v_{i-1})\le\frac{\eps}{4}\cdot 2F(u)=\frac{\eps}{2}\cdot F(u)$.
Similarly the additive error due to the $\left(1+\frac{\eps}{2}\right)$-approximation to $F(u)$ is also $\frac{\eps}{2}\cdot F(u)$, so that by monotonicity of $F$ and a telescoping argument the sum gives a $(1+\eps)$ multiplicative approximation to $F(u+v_1+\ldots+v_i)$.
Since each difference estimator fails with probability at most $\frac{1}{3k}$, then by a union bound, the total probability of failure is at most $\frac{1}{3}$.

The total space is $\sum_{i=1}^k N_i\cdot\frac{\gamma_i}{\eps^2}\cdot S$.
Since $N_i\le 2^i$, $\gamma_i\le\frac{1}{2^i}$, and $k=\O{\log n}$, then the total space is at most $k\cdot\frac{S}{\eps^2}\le\O{S\log n}{\eps^2}$.

§.§ Algorithm

We first describe a simplified version of our adversarially robust framework that adapts the usage of difference estimators.
To achieve a robust $(1+\O{\eps})$-approximation, [17] used a “switch-a-sketch” technique that maintains $(\eps,m)$-flip number $\xi$ (recall def:flipnumber) independent subroutines that each provide a $(1+\eps)$ to a function $F$ evaluated on the frequency vector induced by the stream, with high probability.
For the remainder of the discussion, we assume the $\xi=\Omega\left(\frac{1}{\eps}\log n\right)$, which is true for many important functions $F$, especially the important $F_p$ moments and moreover, that the twist number $\lambda=\xi$, which is true for insertion-only streams.

To prevent an adversary from affecting the output of the algorithm, each subroutine is effectively only used once.
The output of the $i$-th subroutine is only used the first time the true output of the subroutine is at least $(1+\eps)^i$.
The algorithm of [17] then repeatedly outputs this value until the $(i+1)$-st subroutine is at least $(1+\eps)^{i+1}$, at which point the algorithm switches to using the output of the $(i+1)$-st subroutine instead.
Hence, the adversary information-theoretically knows nothing about the internal randomness of the $i$-th subroutine until the output is at least $(1+\eps)^i$.
However, due to monotonicity of $F$ and correctness of the oblivious $(i+1)$-st instance, whatever knowledge the adversary gains about the $i$-th instance does not impact the internal randomness of future instances.
Intuitively, the switch-a-sketch approach uses a sketch once and switches to another sketch once the estimated $F$ has increased by $(1+\eps)$.
$F$ can only increase $\lambda$ times by definition of the $(\eps,m)$-twist number.
Since $\lambda=\Omega\left(\frac{1}{\eps}\log n\right)$, this approach generally achieves $\frac{1}{\eps^3}$ space dependency.

Framework for Robust Algorithms on Insertion-Only Streams
[1]
Stream $u_1,\ldots,u_m\in[n]$ of updates to coordinates of an underlying frequency vector, accuracy parameter $\eps\in(0,1)$, $(\gamma,\eps,\delta)$-difference estimator $\calB$ for $F$ with space dependency $\frac{\gamma^C}{\eps^2}$ for $C\ge 1$, oblivious strong tracker $\calA$ for $F$
Robust $(1+\eps)$-approximation to $F$
$\delta\gets\frac{1}{\poly\left(\frac{1}{\eps}, \log n\right)}$, $\zeta\gets\frac{2}{2^{(C-1)/4}-1}$, $\eta\gets\frac{\eps}{64\zeta}$, $\beta\gets\ceil{\log\frac{8}{\eps}}$
$a\gets 0$, $\varphi\gets 2^{(C-1)/4}$, $\gamma_j\gets 2^{j-1}\eta$
For $j\in[\beta]$, $\eta_j\gets\frac{\eta}{\beta}$ if $C=1$, $\eta_j\gets\frac{\eta}{\varphi^{\beta-j}}$ if $C>1$.
Accuracy for each difference estimator
each update $u_t\in[n]$, $t\in[m]$
Switch sketch at top layer
$a\gets a+1$, $b\gets 0$, $Z_a\gets X$, $t_{a,j}\gets t$ for $j\in[\beta]$.

Compute estimator $X$ for $F$ using unrevealed sketch
$X>\left(1+\frac{(b+1)\eps}{8}\right)\cdot Z_a$
Switch sketch at lower layer
$b\gets b+1$, $k\gets\lsb(b,1)$, $j\gets\flr{\frac{b}{2^k}}$
Freeze old sketch
$t_{a,j}\gets t$ for $j\in[k]$.
Update difference estimator times
$\left(1+\frac{b\eps}{8}\right)\cdot Z_a$
Output estimate for round $t$

Subroutine $\estimateF$ of alg:framework
[1]
$X\gets Z_a$, $k\gets\numbits(b+1)$, $z_i\gets\lsb(b+1,k+1-i)$ for $i\in[k]$.

$z_1>\ldots>z_k$ are the nonzero bits in the binary representation of $b+1$.
$1\le j\le k-1$
Compile previous frozen components for estimator $X$
$X\gets X+Z_{a,j}$
$X\gets X+\calB_{a,j}\left(1,t_{a,z_k},t,\gamma_{z_k},\eta_{z_k},\delta\right)$
Use unrevealed sketch for last component

We first observe that if we instead use the switch-a-sketch technique each time $F$ increases by a power of $2$, then we only need to switch $\O{\log n}$ sketches.
Effectively, this follows from setting $\eps=\O{1}$ in the value of $\lambda$.
Let $t_i$ be the first time $F$ of the stream surpasses $2^i$.
The challenge is then achieving a $(1+\eps)$-approximation to $F$ at the times between each $2^i$ and $2^{i+1}$.
Let $u$ be the underlying frequency vector at time $t_i$, so that $F(u)\ge 2^i$.
If $v$ is the underlying frequency vector at some time between $t_i$ and $t_{i+1}$, then we can decompose $F(v)=F(u)+\sum_{j=1}^{\beta}(F(u_j)-F(u_{j-1}))$, where we use the convention that $u_0=u$ and $u_{\beta}=j$.
Moreover, we assume that $F(u_j)-F(u_{j-1})\le\gamma\cdot F(v)$ for $\gamma\le\frac{1}{2^j}$.

Our key observation is that because we only care about a $(1+\eps)$-approximation to $F(v)$, we do not need a $(1+\eps)$-approximation to each of the differences $F(u_j)-F(u_{j-1})$, which may be significantly smaller than $F(v)$.
For example, note that a $(2^j\cdot\eps)$-approximation to $F(u_j)-F(u_{j-1})$ only equates to an additive $\O{\eps\cdot F(v)}$ error, since $F(u_j)-F(u_{j-1})=\O{\frac{1}{2^j}}\cdot F(v)$.
We require $\frac{1}{\gamma}$ instances of algorithms with such accuracies, to account for the various possible vectors $v$.
Thus if there exists an algorithm that uses $\frac{\gamma}{\eps^2}S(n)$ bits of space to output additive $\eps\cdot F(v)$ error, then the space required across the level $j$ estimators is $\frac{1}{\eps^2}S(n)$ bits of space.
Since there are at most $\O{\log\frac{1}{\eps}}$ levels, then we do not incur any additional factors in $\frac{1}{\eps}$.
Recall that a difference estimator (def:diff:est) to $F$ serves exactly this purpose!

It is not obvious how to obtain a difference estimator for various functions $F$.
However, for the purposes of a general framework, the theoretical assumption of such a quantity suffices; we shall give explicit difference estimators for specific functions $F$ of interest.
The framework appears in full in alg:framework.

Interpretation of alg:framework.
We now translate between the previous intuition and the pseudocode of alg:framework.
The streaming algorithm $\calA_{a+1}$ attempts to notify the algorithm whenever the value of $F$ on the underlying frequency vector induced by the stream has increased by a power of two.
The role of $a$ serves as a counter, ensuring that a new instance of $\calA$ is used each time the value of $a$ has increased.
Since $a$ increases when $\calA_{a+1}>2^a$, i.e., the value of $F$ has increased by roughly a factor of two, then the instances $\calA$, indexed by $a$, perform sketch switching with the finest accuracy.
Thus, alg:framework defines $Z$ to be the value of $\calA_a$ when it is revealed and never uses $\calA_a$ again.

It remains for alg:framework to stitch the sketches between the times when $a$ increases.
Suppose $t_a$ is the time when $Z$ was most recently defined.
Then alg:framework uses the variables $Z_{a,k}$ to stitch together the sketches of the difference estimators $\calB$ for $F(1:t)-F(1:t_a)$.
Each variable $Z_{a,k}$ refers to a separate granularity of the difference estimator $\calB$.
Like the streaming algorithm $\calA$, the difference estimators $\calB$ are indexed by the counter $a$ to distinguish between the instances required for the sketch switching technique.
Additionally, the difference estimators $\calB$ for the variable $Z_{a,k}$ are indexed by a counter $j$ that represents the number of times a level $k$ difference estimator is required throughout the times $t$ that we roughly have $2^a<F(1:t)<2^{a+1}$.
The subroutine $\estimateF$ then stitches together the values $Z_{a,k}$ to form an estimate $X$ of $F(1:t)$.
Similarly, alg:framework stitches together the values $Z_{a,k}$ to form an estimate $X$ of $F(1:t)$, which it then rounds as the output.
The actual stitching process requires partitioning $F(1:t)-F(1:t_a)$, so that the appropriate granularities may be used for each difference estimator.
This is monitored by the nonzero bits in the binary representation of the counter $b$, which roughly denotes the ratio of $F(1:t)-F(1:t_a)$ to $F(1:t_a)$.
Now of course an inconvenience in the actual analysis is that because $\calB$ and $\calA$ are approximation algorithms, then we do not exactly have $2^a<F(1:t)<2^{a+1}$, although this is true up to a multiplicative $(1+\O{\eps})$-factor.

§.§ Analysis

We first show correctness of alg:framework at times where the counter $a$ increases.
This allows us to subsequently focus on times $t\in(t_i,t_{i+1})$ between points in the stream where the counter increases.

Let $F$ be a monotonic function with $(\eps,m)$-twist number $\lambda=\O{\frac{1}{\eps}\log n}$ for $\log m=\O{\log n}$.
For any integer $i>0$, let $t_i$ be the update time during which the counter $a$ in alg:framework is first set to $i$.
Then alg:framework outputs a $\left(1+\frac{\eps}{32}\right)$-approximation to $F$ at all times $t_i$, with probability at least $1-\O{\frac{\delta\log n}{\eps}}$.

Note that by definition, the counter $a$ in alg:framework is incremented from $i-1$ to $i$ in round $t_i$.
Thus all previous outputs of alg:framework have not used the subroutine $\calA_i$.
Hence, the adversarial input is independent of the randomness of $\calA_i$.
Thus by the correctness guarantee of the algorithm, $\calA_i$ outputs a $\left(1+\frac{\eps}{32}\right)$-approximation to $F$ at time $t_i$, with probability $1-\delta$.
Since $F$ has twist number $\lambda=\O{\frac{1}{\eps}\log n}$, then there are at most $\O{\frac{1}{\eps}\log n}$ update times $t_i$ in which the counter $a$ is increased.
By a union bound, alg:framework outputs a $\left(1+\frac{\eps}{32}\right)$-approximation to $F$ at all times $t_i$, with probability at least $1-\O{\frac{\delta\log n}{\eps}}$.

For any integer $i>0$, let $t_i$ be the update time during which the counter $a$ in alg:framework is first set to $i$.
Since lem:constant shows correctness at all times $t_i$, it remains to analyze the behavior of alg:framework between each of the times $t_i$ and $t_{i+1}$.

For each integer $j\ge 0$ and a fixed integer $i$, let $u_{i,j}$ be the last round for which $Z_{i,j}$ in alg:framework is defined.

With probability at least $1-\delta\cdot\poly\left(\frac{1}{\eps},\log n\right)$, we have $F(1,u_{i,j})-F(1,t_{i,j})\le\frac{2^j\eps}{64}\cdot F(1,t_i)$ for each positive integer $j>1$.

As before, let $t_i$ be the update time during which the counter $a$ in alg:framework is first set to $i$ for any integer $i>0$.
Let $t_{i,j}$ be the first round such that the counter $b$ in alg:framework is first set to $j$, and we use the convention that $t_{i,0}=t_i$.
Let $\mathcal{E}_1$ be the event that alg:framework outputs a $\left(1+\frac{\eps}{32}\right)$-approximation to the value of $F$ at all times $t_i$, so that by lem:constant, $\mathcal{E}_1$ holds with probability at least $1-\O{\frac{\delta\log n}{\eps}}$.
For the remainder of the proof, we fix the integer $i$ and show correctness between $t_i$ and $t_{i+1}$.
Note that conditioning on $\mathcal{E}_1$, we have correctness at times $t_i$ and $t_{i+1}$.

Let $\mathcal{E}_2$ be the event that the first $\poly\left(\frac{1}{\eps},\log n\right)$ instances of $\calB$ and $\calA$ in alg:framework are correct, so that $\PPr{\mathcal{E}_2}\ge1-\delta\cdot\poly\left(\frac{1}{\eps},\log n\right)$ by a union bound.
We show by induction on $b$ that conditioned on $\mathcal{E}_1$ and $\mathcal{E}_2$, we have that $F(1,u_{i,j})-F(1,t_{i,j})\le\frac{1}{2^{\beta-j-3}}F(1,t_i)$ for $j\ge 1$.

For the base case $b=1$, only $Z_{i,1}$ is defined.
Suppose by way of contradiction that $F(1,u_{i,1})-F(1,t_{i,1})>\frac{1}{2^{\beta-j-3}}\cdot F(1,t_i)$.
Since $\beta=\ceil{\log\frac{8}{\eps}}$, then $F(1,u_{i,1})-F(1,t_{i,1})>\frac{\eps}{2}\cdot F(1,t_i)$.
Observe that $\calB_{i,1}(1,t_{i,1},u_{i,1},\gamma_1,\eta_1,\delta)$ gives an $\eta_1\cdot F(1,t_i)$ additive approximation to $F(1,u_{i,1})-F(1,t_{i,1})$.
Hence, the estimate $Z_{i,1}$ of $F(1,u_{i,1})-F(1,t_{i,1})$ from $\estimateF$ is at least

\[Z_{i,1}\ge F(1,u_{i,1})-F(1,t_{i,1})-\eta_1\cdot F(1,t_i)>\frac{\eps}{3}\cdot F(1,t_i),\]

since $\eta_1=\frac{\eta}{\varphi^{\beta-1}}<\frac{\eps}{3}$ for $\eta=\frac{\eps}{64\zeta}$ and $\varphi>1$.
But this contradicts the fact that the counter $b$ is set to $j=1$, since

\[Z_i+Z_{i,1}>\left(1+\frac{\eps}{4}\right)Z_i,\]

since $Z_i\le(1+\eps)\cdot F(1,t_i)$ conditioned on $\mathcal{E}_1$.
Thus we have $F(1,u_{i,1})-F(1,t_{i,1})>\frac{1}{2^{\beta-j-3}}\cdot F(1,t_i)$, which completes the base case $j=1$.

For a fixed value $\ell>0$ of the counter $b$, let $k=\numbits(\ell)$ and for $x\in[k]$, let $z_x=\lsb(\ell,k-x+1)$, so that $z_1>\ldots>z_k$ are the nonzero bits of $\ell$.
Let $u=\sum_{x=1}^{k-1} 2^{z_x-1}\cdot z_x$ be simply the decimal representation of the binary number resulting from changing the least significant bit of $\ell$ to zero.

Moreover, if $X_u$ is the output at time $t^{(u)}_i$, then we have $X_u\ge\left(1+\frac{u\eps}{8}\right)\cdot Z_i$, since the counter $b$ is first set to $u$ at time $t^{(u)}_i$.
Note that $Z_{i,z_x}$ has not been changed from time $t^{(u)}_i$ to $t^{(\ell)}_i$ for all $x\in[k-1]$.
Since $X_{\ell}=\sum_{x=1}^{k}Z_{i,z_x}$, then we have

\[X_{\ell}=Z_{i,z_k}+X_u\ge Z_{i,z_k}+\left(1+\frac{u\eps}{8}\right)\cdot Z_i.\]

Suppose by way of contradiction that $F(1,u_{i,z_k})-F(1,t_{i,z_k})>\frac{1}{2^{\beta-z_k-3}}\cdot F(1,t_i)$.
Recall that $Z_{i,z_k}$ is an additive $2\eta_{z_k}F(1,t_i)$ approximation to $F(1,u_{i,z_k})-F(1,t_{i,z_k})$.
Hence we have

\[Z_{i,z_k}>\frac{1}{2^{\beta-z_k-3}}\cdot F(1,t_i)-2\eta_{z_k}F(1,t_i)>\frac{2^{z_k}\cdot\eps}{3}\cdot F(1,t_i),\]

since $\beta=\ceil{\log\frac{8}{\eps}}$ and $\eta_{z_k}=\frac{\eta}{\varphi^{\beta-z_k}}<\frac{\eps}{3}$ for $\varphi>1$.
Then we have

\[X_{\ell}=Z_{i,z_k}+X_u>\frac{2^{z_k}\cdot\eps}{3}\cdot F(1,t_i)+\left(1+\frac{u\eps}{8}\right)\cdot Z_i>\left(1+\frac{\ell\eps}{8}\right)\cdot Z_i,\]

for sufficiently small constant $\eps>0$, since $2^{z_k}\ge(u-\ell)$ and $F(1,t_i)\ge(1-\eps)Z_i$ conditioned on $\mathcal{E}_1$.
But this contradicts the fact that the counter $b$ is set to $\ell$ at time $t^{(\ell)}_i$, since

\[X_{\ell}>\left(1+\frac{\ell\eps}{8}\right)\cdot Z_i.\]

Thus we have $F(1,u_{i,z_k})-F(1,t_{i,z_k})\le\frac{1}{2^{\beta-z_k-3}}\cdot F(1,t_i)$, which completes the inductive step.
The result then follows from observing that for $\beta=\ceil{\log\frac{8}{\eps}}$, we have that $\frac{1}{2^{\beta-j-3}}F(1,t_i)\le\frac{2^j\eps}{64}$.

With probability at least $1-\delta\cdot\poly\left(\frac{1}{\eps},\log n\right)$, alg:framework outputs a $(1+\eps)$-approximation to $F$ at all times on a non-adaptive stream.

As before, let $t_i$ be the update time during which the counter $a$ in alg:framework is first set to $i$ for any integer $i>0$.
For each integer $j\ge 0$, let $u_{i,j}$ be the last round for which $Z_{i,j}$ in alg:framework is defined.
Let $t_{i,\ell}$ be the first round such that the counter $b$ in alg:framework is first set to $\ell$, and we use the convention that $t_{i,0}=t_i$.
Let $\mathcal{E}_1$ be the event that alg:framework outputs a $\left(1+\frac{\eps}{32}\right)$-approximation to the value of $F$ at all times $t_i$, so that by lem:constant, $\mathcal{E}_1$ holds with probability at least $1-\O{\frac{\delta\log n}{\eps}}$.
For the remainder of the proof, we fix the integer $i$ and show correctness between $t_i$ and $t_{i+1}$.
Note that conditioning on $\mathcal{E}_1$, we have correctness at times $t_i$ and $t_{i+1}$.
By the monotonicity of $F$, it suffices to show correctness at all times $t_{i,\ell}$ for each value $\ell$ obtained by the counter $b$ between times $t_i$ and $t_{i+1}$.

Let $\ell$ be a fixed value of the counter $b$, $k=\numbits(\ell)$, and $z_x=\lsb(\ell,x)$ for $x\in[k]$ so that $z_1>\ldots>z_k$ are the nonzero bits in the binary representation of $\ell$.
By lem:time:geometric, we have for all $x\in[k]$

\[F(1,u_{i,z_x})-F(1,t_{i,z_x})\le\frac{1}{2^{\beta-x-3}}F(1,t_i),\]

with probability at least $1-\delta\cdot\poly\left(\frac{1}{\eps},\log n\right)$.
Since $u_{i,z_x}$ is the last round for which $Z_{i,z_x}$ in alg:framework is defined and all times $t_{i,j}$ for $j\le z_x$ are reset at that round, then we have $u_{i,z_x}=t_{i,z_{x+1}}$ for all $x\in[k]$.
Thus since $u_{i,z_k}=t_{i,\ell}$, we can decompose

\[F(1,t_{i,\ell})=\sum_{x=1}^k\left(F(1,u_{i,z_x})-F(1,u_{i,z_{x-1}})\right)=\sum_{x=1}^k\left(F(1,u_{i,z_x})-F(1,t_{i,z_x})\right).\]

Recall that the value $X_{\ell}$ of $X$ output by $\estimateF$ at time $t_{i,\ell}$ satisfies

\[X_{\ell}=Z_i+\sum_{x=1}^k Z_{i,z_x}.\]

By lem:constant, $Z_i$ incurs at most $\left(1+\frac{\eps}{8}\right)$ multiplicative error to $F(1,t_{i,\ell})$ since $F(1,t_{i,\ell})\le 4F(t_i)$.
Moreover, $Z_{i,z_k}$ is an additive $2\eta_{z_k}\cdot F(1,t_i)$ approximation to $F(1,u_{i,z_k})-F(1,t_{i,z_k})$.
Hence, the total additive error of $X_{\ell}$ to $F(1,t_{i,\ell})$ is at most

\[\frac{\eps}{4}\cdot F(1,t_{i,\ell})+\sum_{x=1}^k 2\eta_{z_x}\cdot F(1,t_i).\]

Now if the $(\gamma,\eps,\delta)$-difference estimator uses space dependency $\frac{\gamma}{\eps^2}$, then $\eta_x=\frac{\eta}{\beta}$ for all $x\in[\beta]$, so that

\[\sum_{x=1}^k 2\eta_{z_x}\cdot F(1,t_i)\le\sum_{x\in[\beta]}\eta_x\cdot F(1,t_i)\le\frac{\eps}{32}\cdot F(1,t_i)\]

and the error is at most $\frac{\eps}{2}\cdot F(1,t_{i,\ell})$.
On the other hand, if the $(\gamma,\eps,\delta)$-difference estimator uses space dependency $\frac{\gamma^C}{\eps^2}$ for $C>1$, then $\eta_x=\frac{\eta}{\varphi^{\beta-x}}$ for $\varphi=2^{(C-1)/4}$ implies that the error is at most

\[\sum_{x=1}^k 2\eta_{z_x}\cdot F(1,t_i)\le\frac{\eps}{2}\cdot F(1,t_{i,\ell}).\]

Therefore, $X_{\ell}$ is a $\left(1+\frac{\eps}{2}\right)$-approximation to $F(1,t_{i,\ell})$.

Note that the final output at time $t_{i,\ell}$ by alg:framework further incurs additive error at most $\frac{\eps}{8}\cdot Z_i$ due to the rounding $\left(1+\frac{b\eps}{8}\right)\cdot Z_a$ in the last step.
By lem:constant, $Z_i\le\left(1+\frac{\eps}{8}\right)\cdot F(1,t_{i,\ell})$.
Hence for sufficiently small constant $\eps>0$, we have that alg:framework outputs a $(1+\eps)$-approximation to $F(1,t_{i,\ell})$, with probability at least $1-\delta\cdot\poly\left(\frac{1}{\eps},\log n\right)$.

Let $\eps,\delta>0$ and $F$ be a monotonic function with $(\eps,m)$-twist number $\lambda=\O{\frac{\log n}{\eps}}$ on a stream of length $m$, with $\log m=\O{\log n}$.
Suppose there exists a $(\gamma,\eps,\delta)$-difference estimator for $F$ that uses $\O{\frac{\gamma^C}{\eps^2}\cdot S_1(n,\delta,\eps)+S_2(n,\delta,\eps)}$ bits of space for some constant $C\ge 1$ and a strong tracker for $F$ that use $\O{\frac{1}{\eps^2}\cdot S_1(n,\delta,\eps)+S_2(n,\delta,\eps)}$ bits of space and functions $S_1,S_2$ that depend on $F$.
Then there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation for $F$ that succeeds with constant probability.
For $C>1$, the algorithm uses

\[\O{\frac{1}{\eps^2}\log n\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log n\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)+\frac{1}{\eps^2}\log^2 n}\]

bits of space, where $\delta'=\O{\frac{1}{\poly\left(\frac{1}{\eps},\,\log n\right)}}$.
For $C=1$, the algorithm uses

\[\O{\frac{1}{\eps^2}\log n\log^3\frac{1}{\eps}\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log n\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)+\frac{1}{\eps^2}\log^2 n}\]

bits of space.

Consider alg:framework.
lem:frame:oblivious proves correctness over non-adaptive streams.
We now argue that lem:frame:oblivious holds over adversarial streams.
The claim follows from a similar argument to the switch-a-sketch technique of [17].
Observe that each time either counter $a$ or $b$ increases, the subroutine $\estimateF$ causes alg:framework to use new subroutines $\calB_{i,j}$ and $\calA_i$ that have not previously been revealed to the adversary.
Thus the adversarial input is independent of the randomness of $\calB_{i,j}$ and $\calA_i$.
Hence by the correctness guarantee over non-adaptive streams, alg:framework outputs a $(1+\eps)$-approximation at all times.

We now analyze the space complexity of alg:framework for a difference estimator with space dependency $\frac{\gamma^C}{\eps^2}$ with $C>1$.
Recall that $\estimateF$ uses instance $j=\flr{\frac{b+1}{2^k}}$ for $\calB_{i,j}$ for each ratio parameter $\gamma_k=2^{k-1}\eta$ and accuracy parameter $\eta_k=\frac{\eta}{\varphi^{\beta-k}}$, where $k\in[\beta]$ for $\beta=\O{\log\frac{1}{\eps}}$, $\varphi=2^{(C-1)/4}$, and $\eta=\frac{\eps}{64\zeta}$.

By assumption, a single instance of $\calB$ uses

\[\O{\frac{\gamma^C}{\eps^2}\cdot S_1(n,\delta,\eps)+S_2(n,\delta,\eps)}\]

bits of space.
Since we require correctness of $\poly\left(\log n,\frac{1}{\eps}\right)$ instances of $\calB$, it suffices to set $\delta'=\O{\frac{1}{\poly\left(\frac{1}{\eps},\log n\right)}}$.
For granularity $k$, we have $j=\flr{\frac{b+1}{2^k}}$ for $\calB_{i,j}$ so that there are at most $\frac{C_2}{2^k\eps}$ instances of $\calB_{i,j}$, for some absolute constant $C_2>0$.
Thus for fixed $a$, $\beta\le\log\frac{8}{\eps}+1$, $\gamma_k=2^{k-1}\eta$, and accuracy parameter $\eta_k=\frac{\eta}{\varphi^{\beta-k}}$, the total space for each $\calB_{a,j}$ across the $\beta$ granularities is

\begin{align*}
\sum_{k=1}^\beta\frac{C_3\gamma_k^C}{\eta_k^2 2^k\eps}\cdot S_1(n,\delta',\eps)+\frac{C_3}{2^k\eps}S_2(n,\delta',\eps)&=\sum_{k=1}^\beta\frac{C_3\gamma_{\beta-k}^C}{\eta_{\beta-k}^2 2^{\beta-k}\eps}\cdot S_1(n,\delta',\eps)+\frac{C_3}{2^k\eps}S_2(n,\delta',\eps)\\
&\le\sum_{k=1}^\beta\frac{C_4 (2^{\beta-k}\eps)^C\varphi^{2k}}{\eps^2\cdot2^{\beta-k}\eps}\cdot S_1(n,\delta',\eps)+\frac{C_4}{2^k\eps}\cdot S_2(n,\delta',\eps)\\
&\le\sum_{k=1}^\beta\frac{C_5 2^{-Ck}\varphi^{2k}}{\eps^2\cdot2^{-k}}\cdot S_1(n,\delta',\eps)+\frac{C_4}{2^k\eps}\cdot S_2(n,\delta',\eps),
\end{align*}

for some absolute constants $C_3,C_4,C_5>0$.
Since $\varphi=2^{(C-1)/4}$ for $C>1$, then

\begin{align*}
\sum_{k=1}^\beta\frac{C_3\gamma_k^C}{\eta_k^2 2^k\eps}\cdot S_1(n,\delta',\eps)+\frac{C_3}{2^k\eps}S_2(n,\delta',\eps)&\le\sum_{k=1}^\beta\frac{C_5 2^{k-Ck}2^{(Ck-k)/2}}{\eps^2}\cdot S_1(n,\delta',\eps)+\frac{C_4}{2^k\eps}\cdot S_2(n,\delta',\eps)\\
&\le\O{\frac{1}{\eps^2}\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)}.
\end{align*}

Observe that for a stream with $(\eps,m)$-twist number $\lambda=\O{\frac{\log n}{\eps}}$, we have $a=\O{\log n}$, since the value of $F$ increases by a constant factor each time $a$ increases.
Hence, accounting for $a=\O{\log n}$, then alg:framework uses

\[\O{\frac{1}{\eps^2}\log n\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log n\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)}\]

bits of space in total for $C>1$ across each of the strong trackers and difference estimators.

Finally, we observe that because we run $\O{\frac{1}{\eps^2}\log n}$ instances of the subroutines, it takes $\O{\frac{1}{\eps^2}\log^2 n}$ total additional bits of space to maintain the splitting times for each of the instances over the course of a stream of length $m$, with $\log m=\O{\log n}$, so that the total space is

\[\O{\frac{1}{\eps^2}\log n\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log n\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)+\frac{1}{\eps^2}\log^2 n}.\]

We now analyze the space complexity for alg:framework for a difference estimator with space dependency $\frac{\gamma^C}{\eps^2}$ with $C=1$.
Instead of the accuracy parameter $\eta_k=\frac{\eta}{\varphi^{\beta-k}}$ for $C>1$, we now have $\eta_k=\frac{\eta}{\beta}$ for $C=1$
Thus for fixed $a$, $\beta\le\log\frac{8}{\eps}+1$, and $\gamma_k=2^{k-1}\eta$, there exist constants $C_6,C_7>0$ such that the total space for each $\calB_{a,j}$ across the $\beta$ granularities is

\begin{align*}
\sum_{k=1}^\beta\frac{C_3\gamma_k^C}{\eta_k^2 2^k\eps}\cdot S_1(n,\delta',\eps)+\frac{C_3}{2^k\eps}S_2(n,\delta',\eps)&\le\sum_{k=1}^\beta\frac{C_6 (2^{k-1}\eps)}{\eta^2\beta^{-2}\cdot 2^k\eps}\cdot S_1(n,\delta',\eps)+\frac{C_6}{2^k\eps}\cdot S_2(n,\delta',\eps)\\
&\le\sum_{k=1}^\beta\frac{C_7\beta^2}{\eta^2}\cdot S_1(n,\delta',\eps)+\frac{C_7}{2^k\eps}\cdot S_2(n,\delta',\eps)\\
&\le\O{\frac{1}{\eps^2}\log^3\frac{1}{\eps}\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)}.
\end{align*}

Again accounting for $a=\O{\log n}$ and the space it takes to maintain the splitting times, then alg:framework uses

\[\O{\frac{1}{\eps^2}\log n\log^3\frac{1}{\eps}\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log n\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)+\frac{1}{\eps^2}\log^2 n}.\]

bits of space in total for $C>1$ across each of the strong trackers and difference estimators.

§ ROBUST F2 ESTIMATION

In this section, we use the previous framework of sec:framework to give an adversarially robust streaming algorithm for $F_2$ moment estimation.
Recall that to apply thm:framework, we require an $F_2$ strong tracker and an $F_2$ difference estimator.
We present these subroutines in this section.
We further optimize our algorithm beyond the guarantees of thm:framework specifically for $F_p$ moments, so that our final space guarantees in thm:robust:opt:F2 matches the best known $F_2$ algorithm on insertion-only streams, up to lower order $\polylog\frac{1}{\eps}$ terms.
Finally, we show that our algorithm naturally extends to the problem of finding the $L_2$-heavy hitters, along with producing an estimate for the frequency of each heavy-hitter up to an additive $\O{\eps}\cdot L_2$ error.

We first recall the following $F_2$ strong tracker.

[11]
Given an accuracy parameter $\eps>0$ and a failure probability $\delta\in(0,1)$, let $d=\O{\frac{1}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}+\log\log n\right)}$.
There exists an insertion-only streaming algorithm $\estimator$ that uses $\O{d\log n}$ space to provide $(\eps,\delta)$-strong $F_2$ tracking of an underlying frequency vector $f$.

To define our difference estimator, we first note that “good” $F_2$ approximation to two vectors $u$ and $v$ also gives a “good” approximation to their inner product $\ip{u}{v}$.

Let vectors $u,v\in\mathbb{R}^n$ and $M\in\mathbb{R}^{d\times n}$ be a sketching matrix so that each entry $M_{i,j}$ of $M$ is a four-wise independent random sign scaled by $\frac{1}{\sqrt{d}}$ for $d=\O{\frac{1}{\eps^2}}$.

\[\Pr{|\langle u,v\rangle-\langle Mu, Mv\rangle|\le\eps\|u\|_2\|v\|_2}\ge\frac{2}{3}.\]

The proof is a standard variance reduction argument that follows immediately from lem:approx:ip:all and lem:ams:ex and Chebyshev's inequality, since $M$ can be viewed as taking the arithmetic mean of $d$ scaled sign vectors $s_1,\ldots,s_d$.

Given vectors $0^n\preceq u_1\preceq u_2\preceq\ldots\preceq u_m\in\mathbb{R}^n$ whose entries are bounded by a polynomial in $n$, there exists an algorithm that uses a sketching matrix $M\in\mathbb{R}^{d\times n}$ with $d=\O{\frac{1}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}+\log\log n\right)}$ such that for $m=\poly(n)$ and a fixed $v\in\mathbb{R}^n$ with $v\succeq 0^n$,

\[|\ip{u_i}{v}-\ip{Mu_i}{Mv}|\le\eps\|u_i\|_2\|v\|_2,\]

simultaneously for all $i\in[m]$ with probability at least $1-\delta$.

Consider a sequence of indices $t_1<t_2<\ldots<t_q$ such that $t_{i+1}$ is the minimal index such that $\langle u_{t_{i+1}},v\rangle\ge\left(1+\frac{\eps}{2}\right)\langle u_{t_i},v\rangle$ and observe that $q=\O{\frac{1}{\eps}\log n}$ for $m=\poly(n)$ since each vector $u_i$ has polynomially bounded entries.
Since $0^n\preceq u_1\preceq u_2\preceq\ldots\preceq u_m\in\mathbb{R}^n$ and thus both $\|u_1\|_2\le\|u_2\|_2\le\ldots\|u_m\|_2$ and $\langle u_1,v\rangle\le\langle u_2,v\rangle\le\ldots\le\langle u_m,v\rangle$, it suffices to show that

\[|\ip{u_{t_i}}{v}-\ip{Mu_{t_i}}{Mv}|\le\eps\|u_{t_i}\|_2\|v\|_2,\]

for all $i\in[q]$.
By lem:ams:ex and lem:ams:var, we have that for any

\[\Pr{|\ip{u_{t_i}}{v}-\ip{Mu_{t_i}}{Mv}|\le\eps\|u_{t_i}\|_2\|v\|_2}\ge\frac{2}{3}\]

for a sketching matrix with $\O{\frac{1}{\eps^2}}$ rows.
Thus by taking a sketching matrix with $d$ rows, for $d=\O{\frac{1}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}+\log\log n\right)}$, and using a standard median-of-means approach, we can take a union bound over all $i\in[q]$.

\[|\ip{u_i}{v}-\ip{Mu_i}{Mv}|\le\eps\|u_i\|_2\|v\|_2,\]

simultaneously for all $i\in[m]$ with probability at least $1-\delta$.

Let $s\in\mathbb{R}^n$ be a sign vector $\{-1,+1\}^n$ with four-wise independent entries.
For any $u,v\in\mathbb{R}^n$, we have

\[\Ex{\langle s,u\rangle\cdot\langle s,v\rangle}=\langle u,v\rangle.\]

By linearity of expectation, we have that

\begin{align*}
\Ex{\langle s,u\rangle\cdot\langle s,v\rangle}&=\Ex{\left(\sum_{i=1}^ns_iu_i\right)\left(\sum_{i=1}^ns_iv_i\right)}\\
&=\Ex{\sum_{i=1}^n\sum_{j=1}^n s_iu_is_jv_j}=\sum_{i=1}^n\sum_{j=1}^n\Ex{s_iu_is_jv_j}.
\end{align*}

Since the variables $s_i$ are $4$-wise independent sign variables $\{-1,+1\}$, then $\Ex{s_is_j}=1$ for $i=j$ and $\Ex{s_is_j}=0$ for $i\neq j$.

\[\Ex{\langle s,u\rangle\cdot\langle s,v\rangle}=\sum_{i=1}^nu_iv_i=\langle u,v\rangle.\]

Let $s\in\mathbb{R}^n$ be a sign vector $\{-1,+1\}^n$ with four-wise independent entries.
For any $u,v\in\mathbb{R}^n$, we have

\[\Var\left(\langle s,u\rangle\cdot\langle s,v\rangle\right)\le(\langle u,v\rangle)^2.\]

Since $\Var{\langle s,u\rangle\cdot\langle s,v\rangle}\le\Ex{\left(\langle s,u\rangle\cdot\langle s,v\rangle\right)^2}$, it follows by linearity of expectation that

\begin{align*}
\Var\left(\langle s,u\rangle\cdot\langle s,v\rangle\right)&\le\Ex{\left(\sum_{i=1}^ns_iu_i\right)^2\left(\sum_{i=1}^ns_iv_i\right)^2}\\
&=\Ex{\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{\ell=1}^n s_is_js_ks_\ell u_iv_ju_kv_\ell}\\
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{\ell=1}^n\Ex{s_is_js_ks_\ell u_iv_ju_kv_\ell}.
\end{align*}

Since the variables $s_i$ are $4$-wise independent sign variables $\{-1,+1\}$, then $\Ex{s_is_js_ks_\ell}=1$ if $i,j,k,\ell$ consists of two (possibly not distinct) pairs of indices, e.g., $i=j$ and $k=\ell$, and $\Ex{s_is_js_ks_\ell}=0$ otherwise.

\[\Var\left(\langle s,u\rangle\cdot\langle s,v\rangle\right)\le\sum_{i=1}^n\sum_{j=1}^n u_iv_iu_jv_j=\left(\langle u,v\rangle\right)^2.\]

We now give our $F_2$ difference estimator using the inner product approximation property.

There exists a $(\gamma,\eps,\delta)$-difference estimator for $F_2$ that uses space

\[\O{\frac{\gamma\log n}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}.\]

Let $\eps'=\frac{\min(1,\eps)}{32}$ and $\delta'=\frac{\delta}{2}$.
Given an oblivious stream $\calS$, let $v$ be the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and $w_t$ be the frequency vector induced by updates from time $t_2$ to $t$ exclusive, with $\gamma\cdot F_2(v)\ge F_2(w_t)$.
Let $M(x)$ represent the output of the algorithm $\estimator$ with accuracy parameter $\eps'$ and failure rate $\delta'$ on an input vector $x$ induced by a stream.
Hence we have $M(x)\in\mathbb{R}^d$, where $d=\O{\frac{\gamma}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$.
We remark that the $\log\log n$ term in the dimension of $d$ from thm:strong:F2 results from the analysis of [11] breaking the stream into $\O{\log n}$ times when the value of $F_2$ on the stream doubles.
We do not need this $\log\log n$ term since $\gamma\cdot F_2(v)\ge F_2(w_t)$ for an absolute constant $\gamma>0$ implies that the value of the difference can only double a constant number of times.

By lem:approx:ip, we have that with probability at least $1-\delta'$,

\[|\ip{v}{w_t}-\ip{M(v)}{M(w_t)}|\le\frac{4\eps'}{\sqrt{\gamma}}\|v\|_2\|w_t\|_2.\]

Recalling the identity

\[F_2(v+w_t)-F_2(v)=2\ip{v}{w_t}+\|w_t\|_2^2,\]

we thus have that

\begin{align*}
\big|\left[F_2(v+w_t)-F_2(v)\right]-&\left[2\ip{M(v)}{M(w_t)}+\|M(w_t)\|_2^2\right]\big|\\
\end{align*}

since $\eps'=\frac{\min(1,\eps)}{32}$.
Because $\gamma\cdot F(v)\ge F(w_t)$, then we have $\|w_t\|_2\le\sqrt{\gamma}\|v\|_2$, so that the total error of the estimator is at most

\[\frac{8\eps'}{\sqrt{\gamma}}\|v\|_2\|w_t\|_2+3\eps'\|w_t\|_2^2\le 8\eps'\cdot F(v)+ 3\eps'\gamma\cdot F(v).\]

Hence for $\gamma\le 2$, the error is at most $14\eps'\cdot F(v)\le\eps\cdot F(v)$.

Since thm:strong:F2 and lem:approx:ip each hold with probability at least $1-\delta'$ for $\delta'=\frac{\delta}{2}$, then the total probability of success is at least $1-\delta$.

By thm:strong:F2, each of the two instances of $\estimator$ uses

\[\O{\frac{\gamma\log n}{(\eps')^2}\left(\log\frac{1}{\eps'}+\log\frac{1}{\delta'}+\log\log n\right)}\]

bits of space, for $\eps'=\frac{\min(1,\eps)}{32}$ and $\delta'=\frac{\delta}{2}$.
However, the $\log\log n$ term in the space requirement of $\estimator$ results from the need to union bound over $\log n$ locations where the value of $F_2$ on the stream increases by a factor of $2$.
Since $\gamma$ is upper bounded by a constant, we only need a union bound over a constant number of locations.
Hence, the space complexity of the $(\gamma,\eps,\delta)$-difference estimator for $F_2$ is

\[\O{\frac{\gamma\log n}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}.\]

Given $\eps>0$, there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation for $F_2$ that uses $\O{\frac{1}{\eps^2}\log^2 n\log^3\frac{1}{\eps}\left(\log\frac{1}{\eps}+\log\log n\right)}$ bits of space and succeeds with probability at least $\frac{2}{3}$.

$F_2$ is a monotonic function with $(\eps,m)$-twist number $\lambda=\O{\frac{1}{\eps}\log n}$, by obs:flip:fp.
By lem:diff:est:F2 and thm:strong:F2, there exists a $(\gamma,\eps,\delta)$-difference estimator that uses space

\[\O{\frac{\gamma\log n}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}\]

and there exists an oblivious strong tracker for $F_2$ that uses space

\[\O{\frac{\log n}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}+\log\log n\right)}.\]

Therefore by using the $(\gamma,\eps,\delta)$-difference estimator and the oblivious strong tracker for $F_2$ in the framework of alg:framework, then thm:framework with $S_1=\log n\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}+\log\log n\right)$, $C=1$, and $S_2=0$ proves that there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation for $F_2$ that uses space $\O{\frac{1}{\eps^2}\log^2 n\log^3\frac{1}{\eps}\left(\log\frac{1}{\eps}+\log\log n\right)}$ and succeeds with constant probability.

Optimized $F_2$ Algorithm.
Instead of maintaining all sketches $\calB_a$ and $\calA_{a,j}$ simultaneously, it suffices to maintain sketches $\calB_a$ and $\calA_{a,j}$ for $\O{\log\frac{1}{\eps}}$ values of $a$ at a time.
Namely, the counter $a$ in alg:framework tracks the active instances $\calB_a$ and $\calA_{a,j}$ output by the algorithm.
Because the output increases by a factor of $2$ each time $a$ increases, it suffices to maintain the sketches $\calB_i$ and $\calA_{i,c}$ for only the smallest $\O{\log\frac{1}{\eps}}$ values of $i$ that are at least $a$.
Any larger index will have only missed $\O{\eps}$ fraction of the $F_2$ of the stream and thus still output a $(1+\eps)$-approximation.

Given $\eps>0$, there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation for $F_2$ that succeeds with probability at least $\frac{2}{3}$ and uses $\O{\frac{1}{\eps^2}\log n\log^4\frac{1}{\eps}\left(\log\frac{1}{\eps}+\log\log n\right)}$ bits of space.

At any point, there are $\O{\log\frac{1}{\eps}}$ active indices $a$ and $\O{1}$ active indices $c$ corresponding to sketches $\calB_{a}$ and $\calA_{a,c}$.
Recall from thm:framework that for fixed $a$, the total space for each $\calA_{a,j}$ across the $\beta$ granularities is

\[\O{\frac{1}{\eps^2}\log^3\frac{1}{\eps}\cdot S_1(n,\delta',\eps)+\frac{1}{\eps}\log\frac{1}{\eps}\cdot S_2(n,\delta',\eps)},\]

where we have $S_1(n,\delta',\eps)=\log n\left(\log\frac{1}{\eps}+\log\frac{1}{\delta'}+\log\log n\right)$ and $S_2=0$ for our $F_2$ difference estimator and $F_2$ strong tracker.

Whereas thm:framework bounds the counter $a$ by $\O{\log n}$ so that we maintain $\O{\log n}$ simultaneous instances of $i$ for the algorithms $\calA_{i,j}$, we observed that it suffices to maintain at most $\O{\log\frac{1}{\eps}}$ simultaneous active values of $i$.
Since there are still $\O{\log n}$ total indices $a$ over the course of the stream, then each sketch must have failure probability $\frac{\delta}{\poly\left(\log n,\frac{1}{\eps}\right)}$ for the entire algorithm to have failure probability $\delta=\frac{2}{3}$.
Finally, there are $\O{\log\frac{1}{\eps}}$ active indices of $a$, consisting of $\O{\frac{1}{\eps}}$ subroutines.
Thus, it takes $\O{\frac{1}{\eps}\log n\log\frac{1}{\eps}}$ additional bits of space to store the splitting times for each of the $\O{\frac{1}{\eps}\log\frac{1}{\eps}}$ active subroutines across a stream of length $m$, with $\log m=\O{\log n}$.
Thus the total space required is $\O{\frac{1}{\eps^2}\log n\log^4\frac{1}{\eps}\left(\log\frac{1}{\eps}+\log\log n\right)}$.

As a simple corollary, note that our framework also solves the $L_2$-heavy hitters problem.
By running separate $L_2$-heavy hitters algorithms corresponding to each difference estimator $\calA$ and strong tracker $\calB$, with the heavy-hitter threshold corresponding to the accuracy of each procedure, we obtain a list containing all the possible heavy-hitters along with an estimated frequency of each item in the list.

For any $\eps>0$ and $\delta\in[0,1)$, there exists a streaming algorithm $(\eps,\delta)-\bptree$, that with probability at least $1-\delta$, returns a set of $\frac{\eps}{2}$-heavy hitters containing every $\eps$-heavy hitter and an approximate frequency for every item returned with additive error $\frac{\eps}{4}\cdot L_2$.
The algorithm uses $\O{\frac{1}{\eps^2}\left(\log\frac{1}{\delta\eps}\right)(\log n+\log m)}$ bits of space.

Given $\eps>0$, there exists an adversarially robust streaming algorithm $\heavyhitters$ that solves the $L_2$-heavy hitters problem with probability at least $\frac{2}{3}$ and uses $\O{\frac{1}{\eps^2}\log n\log^4\frac{1}{\eps}\left(\log\frac{1}{\eps}+\log\log n\right)}$ bits of space.

For each integer $j\ge 0$ and a fixed integer $i$, let $u_{i,j}$ be the last round for which $Z_{i,j}$ in alg:framework is defined.
As before, let $t_i$ be the update time during which the counter $a$ in alg:framework is first set to $i$ for any integer $i>0$.
Let $t^{(b)}_i$ be the first round such that the counter $b$ in alg:framework is first set to $j$, and we use the convention that $t^{(0)}_i=t_i$.

Let $\mathcal{E}_1$ be the event that $X_a$ is a $\left(1+\frac{\eps}{32}\right)$-approximation to $F_2(1,t_a)$ and $\mathcal{E}_2$ be the event that $F(1,u_{a,j})-F(1,t_{a,j})\le\frac{1}{2^{\beta-j-3}}F(1,t_a)$ for each positive integer $j>1$.
By lem:constant and lem:time:geometric, we have $\PPr{\mathcal{E}_1\wedge\mathcal{E}_2}\ge 1-\O{\frac{\delta\log n}{\eps}}$.

Suppose there exists $r\in[n]$ such that $(f_r)^2\ge\eps^2 F_2(1,m)$.
Then coordinate $r$ must either be $\frac{\eps^2}{32^2}$-heavy with respect to $F_2(1,t_a)$ or $\frac{2^k\cdot\eps^2}{32^2\beta^2}$-heavy with respect to $F_2(t_{a,k},t_{a,k-1})$ for some integer $k\in[\beta]$, where we use the convention that $t_{a,0}=t_a$.

Hence $\bptree$ with threshold $\frac{2^k\cdot\eps^2}{32^2\beta^2}$ with respect to $F_2(t_{a,k},t_{a,k-1})$ will detect that $r$ is heavy.
Moreover, note that if coordinate $r$ is only reported as heavy in an algorithm corresponding to the level $k$ difference estimator, then $\O{\eps^2}\cdot F_2$ of the contribution of coordinate $r$ towards the overall $F_2$ still appears after $r$ is reported as a heavy-hitter.
Thus by keeping track of the frequency of $r$ after it is reported, we obtain an estimate of the frequency of $r$ up to an additive $\O{\eps}\cdot L_2$.
Since this is also the accuracy parameter of $\calA_{a,k}$, then the space complexity follows.

§ ROBUST FP ESTIMATION FOR 0<P<2

In this section, we use the framework of sec:framework to give an adversarially robust streaming algorithm for $F_p$ moment estimation, where $p\in(0,2)$.
As before, we require an $F_p$ strong tracker and an $F_p$ difference estimator in order to apply thm:framework.
Whereas the $F_2$ difference estimator was straightforward from the inner product approximation via $F_2$ approximation property, it is not clear that such a formulation exists for $F_p$ approximation.
Instead, we use separate sketches for our $F_p$ strong tracker and our $F_p$ difference estimator.
We present these subroutines in this section.
Finally, we again optimize our algorithm beyond the guarantees of thm:framework so that our final space guarantees in thm:robust:opt:Fp:smallp matches the best known $F_p$ algorithm on insertion-only streams, up to $\poly\left(\log\frac{1}{\eps},\log n\right)$ terms.

We first require the following definition for $p$-stable distributions, which will be integral to both our $F_p$ strong tracker and our $F_p$ difference estimator.

[88]
For $0<p\le 2$, there exists a probability distribution $\calD_p$ called the $p$-stable distribution so that for any positive integer $n$ with $Z_1,\ldots,Z_n\sim\calD_p$ and vector $x\in\mathbb{R}^n$, then $\sum_{i=1}^n Z_ix_i\sim\|x\|_pZ$ for $Z\sim\calD_p$.

The probability density function $f_X$ of a $p$-stable random variable $X$ satisfies $f_X(x)=\Theta\left(\frac{1}{1+|x|^{1+p}}\right)$ for $p<2$, while the normal distribution corresponds to $p=2$.
Moreover, [73] details standard methods for generating $p$-stable random variables by taking $\theta$ uniformly at random from the interval $\left[-\frac{\pi}{2},\frac{\pi}{2}\right]$, $r$ uniformly at random from the interval $[0,1]$, and setting

\[X=f(r,\theta)=\frac{\sin(p\theta)}{\cos^{1/p}(\theta)}\cdot\left(\frac{\cos(\theta(1-p))}{\log\frac{1}{r}}\right)^{\frac{1}{p}-1}.\]

These $p$-stable random variables are crucial to obtaining a strong $F_p$ tracking algorithm.

[11]
For $0<p<2$, there exists an insertion-only streaming algorithm $\psketch(1,t,\eps,\delta)$ that uses $\O{\frac{\log n}{\eps^2}\left(\log\log n+\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$ bits of space and provides $(\eps,\delta)$-strong $F_p$ tracking.

Unfortunately, $\psketch$ is based on the $p$-stable sketch of [51], which offers a conceptual promise for the existence of the quantile estimators needed to guarantee provable bounds, but not an explicit computation.
Thus adapting the analysis of $\psketch$ in [51, 11] for the purposes of our difference estimator seems to be a challenge.
Even for the case $p=1$, it does not seem evident how to adapt the median estimator of $\psketch$ to obtain a difference estimator for $F_p$.

Instead, we describe a formulation of Li's geometric mean estimator [63], which also provides a streaming algorithm for $F_p$, but was not previously known to offer strong tracking.
For a positive integer $q\ge3$, let $d$ be a multiple of $q$ and let $A\in\mathbb{R}^{d\times n}$ have independent $p$-stable random variables for the entries of $A$.
Then for a vector $x\in\mathbb{R}^n$ and $y=Ax$, let $z_i:=C_{q,p}\cdot\left(\prod_{j=q(i-1)+1}^{qi}|y_j|^{p/q}\right)$ be the geometric mean of the inner products of $q$ random $p$-stable vectors with the vector $x$, where

\[C_{q,p}=\left[\frac{2}{\pi}\cdot\Gamma\left(1-\frac{1}{q}\right)\cdot\Gamma\left(\frac{p}{q}\right)\cdot\sin\left(\frac{\pi p}{2q}\right)\right]^{-q}.\]

We have the following characterization of the asymptotic behavior of $C_{q,p}$:
[Characterization of $C_{q,p}$]
[63]
$C_{q,p}=\O{\exp(\gamma_e(q-1))}$, for the Euler-Mascheroni constant $\gamma_e\approx 0.57721$.

The value of $C_{q,p}$ is chosen so that each $z_i$ is an unbiased estimate of $\|x\|_p^p$, as a result of the following statement.
We can then bound the expectation and the variance of each random variable.

Let $d$ be an integer multiple of an integer $q\ge 3$ and let $A\in\mathbb{R}^{d\times n}$ have independent $p$-stable random variables for the entries of $A$.
For a vector $x\in\mathbb{R}^n$ and $y=Ax$, let $z_i:=C_{q,p}\cdot\left(\prod_{j=q(i-1)+1}^{qi}|y_j|^{p/q}\right)$ be the geometric mean of the inner products of $q$ random $p$-stable vectors with the vector $x$.
Then $\Ex{z_i}=\|x\|_p^p$ and for $\xi:=\frac{C_{\frac{q}{2},p}}{C_{q,p}}$, we have $\Ex{z_i^2}\le\left(\xi^2-1\right)\cdot\|x\|_p^{2p}$.

Thus by taking the arithmetic mean of $\O{\frac{1}{\eps^2}}$ variables $z_i$, we obtain a $(1+\eps)$-approximation to $\|x\|_p^p$ with constant probability by Chebyshev's inequality.

§.§ Fp Difference Estimator for 0<p<2

We now describe our $F_p$ difference estimator and give the high-level details of the analysis. We use Li's geometric mean estimator to maintain $A(v+w_t)$ and $Av$, where $A$ is the sketching matrix for Li's geometric mean estimator, and $v$ and $w_t$ are frequency vectors.
Observe that if we computed $A(v+w_t)-Av$, then we would obtain $A(w_t)$, which is a sketch that allows us to recover $F_p(w_t)$.
However, we want to estimate $F_p(v+w_t)-F_p(v)$ rather than $F_p(w_t)$.
Instead, we use the sketches $A(v+w_t)$ and $Av$ to compute terms $z_1,z_2,\ldots,z'_1,z'_2,\ldots$, where each $z_i$ is the geometric mean of $q$ consecutive entries in $A(v+w_t)$ and similarly $z'_i$ is the geometric mean of $q$ consecutive entries in $Av$.
Since $z_i$ is an unbiased estimator of $F_p(v+w_t)$ and $z_i$ is an unbiased estimator of $F_p(v)$, it follows that $z_i-z'_i$ is an unbiased estimator of $F_p(v+w_t)-F_p(v)$.
We take the average of the values $z_i-z'_i$ across $\O{\frac{1}{\eps^2}}$ indices of $i$ to obtain a single estimate and take the median of all estimates.
The challenge is achieving both the variance bounds on $z_i-z'_i$ while also obtaining a strong tracking property.
To bound the variance, we expand $z_i-z'_i$ to be a sum of $2^q-1$ geometric means of $q$ terms, each with at least one term $(\ip{A_j}{w_t})^{p/q}$.
Since $A_j$ is a vector of $p$-stable entries, then $(\ip{A_j}{w_t})^{p/q}$ has the same distribution as $(\|w_t\|_p\cdot X)^{p/q}$ for a $p$-stable random variable $X$.
We also have $F_p(w_t)=\gamma\cdot F(v)$, where $\gamma$ is bounded by some absolute constant.
Thus we can bound the probability that $(\ip{A_j}{w_t})^{p/q}\ge\|v\|^{p/q}_p$.

* Let $A$ be a $d\times n$ random matrix whose entries are i.i.d from the $p$-stable distribution $\calD_p$, for $d=\O{\frac{\gamma^{2/p}}{\eps^2}\left(\log\frac{1}{\eps}+\log\log n\right)}$