* For a parameter $q=3$, let each $z_i=\prod_{j=q(i-1)+1}^{qi}(Av+Aw_t)_j^{p/q}$ and $z'_i=\prod_{j=q(i-1)+1}^{qi}(Av)_j^{p/q}$.

* Output the arithmetic mean of $(z_1-z'_1),(z_2-z'_2),\ldots,(z_{d/q}-z'_{d/q})$.

Difference estimator for $F_p(v+w_t)-F_p(w_t)$ with $0<p<2$

Let $p\in(0,2)$ and $\calS$ be an oblivious stream on which $v$ is the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and let $u$ is the frequency vector induced by the updates of $\calS$ from time $t_2$.
Suppose $F_p(v+u)-F_p(v)\le\gamma F_p(v)$ and $F_p(u)\le\gamma F_p(v)$.
Then for each $i\in[d/q]$, $z_i$, and $z'_i$ as defined in fig:diff:est:smallp, we have $\Ex{z_i-z'_i}=F_p(v+u)-F_p(u)$ and

\[\Var(z_i-z'_i)\le2^{2q}\gamma^{2/p}\|v\|_p^{2p}=2^{2q}\gamma^{2/p}(F_p(v))^2.\]

For an oblivious stream $\calS$, let $v$ be the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and let $u$ be the frequency vector induced by the updates of $\calS$ from time $t_2$ so that $F_p(v+u)-F_p(v)\le\gamma F_p(v)$ and $F_p(u)\le\gamma F_p(v)$.
For any integer $d>0$, let $A\in\mathbb{R}^{d\times n}$ be a matrix whose entries are drawn i.i.d. from the $p$-stable distribution $\calD_p$.

Recall that Li's geometric mean estimator first takes a geometric mean $z_i$ of $q$ separate inner products, where $i\in\left[\frac{d}{q}\right]$.
Explicitly, each variable $z_i$ in the estimator takes the form

\begin{align*}
\end{align*}

where $A_j$ is the $j$-th column of $A$.
We define

\[T_i:=\prod_{j=q(i-1)+1}^{qi}\left(1+\frac{\ip{A_j}{u}}{\ip{A_j}{v}}\right)^{p/q}.\]

Similarly, Li's geometric mean estimator for $v$ is a $(1+\eps)$-approximation for $\|v\|_p^p=F_p(v)$ and each variable $z'_i$ in the estimator takes the form

\[z'_i:=C_{q,p}\cdot\prod_{j=q(i-1)+1}^{qi}\left(\ip{A_j}{v}\right)^{p/q}.\]

By ligeoest:var, $z_i$ and $z'_i$ are unbiased estimators for $F_p(v+u)$ and $F_p(v)$ respectively, so that $z_i-z'_i$ is an unbiased estimator for $F_p(v+u)-F_p(v)$,

\[\Ex{z_i-z'_i}=F_p(v+u)-F_p(v).\]

We can also expand $z_i-z'_i$ so that

\[z_i-z'_i=C_{q,p}\cdot(T_i-1)\cdot\prod_{j=q(i-1)+1}^{qi}\left(\ip{A_j}{v}\right)^{p/q}.\]

To bound the variance of $z_i-z'_i$, we first require the following structural inequality to handle the terms inside of the product of $T_i$:

For $a,b\ge 0$ and $p\le 2$, we have $(a+b)^{p/q}\le a^{p/q}+2b^{p/q}$.

For $0\le a\le b$ and $p\le 2\le q$, we have

\[(a+b)^{p/q}\le(2b)^{p/q}\le 2b^{p/q}\le a^{p/q}+2b^{p/q}.\]

For $0\le b\le a$ and $p\le 2\le q$, we have from Bernoulli's inequality that

\[(a+b)^{p/q}=a^{p/q}\left(1+\frac{b}{a}\right)^{p/q}\le a^{p/q}\left(1+\frac{pb}{qa}\right)\le a^{p/q}+b^{p/q}.\]

By clm:ab, we have

\[T_i\le\prod_{j=q(i-1)+1}^{qi}\left(1+\left(\frac{\ip{A_j}{u}}{\ip{A_j}{v}}\right)^{p/q}\right).\]

Hence, $T_i-1$ is a sum of $2^q-1$ terms and similarly, $z_i-z'_i$ is a sum of $2^q-1$ product of $q$ terms, each with at least one term $(\ip{A_j}{u})^{p/q}$.
For example, one term in $z_1-z'_1$ is

\[C_{q,p}(\ip{A_1}{u})^{p/q}(\ip{A_2}{v})^{p/q}(\ip{A_3}{v})^{p/q}\ldots(\ip{A_q}{v})^{p/q},\]

while another term is

\[C_{q,p}(\ip{A_1}{v})^{p/q}(\ip{A_2}{u})^{p/q}(\ip{A_3}{v})^{p/q}\ldots(\ip{A_q}{v})^{p/q}.\]

By ligeoest:var, each of these terms has second moment at most $(\xi^2-1)\gamma^{2/p}\|v\|_p^{2p}$ for $\xi=\frac{C_{\frac{q}{2},p}}{C_{q,p}}$.
Thus the sum of the $2^q-1$ terms has second moment at most $(2^q)^2(\xi^2-1)\gamma^{2/p}\|v\|_p^{2p}$, so that the variance of the sum is at most $\O{2^{2q}\gamma^{2/p}\|v\|_p^{2p}}$.
That is,

\[\Var(z_i-z'_i)\le2^{2q}\gamma^{2/p}\|v\|_p^{2p}=2^{2q}\gamma^{2/p}(F_p(v))^2.\]

Let $p\in(0,2)$, $\delta,\eps\in(0,1)$, and $\calS$ be an oblivious stream on which $v$ is the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and let $u$ is the frequency vector induced by the updates of $\calS$ from time $t_2$.
Suppose $F_p(v+u)-F_p(u)\le\gamma F_p(v)$ and $F_p(u)\le\gamma F_p(v)$.
Then there exists an algorithm that uses a sketch of dimension $d=\O{\frac{\gamma^{2/p}}{\eps^2}\left(\log\frac{1}{\delta}\right)}$ and outputs an additive $\eps\cdot F_p(v)$ approximation to $F_p(v+u)-F_p(u)$ with probability at least $1-\delta$.

For each $i\in[d/q]$, with  $z_i$, and $z'_i$ defined in fig:diff:est:smallp, we have from lem:exp:var:smallp that $\Ex{z_i-z'_i}=F_p(v+u)-F_p(u)$ and

\[\Var(z_i-z'_i)\le2^{2q}\gamma^{2/p}\|v\|_p^{2p}=2^{2q}\gamma^{2/p}(F_p(v))^2.\]

Thus by Chebyshev's inequality, the arithmetic mean of $\O{\frac{2^{2q}\gamma^{2/p}}{\eps^2}}$ differences $z_i-z'_i$ suffices to obtain additive $\eps F_p(v)$ error of the difference $F_p(v+u)-F_p(v)$ with probability at least $\frac{2}{3}$.
The probability of success can then be boosted to $1-\delta$ by taking the median of $\O{\log\frac{1}{\delta}}$ such instances.

To obtain the strong tracking property and avoid extra $\log n$ factors, this argument needs to be interleaved with carefully chosen values of $w_t$ and bounding the supremum of $(\ip{A_j}{w_t})^{p/q}$ across all values of $w_t$, rather than considering each inner product separately and taking a union bound.
We split the stream into $\O{\frac{1}{\eps^{16q/p^2}}}$ times $u_1,u_2,\ldots$ between which the difference estimator increases by roughly $\eps^{16q/p^2}\cdot F_p(v)$ 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 $u_i$ and $u_{i+1}$ for a fixed $i$, we note that the difference estimator only increases by roughly $\eps^{16q/p^2}\cdot F_p(v)$ from $u_i$ to $u_{i+1}$, so that we still obtain a $(1+\eps)$-approximation to $F_p(v+w_t)-F_p(v)$ with a $\eps^{1-16q/p^2}$-approximation to the difference, for a frequency vector $w_t$ induced by updates between $u_i$ and $u_{i+1}$.
We then bound the probability that the supremum of the error between times $u_i$ and $u_{i+1}$ is bounded by $\eps^{1-16q/p}$ by applying chaining results from [9, 8, 11] that bound the supremum of a random process.

We first require the following structural property that bounds the supremum of the inner product of a random process with a vector of independent $p$-stable random variables.

[11]
Let $x^{(1)},x^{(2)},\ldots,x^{(m)}\in\mathbb{R}^n$ satisfy $0\preceq x^{(1)}\preceq\ldots\preceq x^{(m)}$.
Let $Z\in\mathbb{R}^n$ be a vector of entries that are i.i.d. sampled from the $p$-stable random distribution $\calD_p$.
Then for some constant $C_p$ depending only on $p$, we have

\[\PPr{\underset{k\le m}{\sup}|\ip{Z}{x^{(k)}}|\ge\lambda\|x^{(m)}\|_p}\le C_p\left(\frac{1}{\lambda^{2p/(2+p)}}+n^{-1/p}\right).\]

For $0<p<2$, it suffices to use a sketching matrix $A\in\mathbb{R}^{d\times n}$ of i.i.d. entries drawn from the $p$-stable distribution $\calD_p$, with dimension

\[d=\O{\frac{\gamma^{2/p}}{\eps^2}\left(\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}\]

to obtain a $(\gamma,\eps,\delta)$-difference estimator for $F_p$.

For an oblivious stream $\calS$, let $v$ be the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and let $u_i$ be the frequency vector induced by the updates of $\calS$ from time $t_2+1$ to the last time when

\[\max(F_p(u_i),F_p(v+u_1+\ldots+u_i)-F_p(v+u_1+\ldots+u_{i-1}))\le\frac{1}{2^{q^2}}\eps^{16q/p^2}\cdot F_p(v),\]

for some fixed constant $q\ge 3$.
We first show that our difference estimator gives an $\eps\cdot F_p(v)$ approximation to $F_p(v+u_i)-F_p(v)$ for each $i=\O{\frac{1}{\eps^{16q/p^2}}}$.
Let $\mathcal{E}$ be the event that we obtain a $(1+\O{\eps})$-approximation to both $F_p(v+u_i)$ and $F_p(v)$ for all $\O{\frac{1}{\eps^{16q/p^2}}}$ vectors $u_i$.
By cor:diff:est:Fp:smallp:once, we have $\PPr{\mathcal{E}}\ge 1-\frac{\poly(\eps,\delta)}{2}$ for an instance that uses $d=\O{\frac{\gamma^{2/p}}{\eps^2}\log\frac{1}{\eps\delta}}$ rows in the sketching matrix $A$ whose entries are i.i.d. sampled from the $p$-stable distribution $\calD_p$.
We thus condition on the event $\mathcal{E}$ and assume we have additive $\O{\eps}\cdot F(v)$ approximations at all times $u_i$.
Let $w_t$ be a frequency vector induced by updates from time $u_i$ and $u_{i+1}$, so that $F_p(w_t)\le\frac{1}{2^{q^2}}\eps^{16q/p^2}\cdot F_p(v)$.
It then suffices to show that the output of the difference estimator of $F_p(v+w_t)-F_p(v)$ at most $\O{\eps}\cdot F_p(v)$ for all values of $w_t$ over the stream, since such a result proves that the difference estimator changes by at most $\O{\eps}\cdot F_p(v)$ between times $u_i$ and $u_{i+1}$ and conditioning on $\mathcal{E}$, we already have additive $\O{\eps}\cdot F(v)$ approximations at all times $u_i$.
The claim would then follow by monotonicity of $F_p$.

We use the same computation as in cor:diff:est:Fp:smallp:once to reduce the differences of the geometric means.
That is, our difference estimator first takes a geometric mean $z_i$ of $q$ separate inner products, where $i\in\left[\frac{d}{q}\right]$, formed from the entries of $A(v+w_t)$.
Explicitly, each variable $z_i$ in the estimator takes the form

\begin{align*}
\end{align*}

where $A_j$ is the $j$-th column of $A$.
Similarly, each variable $z'_i$ in the estimator formed from the entries of $Av$ takes the form

\[z'_i:=C_{q,p}\cdot\prod_{j=q(i-1)+1}^{qi}\left(\ip{A_j}{v}\right)^{p/q}.\]

As in cor:diff:est:Fp:smallp:once we can write $z_i-z'_i$ as a sum of $2^q-1$ geometric means of $q$ terms, each with at least one term $(\ip{A_j}{w_t})^{p/q}$, e.g., one term in $z_1-z'_1$ is

\[C_{q,p}(\ip{A_1}{w_t})^{p/q}(\ip{A_2}{v})^{p/q}(\ip{A_3}{v})^{p/q}\ldots(\ip{A_q}{v})^{p/q},\]

while another term is

\[C_{q,p}(\ip{A_1}{v})^{p/q}(\ip{A_2}{w_t})^{p/q}(\ip{A_3}{v})^{p/q}\ldots(\ip{A_q}{v})^{p/q}.\]

Thus by lem:chain:lp with $\lambda=\frac{1}{\eps^{8/p}}$, we have

\[\PPr{\underset{t\le t_2}{\sup}|\ip{A_i}{w_t}|\ge\lambda\|w_t\|_p}\le C_p\left(\eps^{16/(2+p)}+n^{-1/p}\right)\]

and similarly

\[\PPr{\underset{t\le t_2}{\sup}|\ip{A_i}{v}|\ge\lambda\|v\|_p}\le C_p\left(\eps^{16/(2+p)}+n^{-1/p}\right).\]

Thus with probability at least $1-\O{\eps^4}$, none of the $2^q-1$ terms exceeds

\[\lambda^p\|w_t\|_p^{p/q}\|v\|^{(q-1)p/q}_p\le\frac{1}{\eps^8}\|w_t\|_p^{p/q}\|v\|^{(q-1)p/q}_p\le\frac{\eps^8}{2^q}\cdot F_p(v),\]

since $F_p(w_t)\le\frac{1}{2^{q^2}}\eps^{64q/p^2}\cdot F_p(v)$.
Hence, the sum of the $2^q-1$ terms is at most $\eps^8\cdot F(v)$, with probability at least $1-\O{2^q\eps^4}$.
In other words, some particular difference of geometric means is at most $\eps^8\cdot F(v)$, with probability at least $1-\O{2^q\eps^4}$.
Taking a union bound over $\O{\frac{1}{\eps^2}}$ geometric means, then the difference estimator $F_p(v+w_t)-F_p(v)$ outputs a value that is at most $\eps^8\cdot F(v)$, with constant probability, for sufficiently small $\eps$.
Finally, if we take the median of $\O{\log\frac{1}{\delta}}$ such estimators, then we can increase the probability of success to at least $1-\delta$.
As previously noted, this shows that the difference estimator provides strong tracking over the entire stream.

Because each entry takes $\O{\log n}$ bits of space, then for constant $q$ and a sketch with $d=\O{\frac{\gamma^{2/p}}{\eps^2}\log\frac{1}{\eps}+\log\frac{1}{\delta}}$ rows, the total space required is

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

since we require a rescaling of $\delta'=\frac{\delta}{\poly\left(\frac{1}{\eps}\right)}$ to union bound over the $\poly\left(\frac{1}{\eps}\right)$ times $\{u_i\}$.

Derandomization of $p$-stable random variables.
To handle the generation and storage of the entries of $A$ drawn i.i.d. from the $p$-stable distribution $\calD_p$, we first note the following derandomization.

Let $\calA$ be any streaming algorithm that stores only a linear sketch $A\cdot f$ on a stream vector $f\in\{-M,\ldots,M\}^n$ for some $M=\poly(n)$, such that the entries of $A\in\mathbb{R}^{k\times n}$ are i.i.d., and can be sampled using $\O{\log n}$ bits.
Then for any fixed constant $c\ge 1$, $\calA$ can be implemented using a random matrix $A'$ using $\O{k\log n(\log\log n)^2}$ bits of space, such that for all $y\in\mathbb{R}^k$ with entry-wise bit complexity of $\O{\log n}$,

\[|\PPr{A\cdot f=y}-\PPr{A'\cdot f=y}|<n^{-ck}.\]

We cannot immediately apply lem:derandom:once because our difference estimator actually stores $A\cdot(v+w_t)$ and $A\cdot v$ and requires the entries of $A$ to be i.i.d. We thus require the following generalization:

For a constant $q\ge 1$, let $f_1,\ldots,f_q\in\{-M,\ldots,M\}^n$ for some $M=\poly(n)$ be vectors defined by a stream so that $f_i$ is defined by the updates of the stream between given times $t_{i,1}$ and $t_{i,2}$, for each $i\in[q]$.
Let $\calA$ be any streaming algorithm that stores linear sketches $A\cdot f_1,\ldots,A\cdot f_q$ , such that the entries of $A\in\mathbb{R}^{k\times n}$ are i.i.d. that can be sampled using $\O{\log n}$ bits, and outputs $g(A\cdot f_1,\ldots,A\cdot f_q)$ for some composition function $g:\mathbb{R}^q\to\mathbb{R}$.
Then for any fixed constant $c\ge 1$, $\calA$ can be implemented using a random matrix $A'$ using $\O{k\log n(\log\log n)^2}$ bits of space, such that for all $y\in\mathbb{R}^k$ with entry-wise bit complexity of $\O{\log n}$,

\[|\PPr{g(A\cdot f_1,\ldots,A\cdot f_q)=y}-\PPr{g(A'\cdot f_1,\ldots,A'\cdot f_q) = y}|<n^{-ck}.\]

We first assume without loss of generality that all entries of $A\cdot f_i$ are integers bounded by $\poly(n)$ for each $i\in[q]$, due to the bit complexity of $A$ and $f_i$.
Let $w_i=A\cdot f_i$ for each $i\in[q]$ and suppose the maximum entry, denoted $\|A\|_\infty$, satisfies $\|A\|_\infty\le n^\alpha$ for some constant $\alpha$.
Let $N=M\cdot n^\alpha$ so that $\|A\cdot f_i\|_\infty\le N$ for all $i\in[q]$.
Define the vector $v=\sum_{i=1}^q N^{2i} w_i$ so that $\|v\|_{\infty}<N'$ for $N'=N^{3q}$.
Note that $N'=\poly(n)$ so that all entries of $v$ can be stored in $\O{\log n}$ bits.
Moreover, observe that each coordinate $v_j$ with $j\in[n]$ has a unique $N^2$-ary representation.
Thus if $v_j=\sum_{i=1}^q N^{2i} w_{i,j}$ where $w_{i,j}$ represents the $j$-th coordinate of vector $w_i$, then the system $v_j=\sum_{i=1}^q N^{2i}\alpha_i$ constrained to the condition that $|\alpha_i|\le N$ for all $i\in[q]$ has a unique solution.
Hence, the vectors $w_i=A\cdot f_i$ can be computed from the vector $v$.

By lem:derandom:once, we can use a random matrix $A'$ with $\O{k\log n(\log\log n)^2}$ bits of space and have for all $y \in \mathbb{R}^k$ with entry-wise bit complexity of $O(\log n)$, that:

\[|\PPr{A\cdot v=y}-\PPr{A'\cdot v=y}|<n^{-ck}.\]

Since any $\mathcal{A}$ that computes $A\cdot v$ can compute the vectors $A\cdot f_1,\ldots,A\cdot f_q$ by the above argument, $\mathcal{A}$ can then compute the composition $g(A\cdot f_1,\ldots, A\cdot f_q)$.
Hence it follows that

\[|\PPr{g(A\cdot f_1,\ldots,A\cdot f_q)=y}-\PPr{g(A'\cdot f_1,\ldots,A'\cdot f_q)}|<n^{-ck}.\]

We now argue that the pseudorandom generator of lem:derandom:many suffices to derandomize the correctness guarantees of our difference estimator.

For $0<p<2$, there exists a $(\gamma,\eps,\delta)$-difference estimator for $F_p$ that uses space

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

The difference estimator for $F_p(v+u)-F_p(v)$ is given an input splitting time $t_1$.
We then need to argue correctness over all possible stopping times $t$ with $t>t_1$, such that $F_p(v+u)-F_p(v)\le\gamma F_p(v)$ for $p<1$ or $F_p(u)\le\gamma F_p(v)$ for $p\ge 1$.
By lem:derandom:many applied with $q = 2$, there exists a pseudorandom generator that succeeds with high probability $1-\frac{1}{\poly(n)}$ over a specific value of $t$.
Since the stream has length $m=\poly(n)$, by taking a union bound over all $\poly(n)$ choice of the stopping times $t$, we have that the pseudorandom generator is also correct with high probability over all possible stopping times $t$.
Thus from lem:sketching:Fp:smallp, we obtain the following guarantees of our difference estimator.

In particular, we remark that the guarantees of the difference estimator only require that the marginal distribution is correct at all times, rather than the joint distribution is correct.
Recall that the difference estimator is used to choose a final stopping time for the purposes of the framework in thm:framework when its output is sufficiently large.
Specifically, the framework takes a set of outputs $s_{t_1+1},\ldots, s_t$ from the difference estimator over the course of the stream and chooses a final stopping time $t_2$ based on the first output that exceeds a certain threshold $T$.
We emphasize that our argument does not rely on fooling the final stopping time $t_2$ chosen by the framework, since it requires a conditional statement on the set $s_{t_1+1},\ldots, s_t$ of outputs from the difference estimator not exceeding the threshold $T$.

For example, consider a scenario where the probability over the choice of independent $p$-stable random variables that $s_{t_1+1}$ exceeds $T$ is $\frac{1}{2}$ and the probability that $s_{t_1+2}$ exceeds $T$ is $\frac{1}{2}$, i.e., $\PPr{s_{t_1+1}\ge T}=\frac{1}{2}$ and $\PPr{s_{t_1+2}\ge T} = \frac{1}{2}$.
However, suppose that conditioned on the event that $s_{t_1+1}<T$, we have that $s_{t_1+2}$ cannot exceed $T$, so that $\PPr{s_{t_1+2}\ge T|s_{t_1+1}<T}=0$.
Then since thm:framework chooses the first time that exceeds $T$, the framework can never choose $t_1+2$, i.e., $\PPr{t_2=t_1+2}=0$.
Since our derandomization does not use independent $p$-stable random variables and only fools the marginal probabilities (of a pair of times $(t, t_1)$ for each $t > t_1$), we need not fool the joint distribution, and thus not fool the choice of stopping time.
Hence, it could be that thm:framework using our derandomized difference estimator selects $t_2=t_1+2$.
On the other hand, $t_1+2$ is still a valid stopping time if the difference estimator is correct at time $t_1+1$, and the output does not exceed $T$.

In other words, while the geometric mean estimator can be fooled by fooling a constant a number of half-space queries, we may need to condition on $\poly(n)$ intermediate stream positions.
Instead, we note that the derandomization of our difference estimator provides the same correctness guarantees.
Thus, even though the difference estimator with the pseudorandom generator could induce a different distribution on the final stopping time, the final stopping time $t'_2$ output by our derandomized algorithm and the algorithm itself can be used in our framework because $t'_2$ corresponds to the first output of the algorithm that exceeds the threshold $T$. We also have correctness at all intermediate times between $t_1$ and $t'_2$.

Bit complexity and rounding of $p$-stable random variables.
We remark that for each inner product in lem:diff:est:Fp:smallp to be stored in $\O{\log n}$ bits of space, then each randomly generated $p$-stable random variable must also be rounded to $\O{\log n}$ bits of precision.
Due to the rounding, that each summand changes additively by $\frac{1}{\poly(n)}$, so that the total estimate also changes by an additive $\frac{1}{\poly(n)}$, so that the total error for the estimate of $F_p(v+u)-F_p(v)$ is $\eps\cdot F_p(v)+\frac{1}{\poly(n)}$.
The additive $\frac{1}{\poly(n)}$ can be absorbed into the $\eps\cdot F(v)$ term with a rescaling of $\eps$ unless $F_p(v)=0$.
However, in the case $F_p(v)=0$, then our estimator will output $0$ anyway, so that the rounding of the $p$-stable random variables still gives an additive $\eps\cdot F(v)$.

§.§ Fp Estimation Algorithm

We now give an adversarially robust streaming algorithm for $F_p$ moment estimation with $p\in(0,2)$ by using thm:framework.

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

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

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

and an oblivious strong tracker $\psketch$ for $F_p$ that uses space

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

Therefore by using the $(\gamma,\eps,\delta)$-difference estimator and the oblivious strong tracker for $F_p$ in the framework of alg:framework, then consider applying thm:framework with parameters $C=2/p\ge 1$, $S_1(n,\delta,\eps)=\frac{1}{\eps}\log n(\log\log n)^2\left(\log\log n+\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)$, and $S_2=0$.
Namely, thm:framework gives an adversarially robust streaming algorithm that outputs a $(1+\eps)$ for $F_p$ that succeeds with constant probability and uses space

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

Optimized $F_p$ Algorithm.
To improve the space dependency, we use the same technique as in sec:F2.
That is, recall that the counter $a$ in alg:framework tracks the active instances $\calA_a$ and $\calB_{a,c}$ output by the algorithm.
Then we only maintain the most sketches $\calA_i$ and $\calB_{i,c}$ for the smallest $\O{\log\frac{1}{\eps}}$ values of $i$ that are at least the value of the counter $a$, instead of maintaining $\O{\log n}$ total sketches.
Because the output increases by a factor of $2$ each time $a$ increases, any larger index will have only missed $\O{\eps}$ fraction of the $F_p$ of the stream and thus still output a $(1+\eps)$-approximation.

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

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

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

where for our purposes, $S_1(n,\delta',\eps)=\log n(\log\log n)^2\left(\log\frac{1}{\eps}+\log\frac{1}{\delta'}+\log\log n\right)$ and $S_2=0$ for our $F_p$ strong tracker and $F_p$ difference estimator.
Since there are $\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}$.
However, since we maintain at most $\O{\log\frac{1}{\eps}}$ simultaneous active values of $a$, then the $\O{\frac{1}{\eps^{2}}\log n(\log\log n)^2\log\frac{1}{\eps}\left(\log\log n+\log\frac{1}{\eps}\right)}$ bits of space are required to perform the sketching stitching and granularity changing framework.
Since there are $\O{\log\frac{1}{\eps}}$ active indices of $a$, consisting of $\O{\frac{1}{\eps}}$ subroutines, then 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}$.
Hence, the total space required is $\O{\frac{1}{\eps^{2}}\log n(\log\log n)^2\log\frac{1}{\eps}\left(\log\log n+\log\frac{1}{\eps}\right)}$.

Similarly, we have:

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

Finally, we remark that our analysis for lem:diff:est:Fp:smallp can be repeated to show that Li's geometric mean estimator provides strong $L_p$ tracking for $p\in(0,2)$.
Namely by first union bounding over all $\O{\log n}$ times in the stream where the value of $F_p$ on the underlying frequency vector induced by the stream roughly doubles, we again reduce the problem to maintaining an accurate estimation of $F_p$ between two times in which the value of $F_p$ roughly doubles.
We can subsequently apply the techniques of lem:sketching:Fp:smallp by further breaking down the stream into times when the value of $F_p$ increases by a factor of $(1+\poly(\eps))$ and bounding the same terms $z_i$, as defined in fig:diff:est:smallp.
This analysis incurs an extra factor of $\log\log n$ due to an initial union bound over $\poly\left(\log n, \frac{1}{\eps}\right)$ times in the stream rather than $\poly\left(\frac{1}{\eps}\right)$.
Hence, the space required to implement Li's geometric mean estimator as a strong $L_p$ tracker in the random oracle model is $\O{\frac{\log n}{\eps^2}\left(\log\log n+\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$, which matches the strong $L_p$ tracker of [11].
To derandomize the algorithm, we incur an additional $(\log\log n)^2$ factor due to lem:derandom:many.

For $p\in(0,2)$, there exists a one-pass streaming algorithm that uses total space $\O{\frac{1}{\eps^2}\log n(\log\log n)^2\left(\log\log n+\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$ bits and provides $(\eps,\delta)$-strong tracking for the $F_p$ moment estimation problem.

Consider an instance of Li's geometric mean estimator with $d=\O{\frac{1}{\eps^2}\left(\log\frac{1}{\delta'}\right)}$ rows.
We define a sequence of times $t_1,t_2,\ldots,t_w$ throughout an oblivious stream $\calS$ so that each time $t_i$ is implicitly defined as the last time that $F_p(1:t_i)\le2^{i-1}$ and thus $w=\O{\log n}$.
For each $i\in[w]$, we further consider a sequence of times $t_{i,1},t_{i,2},\ldots$ so that time $t_{i,j}$ is defined as the last time $t$ such that that

\[\max(F_p(t_{i,j-1}+1:t),F_p(1:t)-F_p(1:t_{i,j-1}))\le\frac{1}{2^{q^2}}\eps^{16q/p^2}\cdot F_p(1:t_i).\]

Let $\mathcal{E}_1$ be the event that Li's geometric mean estimator gives a $\left(1+\frac{\eps}{2}\right)$-approximation to $F_p(1:t_i)$ for all $i\in[w]$ and let $\mathcal{E}_2$ be the event that Li's geometric mean estimator gives a $\left(1+\frac{\eps}{2}\right)$-approximation to $F_p(1:t_{i,j})$ for all $t_{i,j}$.
Since there are $\poly\left(\frac{1}{\eps},\log n\right)$ times $\{t_i\}\cup\{t_{i,j}\}$, then we require $\delta'=\delta/\poly\left(\frac{1}{\eps},\log n\right)$ to obtain success probability $1-\delta$ after taking a union bound over $\poly\left(\frac{1}{\eps},\log n\right)$ times.
By ligeoest:var, the arithmetic mean of $\O{\frac{1}{\eps^2}}$ variables $z_i$ achieves a $(1+\eps)$-approximation to $F_p(1:t)$ with constant probability for a fixed time $t$.
Thus by taking the median of $\O{\log\log n+\log\frac{1}{\eps}+\log\frac{1}{\delta}}$ such means and taking a union bound, we have that $\PPr{\mathcal{E}_1\wedge\mathcal{E}_2}\ge 1-\frac{\delta}{2}$.

For times $a,b\in[m]$, let $\calL(a:b)$ be the output of Li's geometric mean estimator for the frequency vector induced by the updates of $\calS$ from times $a$ to $b$.
From the chaining argument in lem:sketching:Fp:smallp and a sketching matrix with dimension $d=\O{\frac{1}{\eps^2}\left(\log\frac{1}{\delta'}\right)}$ rows, we have that for a fixed $i\in[w]$, there does not exist $t\in[t_{i,j}+1,t_{i,j+1}]$ such that $|\calL(1:t)-\calL(1:t_{i,j}+1)|\ge\frac{\eps}{2}F_p(1:t_{i,j})$, with probability at least $1-\delta'$.
Hence conditioned on $\mathcal{E}_1$ and $\mathcal{E}_2$, $\calL(1:t)$ outputs a $(1+\eps)$ approximation to $F_p(1:t)$ for all times $t\in[t_{i,j}+1,t_{i,j+1}]$, with probability at least $1-\delta'$.
We again take a union bound over $\poly\left(\frac{1}{\eps},\log n\right)$ times $\{t_i\}\cup\{t_{i,j}\}$, so that setting $\delta'=\delta/\poly\left(\frac{1}{\eps},\log n\right)$ implies that the $\calL(1:t)$ simultaneously gives a $(1+\eps)$-approximation to all $F_p(1:t)$ with probability $1-\delta$.
Hence, the total number of rows required in $D$ is $d=\O{\frac{1}{\eps^2}\left(\log\frac{1}{\delta'}\right)}$, which translates to $\O{\frac{1}{\eps^2}\left(\log\log n+\log\frac{1}{\eps}+\log\frac{1}{\delta}\right)}$ total rows.
Each entry in the sketch uses $\O{\log n}$ bits of space to store.
Moreover, we incur an additional $(\log\log n)^2$ factor due to lem:derandom:many to derandomize the algorithm.
Therefore, the total space in bits is

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

Applications to Entropy Estimation.
Finally, we give an application to adversarially robust entropy estimation, similar to thm:sw:entropy.

Given $\eps>0$, there exists an adversarially robust streaming algorithm that outputs an additive $\eps$-approximation to Shannon entropy and uses $\tO{\frac{1}{\eps^2}\log^3 n}$ bits of space and succeeds with probability at least $\frac{2}{3}$.

By obs:entropy:addmult and lem:entropy:reduction, it suffices to obtain adversarially robust $(1+\eps')$-approximation algorithms to $F_{y_i}(v)$ for all $y_i\in(0,2)$ in the set $\{y_0,\ldots,y_k\}$, where $k=\log\frac{1}{\eps}+\log\log m$ and $\eps'=\frac{\eps}{12(k+1)^3\log m}$.
By thm:robust:opt:Fp:smallp with accuracy parameter $\eps'$, we can obtain such robust algorithms approximating each $F_{y_i}(v)$, using space

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

Moreover, the failure probability of each algorithm is $1-\poly\left(\eps,\frac{1}{\log n}\right)$, due to the rescaling of the failure probability $\delta'=\frac{\delta}{\poly\left(\frac{1}{\eps},\log n\right)}$ in both lem:diff:est:Fp:smallp and thm:strong:Fp:smallp.
Hence for $\eps'=\frac{\eps}{12(k+1)^3\log m}$ and $\log m=\O{\log n}$, each of the $\O{k}$ algorithms use space $\tO{\frac{1}{\eps^2}\log^3 n}$.
Since $k=\log\frac{1}{\eps}+\log\log m$, the overall space complexity follows.

§ ROBUST FP ESTIMATION FOR INTEGER 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>2$ is an integer.
We again require both an $F_p$ strong tracker and an $F_p$ difference estimator to use thm:framework.
Recall that for integer $p>2$, the dominant space factor is $n^{1-2/p}$ and thus we will not try to optimize the $\log n$ factors.
Hence we obtain an $F_p$ strong tracker by adapting an $F_p$ streaming algorithm and a union bound over $m$ points in the stream.
The main challenge of the section is to develop the $F_p$ difference estimator, since we have the following $F_p$ strong tracker:

For integer $p>2$, there exists an insertion-only streaming algorithm $\ghss(1,t,\eps,\delta)$ that uses $\O{\frac{1}{\eps^2}n^{1-2/p}\log^2 n\log\frac{1}{\delta}}$ bits of space that gives a $(1+\eps)$-approximation to the $F_p$ moment.

By setting $\delta'=\frac{\delta}{\poly(n)}$, we can apply thm:Fp:largep across all $m=\poly(n)$ times on a stream, thus obtaining a strong tracker.

[40, 44]
For integer $p>2$, there exists an insertion-only streaming algorithm $\ghss(1,t,\eps,\delta)$ that uses $\O{\frac{1}{\eps^2}n^{1-2/p}\log\frac{n}{\delta}\log^2 n}$ bits of space and provides $(\eps,\delta)$-strong $F_p$ tracking.

To acquire intuition for our $F_p$ estimation algorithm, we first recall the following definition of perfect $L_p$ sampling.

Let $f\in\mathbb{R}^n$ and failure probability $\delta\in(0,1)$.
A perfect $L_p$ sampler is an algorithm that either outputs a failure symbol $\bot$ with probability at most $\delta$ or an index $i\in[n]$ such that for each $j\in[n]$,

\[\PPr{i=j}=\frac{u_j^p}{F_p(u)}+\O{n^{-c}},\]

for some arbitrarily large constant $c\ge 1$.

We use the expansion $F_p(v+u)-F_p(v)=\sum_{k=1}^{p}\binom{p}{k}\langle v^k,u^{p-k}\rangle$ for our difference estimator for $F_p$ moment estimation for integer $p>2$, where $u^k$ denotes the coordinate-wise $k$-th power of $u$.
Suppose we use a perfect $L_p$ sampler to sample a coordinate $a\in[n]$ with probability $\frac{v_a^k}{\|v\|_k^k}$.
We then set $Z$ to be the $a$-th coordinate of the frequency vector $v^{p-k}$.
Observe that $u$ arrives completely after the splitting time denotes the end of the updates to frequency vector $v$.
Thus we can sample $a$ at the splitting time and then explicitly compute $Z$.
We can then obtain an unbiased estimate $Y$ to $\|v\|_k^k$ with low variance, so that the expected value of $YZ$ would be exactly $\langle v^k,u^{p-k}\rangle$ and moreover, $YZ$ is a “good” approximation to $\langle v^k,u^{p-k}\rangle$.

The downfall of this approach is that it requires a perfect $L_p$-sampler for $p>2$, which is not known.
Perfect $L_p$-samplers are known for $p\le 2$ [56], but their constructions are based on duplicating each stream update $\poly(n)$ times.
Hence adapting these constructions to build perfect $L_p$-samplers for $p>2$ would be space-inefficient, since the space dependence is $\Omega(n^{1-2/p})$ for $p>2$, rather than $\polylog(n)$ for $p\le 2$.
Thus after duplication the space required would be $\Omega((\poly(n))^{1-2/p})$ rather than $\polylog(\poly(n))$.
Note that the former requires space larger than $n$ while the latter remains $\polylog(n)$.
One possible approach would be to use approximate $L_p$ samplers and their variants [71, 54, 4, 70], but these algorithms already have $\frac{1}{\eps^2}$ space dependency for each instance, which prohibits using $\Omega\left(\frac{1}{\eps}\right)$ instances to reduce the variance of each sampler.
Instead, we use the following perfect $L_2$-sampler of [56] to return a coordinate $a\in[n]$ with probability $\frac{v_a^2}{\|v\|_2^2} \pm \frac{1}{\poly(n)}$.

[56]
Given failure probability $\delta\in(0,1)$, there exists a one-pass streaming algorithm $\sampler$ that is a perfect $L_2$ sampler and uses $\O{\log^3 n\log\frac{1}{\delta}}$ bits of space.

We also obtain unbiased estimates $X$ and $Y$ of $v_a^{k-2}$ and $\|v\|_2^2$, respectively.
Given $a\in[n]$, we then track the $a$-th coordinate of $u^{p-k}$ exactly.
We show that the product of these terms $X$, $Y$, and $u^{p-k}$ forms an unbiased estimate to $\langle v^k,u^{p-k}\rangle$.
We then analyze the variance and show that taking the mean of enough repetitions gives a $(1+\eps)$-approximation to $\langle v^k,u^{p-k}\rangle$.
By repeating the estimator for each summand in $\sum_{k=1}^{p}\binom{p}{k}\langle v^k,u^{p-k}\rangle$, it follows that we obtain a $(\gamma,\eps,\delta)$-difference estimator for $F_p$.

We first require the well-known $\countsketch$ algorithm for identifying heavy-hitters, which consists of a table with $\log\frac{n}{\delta}$ rows, each consisting of $\O{\frac{1}{\eps^2}}$ buckets, to identify $\eps\cdot L_2$ heavy hitters.
For each row, each item $i\in[n]$ in the universe is hashed to one of the $\O{\frac{1}{\eps^2}}$ buckets along with a random sign.
The signed sum of all items assigned to each bucket across all rows is tracked by the data structure and the estimated frequency of each item $i$ is the median of the values associated with each bucket that $i$ is hashed to, across all rows.

* Find a list $\calH$ that includes all $i\in[n]$ with $v_i\ge\frac{\gamma^{1/p}}{16}\|v\|_p$.

* Using $\countsketch$, obtain an estimate $\widehat{v_i}$ to $v_i$ with additive error $\frac{\eps\gamma^{1/p}}{64\gamma}\|v\|_p$ for each $i\in\calH$ and let $h\in\mathbb{R}^n$ be the vector such that $h_i=\widehat{v_i}$ if $i\in\calH$ and zero otherwise.

* Perform perfect $L_2$ sampling on $v-h$ to obtain a set $\calS$ of size $k=\O{\frac{\gamma}{\eps^2}n^{1-2/p}}$.

* Obtain an estimate $\widehat{s_i}$ to $v_i-h_i$ for each $i\in\calS$.

* Let $W$ be a $(1+\eps)$-approximation to $\|v-h\|_2^2$.

* Output $W+\sum_{k=1}^{p-1}\binom{p}{k}\left(\sum_{i\in\calH}\widehat{v_i}^k,u_i^{p-k}+W\cdot\sum_{i\in\calS}\widehat{s_i}^{k-2},u_i^{p-k}\right)$.

$F_p$ difference estimator for $F_p(v+u)-F_p(v)$ with integer $p>2$.

For integer $p>2$ and failure probability $\delta\in(0,1)$, there exists a one-pass streaming algorithm that outputs an index $i\in[n]$ with probability $\frac{u_i^2}{F_2(u)}+\frac{1}{\poly(n)}$, as well as an unbiased estimate to $u_i^p$ with variance $u_i^{2p}$.
The algorithm uses $\O{\log^3 n\log\frac{1}{\delta}}$ bits of space.

Recall that $\sampler$ first duplicates each coordinate $u_i$ for $i\in[n]$ a total number of $n^c$ times and for each $(i,j)\in[n]\times[n^c]$, $\sampler$ scales $u_i$ to obtain random variables $z_{i,j}=\frac{u_i}{\sqrt{e_{i,j}}}$ for an exponential random variable $e_{i,j}$ (the exponential random variables in [56] are then derandomized).
This linear transformation to the frequency vector $u\in\mathbb{R}^n$ results in a vector $z\in\mathbb{R}^{n^{c+1}}$, which can also be interpreted as having dimensions $n\times n^c$.
Moreover, $\sampler$ only outputs an index $i\in[n]$ if there exists an index $j\in[n^c]$ if $|z_{i,j}|\ge\O{1}|z|_2$.
We then run an instance of $\countsketch$ with constant factor approximation to obtain an estimate $\widehat{z_{i,j}}$ for the frequency of $z_{i,j}$ and set $\widehat{u_i}=\sqrt{e_{i,j}}\cdot\widehat{z_{i,j}}$.
Recall that each estimate $\widehat{z_{i,j}}$ of $z_{i,j}$ is

\[\sum s_{i,j}\bfone_{h(a,b)=h(i,j)}s_{a,b}z_{a,b},\]

where $s_{a,b}$ is a uniformly random sign and $\bfone_{h(a,b)=h(i,j)}$ is the indicator variable of whether $h(a,b)=h(i,j)$.
That is, we define $\bfone_{h(a,b)=h(i,j)}=1$ if $h(a,b)=h(i,j)$ and $\bfone_{h(a,b)=h(i,j)}=0$ if $h(a,b)\neq h(i,j)$.
Hence, $\widehat{z_{i,j}}$ is an unbiased estimate of $z_{i,j}$ so that $\widehat{u_i}$ is an unbiased estimate of $u_i$.
Moreover, the variance of $\widehat{z_{i,j}}$ is at most $\O{\|z\|_2^2}=\O{z_{i,j}^2}$ so that the variance of $\widehat{u_i}$ is $\O{u_i^2}$.
Thus if we use $p$ independent instances of $\countsketch$ with estimates $\widehat{u_i}^{(1)},\ldots,\widehat{u_i}^{(p)}$, their product is an unbiased estimate to $u_i^p$ with variance $u_i^{2p}$, as desired.

Each of the $p$ instances of $\countsketch$ with constant factor approximation uses $\O{\log n\log\frac{n}{\delta}}$ bits of space.
Since the perfect $L_2$ $\sampler$ uses $\O{\log^3 n\log\frac{1}{\delta}}$ bits of space by thm:perfect:sampler, then the total space used is $\O{\log^3 n\log\frac{1}{\delta}}$.

Unfortunately, perfect $L_2$ sampling coordinates of $v$ alone is not enough; the variance of the resulting procedure is too high to obtain space dependency $\frac{\gamma}{\eps^2}$.
Thus we also run a subroutine that removes a set of “heavy” coordinates $\calH$ of $v$ and tracks the corresponding coordinates of $u$.
Although we have the exact values of $u_a$ for $a\in\calH$, we still do not have exact values of $v_a$; instead, we have estimates $\widehat{v_a}$ for each $v_a$ with $a\in\calH$.
Setting $h$ to be the sparse vector that contains the estimates $\widehat{v_a}$ for each $a\in\calH$ and $w:=v-h$, our algorithm perfect $L_2$ samples from $L_2$ sample from.
To show correctness, we decompose

\[F_p(v+u)-F_p(v)=\sum_{a\in\calH}\sum_{i=1}^{p}\binom{p}{i}v_a^iu_a^{p-i}+\sum_{a\notin\calH}\sum_{i=1}^{p}\binom{p}{i}v_a^iu_a^{p-i}.\]

The heavy-hitter subroutine allows accurate estimation to the first term and the perfect $L_2$ sampling subroutines allows accurate estimation to the second term.
Finally, we remark that perfect $L_2$ sampling incurs a term of $v_a^2$.
Thus we further need to split the estimation of the second term into the cases where $i=1$ and $i>1$.

Estimation of $\langle v^i,u^{p-i}\rangle$ for $i>1$.
We first show that our difference estimator gives an additive $\eps\cdot F_p(v)$ approximation to $\sum_{a\notin\calH}\binom{p}{i}v_a^iu_a^{p-i}$ with $i\ge 2$

For integer $p>2$, there exists an algorithm that uses space $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}$ and outputs an additive $\eps\cdot F_p(v)$ approximation to $\sum_{a\notin\calH}\binom{p}{i}v_a^iu_a^{p-i}$ with $i\ge 2$.

For an oblivious stream $\calS$, let $v$ be the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and $u$ be the frequency vector induced by updates from time $t_2$ to $t$ exclusive, with $F_p(u)\le\gamma\cdot F_p(v)$.
By thm:robust:opt:HH, there exists an algorithm $\heavyhitters$ that uses $\O{\frac{\gamma^{2-2/p}\log^2 n}{\eps^2}n^{1-2/p}}$ space and outputs a list $\calH$ of coordinates and estimates $\widehat{v_i}$ with additive error $\frac{\eps\gamma^{1/p}}{64\gamma}\|v\|_p$.
Moreover, $\calH$ includes all coordinates $i\in[n]$ such that $v_i\ge\frac{\gamma^{1/p}}{16}\|v\|_p$ and no coordinate $j$ such that $v_j\le\frac{\gamma^{1/p}}{32}\|v\|_p$.
Let $h$ be the vector consisting of the estimates $\widehat{v_i}$ for each $i\in[n]$ with $i\in\calH$ and $0$ in the positions $i$ for which $i\notin\calH$.
We define the vector $w:=v-h$.

We use $\sampler$ to sample indices $j_1,\ldots,j_k\in[n]$ with so that each sample is a coordinate $a\in[n]$ with probability $\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}$.
We obtain unbiased estimates to $\widehat{w_{j_1}^{p-i-2}},\ldots,\widehat{w_{j_k}^{p-i-2}}$ of $w_{j_1}^{p-i-2},\ldots,w_{j_k}^{p-i-2}$ through lem:coor:exp:var.
We also obtain a $(1+\O{\eps})$-approximation unbiased estimate $W$ of $\|w\|_2^2$.
Thus for each $b\in[k]$, the product $\widehat{w_{j_b}^{p-i-2}}\cdot W\cdot u_{j_b}^i$ satisfies

\begin{align*}
\Ex{\widehat{w_{j_b}^{p-i-2}}\cdot W\cdot u_{j_b}^i}&=\sum_{a\in\calH}\ip{\widehat{v_a}^{p-i}}{u_a^i}+\sum_{a\in\calH}\left(\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^{p-i-2}\cdot(1\pm\O{\eps})\|w\|_2^2\cdot u_a^i\\
&+\sum_{a\in[n]\setminus\calH}\left(\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^{p-i-2}\cdot(1\pm\O{\eps})\|w\|_2^2\cdot u_a^i.
\end{align*}

Observe that since $\widehat{v_a}$ is a $(1+\eps)$-approximation to $v_a$ for $a\in\calH$, then $|w_a|\le\eps|v_a|$, so that the second summation is at most $\O{\eps}\ip{v^{p-i}}{u^i}$.
Moreover, we have $w_a=v_a$ for $a\in[n]\setminus\calH$, so that

\begin{align*}
\Ex{\widehat{w_{j_b}^{p-i-2}}\cdot W\cdot u_{j_b}^i}&\in(1\pm\O{\eps})|\ip{w^{p-i}}{u^i}|+\frac{1}{\poly(n)}.
\end{align*}

Similarly, the variance is at most

\begin{align*}
\Var\left(\widehat{w_{j_b}^{p-i-2}}\cdot W\cdot u_{j_b}^i\right)&\le\sum_{a\in[n]}\left(\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^{2p-2i-4}\cdot(1\pm\O{\eps})\|w\|_2^4\cdot u_a^{2i}\\
&\le\sum_{a\in[n]}(1\pm\O{\eps})w_a^{2p-2i-2}\cdot\|w\|_2^2\cdot u_a^{2i}\\
&\le\sum_{a\in[n]}(1\pm\O{\eps})w_a^{2p-4}\cdot\|w\|_2^2\cdot u_a^{2}.
\end{align*}

By Hölder's inequality, the variance is at most

\begin{align*}
\end{align*}

Since $(1+\eps)\|w\|_2^2\le2\|v\|_2^2$ for $\eps\le 1$ and $\|u\|_p^p\le\gamma\|v\|_p^p$, then the variance is at most

\begin{align*}
\end{align*}

Recall that the vector $w$ is formed by removing from $v$ the coordinates $i\in[n]$ such that $v_i\ge\frac{\gamma^{1/p}}{16}\|v\|_p$.
Thus, $|w_i|\le\frac{\gamma^{1/p}}{16}\|v\|_p$ for all $i\in[n]$.
Subject to these constraints, we have that

\[\|w\|_{2p}^{2p}\le\frac{16^p}{\gamma}\cdot\frac{\gamma^2}{16^{2p}}\|v\|_p^{2p}.\]

Thus we have

\[\|w\|_{2p}^{2p-4}\le\frac{\gamma^{1-2/p}}{16^{p-2}}\|v\|_p^{2p-4}.\]

Hence, the variance is at most

\begin{align*}
\|v\|_2^2\cdot\gamma^{2/p}\|v\|_p^2\cdot\gamma^{1-2/p}\|v\|_p^{2p-4}\le\frac{\gamma}{n^{1-2/p}}\|v\|_p^2\cdot\|v\|_p^2\cdot\|v\|_p^{2p-4}.
\end{align*}

Thus by setting $k=\O{\frac{\gamma}{\eps^2}n^{1-2/p}}$, we obtain an additive $\frac{\eps}{p}\cdot F_p(v)$ approximation to $F_p(v+u)-F_p(v)$ with constant probability.
We can then boost this probability to $1-\frac{\delta}{\poly(n)}$ by repeating $\O{\log\frac{n}{\delta}}$ times.
Hence, we have a $(\gamma,\eps,\delta)$-difference estimator for $F_p$.

To analyze the total space complexity, first observe that we use $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log n}$ instances of $\sampler$, $\countsketch$, and an $F_2$ moment estimation algorithm.
For $\countsketch$, we only require constant factor approximation, so that each instance uses space $\O{\log^2 n}$.
Similarly for an $F_2$ moment estimation algorithm, we only require constant factor approximation, so that $\O{\log^2 n}$ space suffices, by thm:robust:opt:F2.
Each instance of $\sampler$ uses space $\O{\log^3 n}$.
Hence, the total space is $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}$.

Estimation of $\langle v,u^{p-1}\rangle$.
We first duplicate each coordinate of $u$ and $v$ a total number of $M=n^c$ times, for some sufficiently large constant $c>0$.
For each $i\in[n]$ and $j\in[M]$, we scale $u_i$ and $v_i$ by $1/e_{i,j}^{1/2}$, where $e_{i,j}$ is a random exponential variable truncated at $N^2$, where $N=nM$.
Thus we have that the cdf of $\frac{1}{e_{i,j}}$ satisfies $\PPr{\frac{1}{e_{i,j}}\ge x}\le\Theta\left(\frac{1}{x}\right)$ for $x>0$, so that $\Ex{\frac{1}{e_{i,j}}}=\int_0^{N^2}1-\left(1-\Theta\left(\frac{1}{x}\right)\right)\,dx=\O{\log n}$.
Let $U\in\mathbb{R}^N$ and $V\in\mathbb{R}^N$ be scaled and duplicated vector representations of $u$ and $v$, respectively.

* Use a set of exponential random variables to form a vector $V$ of duplicated and scaled coordinates of $v$.

* Hash the coordinates of $V$ into a $\countsketch$ data structure with $\O{\log n}$ buckets.

* Use the same exponential random variables to perform perfect $L_2$ sampling on $u$ to obtain a coordinate $(i,j)$ and an unbiased estimate $\widehat{u_{i,j}}$ to $u_{i,j}$.

* Let $\widehat{U}$ be an unbiased estimate of $\|u\|_2^2$ with second moment $\O{\|u\|_2^4}$.

* Query $\countsketch$ for an unbiased estimate $\widehat{v_{i,j}}$ to $v_{i,j}$ and set an estimator as $\widehat{U}\cdot\widehat{v_{i,j}}\left(\widehat{u_{i,j}}\right)^{p-3}$.

* Output the mean of $\O{\frac{\gamma}{\eps^2}\cdot n^{1-2/p}}$ such estimators.

$F_p$ difference estimator for $\langle v,u^{p-1}\rangle$ with integer $p>2$.

For integer $p>2$, there exists an algorithm that uses space $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}$ and outputs an additive $\eps\cdot F_p(v)$ approximation to $\langle v,u^{p-1}\rangle$.

For an oblivious stream $\calS$, let $v$ be the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and $u$ be the frequency vector induced by updates from time $t_2$ to $t$ exclusive, with $F_p(u)\le\gamma\cdot F_p(v)$.
We use $\sampler$ to sample indices $j_1,\ldots,j_k\in[n]$ with so that each sample is a coordinate $a\in[n]$ with probability $\frac{u_a^2}{\|u\|_2^2}+\frac{1}{\poly(n)}$.
For each $b\in[k]$, we also obtain an unbiased estimate $\widehat{v_{j_b}}$ of $v_{j_b}$ from the $\countsketch$ data structure.
We also obtain an unbiased estimate $\widehat{U}$ of $\|u\|_2^2$.
Observe that

\[\Ex{\widehat{U}\cdot\widehat{v_{j_b}}\cdot\widehat{u_{j_b}^{p-3}}}=\|u\|_2^2\sum_{a\in[n]}\left(\frac{u_a^2}{\|u\|_2^2}+\frac{1}{\poly(n)}\right)v_a\cdot u_a^{p-3}=\langle v,u^{p-1}\rangle.\]

To analyze the variance of $\widehat{U}\cdot\widehat{v_{j_b}}\left(\widehat{u_{j_b}}\right)^{p-3}$, we first observe that by the min-stability of exponential random variables, the maximum coordinate of the scaled vector $V$ is distributed as $\|V\|_2/E^{1/2}$ for an exponential random variable $E$.
If the coordinate $a\in[n]$ from the unscaled vector $v$ is sampled, this maximum coordinate is also $v_a/e_{a,j}^{1/2}$ for an exponential random variable $e_{a,j}$.
We have that $v_a/e_{a,j}^{1/2}\ge\|V_{-a,j}\|_2/E^{1/2}$, where $V_{-a}$ indicates the vector $V$ with the $a$-th entry set to zero.
Since $E=\O{\log n}$ with probability $1-\frac{1}{\poly(n)}$, then we have $e_{a,j}\le\frac{\O{\log n}\cdot v_a^2}{\|V\|_2^2}$.
Hence $e_{a,j}$ has expectation $\frac{\O{\log n}\cdot v_a^2}{\|V\|_2^2}$ so that by using $\O{\log n}$ buckets, $\countsketch$ outputs an estimate $\widehat{v_{j_b}}$ with variance $v_a^2$ if $a\in[n]$ is sampled in iteration $b$.

Thus, there exists a constant $C>0$ such that the variance of $\widehat{U}\cdot\widehat{v_{j_b}}\left(\widehat{u_{j_b}}\right)^{p-3}$ is at most

\begin{align*}
\Var\left(\widehat{U}\cdot\widehat{v_{j_b}}\cdot\widehat{u_{j_b}^{p-3}}\right)&\le\sum_{a\in[n]}\left(\frac{u_a^2}{\|u\|_2^2}+\frac{1}{\poly(n)}\right)\cdot C\|u\|_2^4\cdot v_a^2\cdot u_a^{2p-6}\\
&\le\sum_{a\in[n]} 2C\cdot u_a^{2p-4}v_a^2\cdot\|u\|_2^2.
\end{align*}

By Hölder's inequality, the variance is at most

\begin{align*}
\Var\left(\widehat{U}\cdot\widehat{v_{j_b}}\cdot\widehat{u_{j_b}^{p-3}}\right)&\le2C\cdot\|u\|_2^2\cdot\left(\sum_{a\in[n]}v_a^p\right)^{2/p}\left(\sum_{a\in[n]}u_a^{2p}\right)^{1-2/p}\\
&\le2C\cdot n^{1-2/p}\cdot\|u\|_p^2\cdot\|v\|_p^2\cdot\|u\|_{2p}^{2p-4}\\
&\le2C\cdot n^{1-2/p}\cdot\|u\|_p^{2p-2}\|v\|_p^2\\
&\le2C\cdot\gamma n^{1-2/p}\cdot n^{1-2/p}\|v\|_p^2,
\end{align*}

where the last inequality results from the fact that $F_p(u)\le\gamma F_p(v)$ and $p>2$.
Thus by setting $k=\O{\frac{\gamma}{\eps^2}n^{1-2/p}}$, we obtain an additive $\frac{\eps}{p}\cdot F_p(v)$ approximation to $\langle v,u^{p-1}\rangle$ with constant probability.
We can then boost this probability to $1-\frac{\delta}{\poly(n)}$ by repeating $\O{\log\frac{n}{\delta}}$ times.

Putting it all together.
We now give our $F_p$ difference estimator for integer $p>2$ using the above subroutines to approximate $F_p(v+u)-F_p(v)=\sum_{i=1}^{p}\binom{p}{i}\langle v^i,u^{p-i}\rangle$.

For integer $p>2$, there exists a $(\gamma,\eps,\delta)$-difference estimator for $F_p$ that uses space $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}$.

For an oblivious stream $\calS$, let $v$ be the frequency vector induced by the updates of $\calS$ from time $t_1$ to $t_2$ and $u$ be the frequency vector induced by updates from time $t_2$ to $t$ exclusive, with $F_p(u)\le\gamma\cdot F_p(v)$.
Observe that for integer $p$, we can expand

\[F_p(v+u)-F_p(v)=\sum_{i=1}^{p}\binom{p}{i}\langle v^i,u^{p-i}\rangle,\]

where we write $v^p$ as the coordinate-wise $p$-th power of $v$.
Let $\calH$ be the set of coordinates output by $\heavyhitters$.

\[F_p(v+u)-F_p(v)=\sum_{a\in\calH}\sum_{i=1}^{p}\binom{p}{i}v_a^iu_a^{p-i}+\sum_{a\notin\calH}\sum_{i=1}^{p}\binom{p}{i}v_a^iu_a^{p-i}.\]

By thm:robust:opt:HH, there exists an algorithm $\heavyhitters$ that uses $\O{\frac{\gamma^{2-2/p}\log^2 n}{\eps^2}n^{1-2/p}}$ space and outputs a list $\calH$ of coordinates and estimates $\widehat{v_a}$ with additive error $\frac{\eps\gamma^{1/p}}{64\gamma}\|v\|_p$.
Thus using the estimates $\widehat{v_a}$ along with the corresponding coordinates $u_a$ gives an additive $\O{\eps}F_p(v)$ approximation to $\sum_{a\in\calH}\sum_{i=1}^{p}\binom{p}{i}v_a^iu_a^{p-i}$ using $\tO{\frac{\gamma\log^2 n}{\eps^2}\,n^{1-2/p}}$ space, for $p>2$.
By lem:diff:est:largep:one and lem:diff:est:largep:generali, we similarly obtain an additive $\O{\eps}F_p(v)$ approximation to $\sum_{a\notin\calH}\sum_{i=1}^{p}\binom{p}{i}v_a^iu_a^{p-i}$ using $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta'}}$ space, where $\delta'=\frac{\delta}{p}$.
Thus by rescaling $\eps$, we obtain an additive $\eps\,F_p(v)$ approximation to $F_p(v+u)-F_p(v)$ using $\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}$ bits of space.

Using our difference estimator, we obtain a robust algorithm for $F_p$ moment estimation for integer $p>2$.

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

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

\[\O{\frac{\gamma}{\eps^2}n^{1-2/p}\log^3 n\log\frac{n}{\delta}}\]

and a strong tracker for $F_p$ that each uses space

\[\O{\frac{1}{\eps^2}n^{1-2/p}\log^2 n\log\frac{n}{\delta}}.\]

We use these subroutines in the framework of alg:framework.
Therefore, thm:framework with $S_1(n,\delta,\eps)=n^{1-2/p}\log^3 n\log\frac{n}{\delta}$, $C=1$, and $S_2=0$ proves that there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$ for $F_p$ that succeeds with constant probability and uses space $\O{\frac{1}{\eps^2}n^{1-2/p}\log^5 n\log^3\frac{1}{\eps}}$.

§ ROBUST F0 ESTIMATION

In this section, we use the framework of sec:framework to give an adversarially robust streaming algorithm for the distinct elements problem or equivalently, the $F_0$ moment estimation.
We again require an $F_0$ strong tracker and an $F_0$ difference estimator so that we can apply thm:framework.
Fortunately, we can again use similar sketches for both the $F_0$ strong stracker and the $F_0$ difference estimator, similar to the approach for $F_2$ moment estimation.
We can then optimize our algorithm beyond the guarantees of thm:framework so that our final space guarantees in thm:robust:opt:F0 match the bounds in thm:robust:opt:F2.
Note that this does not quite match the best known $F_0$ strong-tracking algorithm on insertion-only streams [18], which uses $\O{\frac{\log\log n}{\eps^2}+\log n}$ bits of space:

[18]
There exists an insertion-only streaming algorithm $\zeroestimate(1,t,\eps,\delta)$ that uses $\O{\frac{1}{\eps^2}\log\frac{1}{\delta}+\log n}$ bits of space and provides $(\eps,\delta)$-strong $F_0$ tracking.

thm:strong:F0 and other $F_0$ approximation algorithms use a balls-and-bins argument with increasing levels of sophistication [15, 61, 18].
We use a similar balls-and-bins argument, where each item is subsampled at a level $k$ with probability $\frac{1}{2^k}$, to obtain an $F_0$ difference estimator.
By counting the number of items in a level with $\Theta\left(\frac{\gamma}{\eps^2}\right)$ items that survive the subsampling process for the stream $u$, it follows that the expected number of the distinct items in $v$ but not $u$ is $\Theta\left(\frac{\gamma^2}{\eps^2}\right)$.
Thus we obtain a $\left(1+\frac{\eps}{\gamma}\right)$-approximation to $F_0(v)-F_0(u)$ from this procedure by first running the balls-and-bins experiment on $u$ and counting the number of bins that are occupied at some level $k$ with $\Theta\left(\frac{\gamma}{\eps^2}\right)$ survivors.
We then run the same balls-and-bins experiment on $v-u$ by only counting the additional bins that are occupied at level $k$, and rescaling this number by $2^k$.
Note that additional bins only correspond to items 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)$ and is exactly the requirement for the $F_0$ difference estimator, since $F_0(v)-F_0(u)\le\gamma F(u)$.

There exists a $(\gamma,\eps,\delta)$-difference estimator for $F_0$ that uses $\O{\frac{\gamma}{\eps^2}\left(\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta}\right)+\log n}$ bits of space.

Suppose we would like to estimate $F_0(v)-F_0(u)=\gamma\cdot F_0(u)$ for $\gamma=\Omega(\eps)$ and we subsample with probability $\frac{1}{2^k}$ so that $\frac{F_0(u)}{2^k}=\Theta\left(\frac{\gamma}{\eps^2}\right)$.
Then in expectation, the number of sampled items in $v$ that are not in $u$ is $\frac{F_0(v)-F_0(u)}{2^k}=\Theta\left(\frac{\gamma^2}{\eps^2}\right)$.
Hence if $X$ is the number of survivors from $F_0(v)-F_0(u)$ at level $k$, then $\Ex{2^k\cdot X}=F_0(v)-F_0(u)$ and the variance of $2^k\cdot X$ is at most

\[2^k\cdot(F_0(v)-F_0(u))\le\frac{\eps^2\cdot F_0(u)}{\gamma}\cdot(F_0(v)-F_0(u))\le\eps^2(F_0(u))^2.\]

Thus, the $2^k\cdot X$ gives an additive $\eps\cdot F_0$ approximation to $F_0(v)-F_0(u)$ with constant probability.
The probability can then be boosted to at least $1-\delta$ by taking the median of $\log\frac{1}{\delta}$ parallel instances.
Since the algorithm maintains $\frac{\gamma}{\eps^2}$ sampled items, the total space naïvely required is $\O{\frac{\gamma\log n}{\eps^2}\log\frac{1}{\delta}}$.
By hashing to $P=\poly\left(\frac{1}{\eps},\log n,\frac{1}{\delta}\right)$ buckets, the space bound can be further improved to $\O{\frac{\gamma}{\eps^2}\left(\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta}\right)+\log n}$, e.g., by first composing a hash function $h_1:[n]\to[P^3]$ and then a hash function $h_2:[P^3]\to[P]$, along the lines of [61, 18].
This suffices for a difference estimator at a single point in time; to obtain the strong tracking property, we note that both the estimator and $F_0(v)-F_0(u)$ are monotonic.
Hence, it suffices to take a union bound over $\log\frac{1}{\eps}$ times when the difference increases by a factor of $(1+\O{\eps})$.
Therefore, the total space required is $\O{\frac{\gamma}{\eps^2}\left(\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta}\right)+\log n}$.

Note that the difference estimator in lem:diff:est:F0 only requires pairwise independence and thus can be derandomized using a hash function that can be stored using $\O{\log n}$ bits of space.
We now use our difference estimator to get an adversarially robust streaming algorithm for the distinct elements problem.

Given $\eps>0$, there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation to $F_0$ that succeeds with probability at least $\frac{2}{3}$ and uses space

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

First note that $F_0$ is a monotonic function with $(\eps,m)$-twist number $\lambda=\O{\frac{1}{\eps}\log n}$ for $m=\poly(n)$, by obs:flip:fp.
By thm:strong:F0 and lem:diff:est:F0, there exist a $(\gamma,\eps,\delta)$-difference estimator that uses $\O{\frac{\gamma}{\eps^2}\left(\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta}\right)+\log n}$  bits of space and an oblivious strong tracker for $F_0$ that uses $\O{\frac{1}{\eps^2}\log\frac{1}{\delta}+\log n}$ bits of space, which can be used in the framework of alg:framework.
We thus apply thm:framework with $S_1(n,\delta,\eps)=\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta}$ , $C=1$, and $S_2(n,\delta,\eps)=\log n$.
Thus the total space is

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

Optimized $F_0$ Algorithm.
To improve the space requirements, we can again observe that it suffices to maintain sketches $\calA_a$ and $\calB_{a,c}$ for $\O{\log\frac{1}{\eps}}$ values of $a$ at a time, instead of maintaining all sketches $\calA_a$ and $\calB_{a,c}$ simultaneously.
By the same argument as before, it suffices to maintain only the most sketches $\calA_i$ and $\calB_{i,c}$ for only the smallest $\O{\log\frac{1}{\eps}}$ values of $i$ that are at least $a$ since the output increases by a factor of $2$ each time $a$ increases and thus any larger index will have only missed $\O{\eps}$ fraction of the $F_0$ of the stream.
Hence, any larger index still outputs a $(1+\eps)$-approximation once it becomes initialized.

Given $\eps>0$, there exists an adversarially robust streaming algorithm that outputs a $(1+\eps)$-approximation for $F_0$ that succeeds with probability at least $\frac{2}{3}$ and uses total space

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

At any point, there are $\O{\log\frac{1}{\eps}}$ active indices $a$ and $\O{1}$ active indices $c$ corresponding to sketches $\calA_{a}$ and $\calB_{a,c}$.
Because there are $\O{\log n}$ total indices $a$ over the stream, we set $\delta'=\frac{\delta}{\poly\left(\log n,\frac{1}{\eps}\right)}$.
Thus from thm:framework and thm:framework:F0 that for fixed $a$, the total space that sketches $\calA_{a}$ and $\calB_{a,c}$ use across the $\beta$ granularities is

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

since we have $S_1(n,\delta',\eps)=\left(\log\frac{1}{\eps}+\log\log n+\log\frac{1}{\delta'}\right)$, $C=1$, and $S_2(n,\delta',\eps)=\log n$.
However, there are only $\O{\log\frac{1}{\eps}}$ active indices $a$ simultaneously maintained by the optimized algorithm.
For each active index $a$, the sketches use $\O{\frac{1}{\eps^2}\log^3\frac{1}{\eps}\left(\log\log n+\log\frac{1}{\eps}\right)+\log n}$ bits of space.

As there are $\O{\log\frac{1}{\eps}}$ active indices of $a$, consisting of $\O{\frac{1}{\eps}}$ subroutines, then 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}$.
Therefore, the total space required is

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

§ FRAMEWORK FOR STREAMS WITH BOUNDED TWIST NUMBER

Recall that the previous framework of thm:framework in sec:framework was only suited for insertion-only streams.
In this section, we modify the framework of alg:framework to handle $F_p$ moment estimation on turnstile streams.

The main difference for turnstile streams is that the value of $F$ on the underlying frequency vector induced by the stream can decrease as well as increase.
Thus if we assign an algorithm $\calA_j$ to be revealed when the value of $F$ exceeds $2^j$, this may happen multiple times.
However, once $\calA_j$ is revealed for the first time, then the input to the algorithm is no longer independent to the randomness of the algorithm, due to the adversary.
Hence, we can no longer use $\calA_j$ to estimate the value of $F$ if it decreases and then exceeds $2^j$ again.

Nevertheless, note that each time the value of $F$ increases or decreases by a factor of roughly $(1+\eps)$, the value of the $(\eps,m)$-twist number $\lambda$ increases.
Therefore, $\lambda$ governs the number of times the value of $F$ can exceed $2^j$, going from $2^{j-1}$.
Similarly, $\lambda$ governs the number of times the value of $F$ can exceed $(1+\eps)^{Ci}2^j$, going from $(1+\eps)^{C(i-1)}2^j$ for any constant $C$.
Thus if $\lambda$ is given in advance, the algorithm can maintain the appropriate number of independent instances of the difference estimators $\calB$ and the streaming algorithms $\calA$ to handle each time the value of $F$ crosses a threshold.
We give the algorithm in full in alg:framework:flip.

Framework for Robust Algorithms on Turnstile 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)$, difference estimator $\calB$ for $F$, oblivious strong tracker $\calA$ for $F$, $\left(\frac{\eps}{32},m\right)$-twist number $\lambda$
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}}$, $\tau\gets 0$
$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
$t_{i,j}\gets\infty$ for $i\le\O{\eps\lambda}$, $j\in[\beta]$
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\min(t,t_{a,j})$ for $j\in[\beta]$.
Switch sketch at top layer
$a\gets a-1$, $b\gets\flr{\frac{8}{\eps}\cdot(X-Z_a)}$

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
$\tau\gets\tau+1$, $b\gets b+1$, $k\gets\lsb(b,1)$, $j\gets\flr{\frac{\tau}{2^k}}$
Freeze old sketch
$t_{a,j}\gets t$ for $j\in[k]$.
Update difference estimator times
$X<\left(1+\frac{(b-1)\eps}{8}\right)\cdot Z_a$
Switch sketch at lower layer
$\tau\gets\tau+1$, $b\gets b-1$, $k\gets\lsb(b,1)$, $j\gets\flr{\frac{\tau}{2^k}}$
Freeze old sketch
$t_{a,j}\gets t$ for $j\in[k]$.
Update difference estimator times
if there exist $j,k$ with unfrozen $\calB_{a,j}(1,t_{a,k},t,\gamma_k,\eta_k,\delta)>\frac{\gamma_j}{2} X$
$\tau\gets\tau+1$, $j\gets\flr{\frac{\tau}{2^k}}$
$Z_{a,k}\gets Z_{a,k}+\calB_{a,j}(1,t_{a,k},t,\gamma_k,\eta_k,\delta)$
Freeze old sketch
$t_{a,j}\gets t$ for $j\in[k]$.
$\left(1+\frac{b\eps}{8}\right)\cdot Z_a$
Output estimate for round $t$

Subroutine $\estimateF$, modified for alg:framework:flip
[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^{(j)}_{a,z_k},t,\gamma_{z_k},\eta_{z_k},\delta\right)$
Use unrevealed sketch for last component

The proof of correctness on non-adaptive streams follows similarly from the same argument as lem:frame:oblivious.
The main difference is that because the value of $F$ on the stream can both increase and decrease, we must be a little more careful in defining the times for which the difference estimators reveal their outputs.
In addition, to ensure the correctness of the difference estimator, we must facilitate the conditions required for the difference estimator.
Thus we restart a difference estimator each time the value of the suffix has become sufficiently large even if the difference itself has not become large.
This is a subtle issue for which we use the definition of twist number, rather than the simpler definition of flip number.

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

Let $t^{(y)}_i$ be the time in the stream at which the counter $a$ in alg:framework:flip is set to $i$ for the $y$-th time, for integers $i,y>0$.
For each integer $j\ge 0$, let $u_{i,j}$ be the last round for which $Z_{i,j}$ in alg:framework:flip is defined.
Let $t_{i,\ell}$ be the last round such that the counter $b$ in alg:framework:flip is first set to $\ell$.
Let $\mathcal{E}_1$ be the event that alg:framework:flip outputs a $\left(1+\frac{\eps}{32}\right)$-approximation to the value of $F$ at all times $t^{(y)}_i$, so that by lem:constant, $\mathcal{E}_1$ holds with probability at least $1-\O{\frac{\lambda\delta\log n}{\eps}}$, since there are at most $\lambda$ times $\{t^{(y)}_i\}$ by the definition of the twist number.
For the remainder of the proof, we fix the integers $i$ and $y$ and show correctness between $t^{(y)}_i$ and the first time $t>t^{(y)}_i$ such that either $t=t^{(y')}_{i+1}$ or $t=t^{(y')}_{i-1}$ for some $y'$.
Without loss of generality, suppose $t=t^{(y')}_{i+1}$.
We then show correctness at all times $t^{(\ell,r)}_{i}$ for each value $\ell$ obtained by the counter $b$ between times $t^{(y)}_i$ and $t^{(y')}_{i+1}$.
The remainder of the argument proceeds similarly to lem:frame:oblivious.

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 similar reasoning to 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:flip 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 for $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}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_k}F(1,t_i)$.
Now if the $(\gamma,\eps,\delta)$-difference estimator has space dependency $\frac{\gamma^C}{\eps^2}$ with $C=1$, then $\eta_{z_k}=\frac{\eta}{\beta}$.
Otherwise if $C>1$, then $\eta_{z_k}=\frac{\eta}{\varphi^{\beta-z_k}}$, with $\varphi>1$.
In both cases, we have that the total additive error is at most $\frac{\eps}{2}\cdot F(1,t_{i,\ell})$, since $\beta=\ceil{\log\frac{8}{\eps}}$.
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:flip 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:flip 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 $(\eta,m)$-twist number $\lambda$, where $\eta=\frac{\eps}{32}$.
Suppose there exists a $(\gamma,\eps,\delta)$-difference estimator with space dependency $\frac{\gamma^C}{\eps^2}$ for $C\ge 1$ and a strong tracker for $F$ on dynamic streams that use $\O{\frac{1}{\eps^2} S_F(n,\delta,\eps)}$ bits of space.
Then there exists an adversarially robust dynamic streaming algorithm that outputs a $(1+\eps)$ approximation for $F$ that succeeds with constant probability.
For $C>1$, the algorithm uses $\O{\frac{\lambda}{\eps}\cdot S_F(n,\delta',\eps)}$ bits of space, where $\delta'=\O{\frac{1}{\poly\left(\lambda,\frac{1}{\eps}\right)}}$.
For $C=1$, the algorithm uses $\O{\frac{\lambda}{\eps}\log^3\frac{1}{\eps}\cdot S_F(n,\delta',\eps)}$ bits of space.

Consider alg:framework:flip and note that lem:frame:oblivious:flip proves correctness over non-adaptive streams.
We now argue that lem:frame:oblivious:flip holds with over adversarial streams, using the same argument as thm:framework and the switch-a-sketch proof by [17].
Observe that each time either counter $a$ or $b$ either increases or decreases, the modified subroutine $\estimateF$ compels alg:framework:flip to use new subroutines $\calB_{i,j}$ and $\calA_i$ that have not previously been revealed to the adversary.
In particular, since $\estimateF$ sets $j=\flr{\frac{b+1}{2^{z_k}}}+\ceil{\frac{\tau}{2^k}}$, then since the $\eta$ twist number has only reached $\tau$, the value of $j$ ensures that $\calB_{i,j}$ has not been previously revealed.
Hence, the input is independent of the internal randomness of $\calB_{i,j}$ until the counter $b$ reaches $b=j$ for the $\ceil{\frac{\tau}{2^k}}$-th time, at which point $\calB_{i,j}$ is revealed once and not used again.

It remains to analyze the space complexity of alg:framework:flip.
We first analyze the space complexity for a $(\gamma,\eps,\delta)$-difference estimator with space dependency $\frac{\gamma^C}{\eps^2}$ and $C>1$.
Observe that $a=\O{\eps\lambda}$ and across the $\beta$ granularities, each value of $\eta_k$ is invoked at most $\O{\frac{\lambda}{2^k}}$ times.
Since we require correctness of $\O{\eps\lambda}$ instances of $\calB$, it suffices to set $\delta'=\O{\frac{1}{\poly\left(\lambda,\frac{1}{\eps}\right)}}$.
By assumption, a single instance of $\calB$ with granularity $\eta_k$ uses at most $\frac{C_1}{(\eta_k)^2} S_F(n,\delta',\eps)$ bits of space, for some constant $C_1>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 and the values of the counter $a$ is

\begin{align*}
\sum_{k=1}^\beta\frac{C_1\lambda\gamma_k^C}{\eta_k^2 2^k}\cdot S_F(n,\delta',\eps)&=\sum_{k=1}^\beta\frac{C_1\lambda\gamma_{\beta-k}^C}{\eta_{\beta-k}^2 2^{\beta-k}}\cdot S_F(n,\delta',\eps)\\
&\le\sum_{k=1}^\beta\frac{C_2\lambda(2^{\beta-k}\eps)^C\varphi^{2k}}{\eps^2\cdot2^{\beta-k}}\cdot S_F(n,\delta',\eps)\\
&\le\sum_{k=1}^\beta\frac{C_3\lambda 2^{-Ck}\varphi^{2k}}{\eps\cdot2^{-k}}\cdot S_F(n,\delta',\eps),
\end{align*}

for some absolute constants $C_1,C_2,C_3>0$.
Since $\varphi=2^{(C-1)/4}$ for $C>1$, then there exists a constant $C_4$ such that

\begin{align*}
\sum_{k=1}^\beta\frac{C_1\lambda\gamma_k^C}{\eta_k^2 2^k}\cdot S_F(n,\delta',\eps)&\le\sum_{k=1}^\beta\frac{C_4\lambda 2^{k-Ck}2^{(Ck-k)/2}}{\eps}\cdot S_F(n,\delta',\eps)\\
&\le\O{\frac{\lambda}{\eps}\cdot S_F(n,\delta',\eps)}.
\end{align*}

Moreover, since each strong tracker $\calA$ is used when the value of $F$ increases by a constant factor, then $\O{\eps\lambda}$ instances of $\calA$ are required.
Hence, the total space required for $C>1$ is $\O{\frac{\lambda}{\eps}\cdot S_F(n,\delta',\eps)}$.

For $C=1$, we recall that $\eta_k=\frac{\eta}{\beta}$, with $\beta\le\log\frac{8}{\eps}+1$.
Thus the total space is

\begin{align*}
\sum_{k=1}^\beta\frac{C_1\lambda\gamma_k^C}{\eta_k^2 2^k}\cdot S_F(n,\delta',\eps)&\le\sum_{k=1}^\beta\frac{C_5\lambda(2^{k-1}\eps)}{\eta^2\beta^{-2}\cdot 2^k}\cdot S_F(n,\delta',\eps)\\
&\le\sum_{k=1}^\beta\frac{C_6\lambda\beta^2\eps}{\eta^2}\cdot S_F(n,\delta',\eps)\\
&\le\O{\frac{\lambda}{\eps}\log^3\frac{1}{\eps}\cdot S_F(n,\delta',\eps)}.
\end{align*}

As a direct application of thm:framework:flip, we obtain the following:

Given $\eps>0$, there exists an adversarially robust streaming algorithm on turnstile streams with $(\eps,m)$ twist number $\lambda$ that outputs a $(1+\eps)$-approximation for $F_p$ with $p\in[0,2]$ that succeeds with probability at least $\frac{2}{3}$ and uses $\tO{\frac{\lambda}{\eps}\log^2 n}$ bits of space.

§ FRAMEWORK FOR SLIDING WINDOW ALGORITHMS

In this section, we describe a general framework for norm estimation in the sliding window model, using the sketch stitching and granularity changing technique.
We first require the following background on sliding windows algorithms.

Given adjacent substreams $A$, $B$, and $C$, a function $f$ is $(\alpha,\beta)$-smooth 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.
Smooth functions are integral to the smooth histogram framework for sliding window algorithms.

Smooth Histograms.
Braverman and Ostrovsky introduced the smooth histogram, an elegant framework that solves a large number of problems in the sliding window model, such as $L_p$ norm estimation, longest increasing subsequence, geometric mean estimation, or other weakly additive functions [23].
Thus the smooth histogram data structure maintains a number of timestamps throughout the data stream, along with a streaming algorithm for each timestamp that stores a sketch of all the elements seen from the timestamp.
The timestamps maintain the invariant that at most three checkpoints produce values that are within $(1-\beta)$ of each other, since any two of the sketches would always output values that are within $(1-\alpha)$ afterwards.
Hence if the function is polynomially bounded, then the smooth histogram data structure only needs a logarithmic number of timestamps.

We now define the following variant of a difference estimator.

Given a stream $\calS$ and fixed times $t_1$, $t_2$, and $t_3$, let frequency vectors $u$ and $v$ be induced by the updates of $\calS$ between times $[t_1,t_2)$ and $[t_2, t_3)$.
Given an accuracy parameter $\eps>0$ and a failure probability $\delta\in(0,1)$, a streaming algorithm $\calC(t_1,t_2,t,\gamma,\eps,\delta)$ is a $(\gamma,\eps,\delta)$-suffix difference estimator for a function $F$ if, with probability at least $1-\delta$, it outputs an additive $\eps\cdot F(v+w_t)$ approximation to $F(u+v+w_t)-F(v+w_t)$ for all frequency vectors $w_t$ induced by $[t_3,t)$ for times $t>t_3$, given $\min(F(u), F(u+v)-F(v))\le\gamma\cdot F(v)$ for a ratio parameter $\gamma\in(0,1]$.

Observe that the difference between def:diff:est:pre and def:diff:est:suf is that the fixed-prefix difference estimator approximates $F(v+w_t)-F(v)$ when the contribution to $F$ of the first frequency vector $v$ that arrives in the stream is much larger than that of $w_t$, while the suffix-pivoted difference estimator approximates $F(v+w_t)-F(w_t)$ when $F(w_t)$ is larger than $F(v)$.
Nevertheless, we prove that our fixed-prefix difference estimators for $F_p$ moment estimation with $p\in(0,2]$ can also be adjusted to form suffix-pivoted difference estimators.
Unless otherwise noted, the difference estimators in this section refer to the suffix-pivoted difference estimators rather than the fixed-prefix difference estimators.

We adapt our sketch stitching and granularity changing technique to the sliding window model by focusing on the suffix of the stream, since prefixes of the stream may expire.
We thus run the highest accuracy algorithms, the separate streaming algorithms $\calA$, on various suffixes of the stream similar to the smooth histogram framework.
It follows from smoothness that 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$ on the sliding window.
Our task is then to remove the extraneous contribution of the updates between times $t_0$ and $m-W+1$, i.e., the starting time of the sliding window.

We partition the substream of these updates into separate blocks based on their contribution to the value of $F$ by guessing $\O{\log n}$ values for the final value of $F$ on the sliding window and forming new difference estimators at level $j$ when the value of $F$ on each block has exceeded a $\frac{1}{2^j}$ fraction of the corresponding guess.
We terminate a guess when there are more than $100\cdot 2^j$ blocks in that level, indicating that the guess is too low.

We can maintain separate sketches for these blocks, with varying granularities, and stitch these sketches together at the end.
We give our algorithm in full in alg:sliding.

Interpretation of alg:sliding.
We now translate between the previous intuition and the pseudocode of alg:sliding.
At each time, alg:sliding only runs two subroutines: $\guessupdatesw$ and $\mergesw$.
The first subroutine $\guessupdatesw$ creates new instances of each algorithm (both a streaming algorithm approximating $F$ on a suffix of the stream and a difference estimator starting at each time) at each time in the stream.
Moreover, $\guessupdatesw$ partitions the stream into blocks for the difference estimator by using exponentially increasing guesses for the value of $F$ at the end of the stream to assist with appropriate granularity for each block.
The second subroutine $\mergesw$ performs maintenance on the data structure to ensure that there are not too many instances that have been created by the first subroutine that are simultaneously running.
Namely, $\mergesw$ deletes algorithms running on suffixes of the stream that output a similar value, so that the number of remaining algorithms is logarithmic rather than linear.
Similarly, $\mergesw$ merges two difference estimators when it is clear their combined contribution is still too small.
Finally at the end of the stream, $\stitchsw$ creates an estimate for the value of $F$ on the stream by stitching together the estimates output by each difference estimator.
Although alg:framework is notationally heavy, each timestamp $t^{(k)}_{i,j,\ell}$ should be associated with (1) a guess $k\in[C\log n]$ for the value of $F$ at the end of the stream, (2) an index $i\in\O{\log n}$ roughly associated with the number of times $F$ has actually doubled in the stream so far, (3) a granularity $j$, and (4) the number of the block $\ell$ in granularity $j$.

Moment Estimation in the Sliding Window Model
[1]
Stream $u_1,\ldots,u_m$ of updates, an $(\eps,\eps^q)$-smooth function $F$, accuracy parameter $\eps\in(0,1)$, window parameter $W>0$
Robust $(1+\eps)$-approximation to $F$
$\delta\gets\frac{1}{\poly(m)}$, $\eta\gets\frac{\eps}{2^{20}q\log\frac{1}{\eps}}$, $\varphi\gets\sqrt{2}$ be a parameter
$\beta\gets\ceil{\log\frac{100\cdot 4^q}{\eps^q}}$, $\gamma_j\gets 2^{3-j}$ for all $j\in[\beta]$
each update $u_t\in[n]$, $t\in[m]$
Create new subroutines for each update
Removes extraneous subroutines
Estimate $F$ on sliding window

Subroutine $\guessupdatesw$ of alg:sliding: create new subroutines for each update
[1]
Let $s$ be the number of instances of $\calA$.
$t_{s+1}\gets t$
Start a new instance $\calA(t_{s+1},t,\eta,\delta)$.
Maintain instances of each granularity
$k\in[C\log n]$
$n^C$ is upper bound on value of $F$
Let $r_k$ be the number of instances of timestamps $t^{(k)}_{s+1,j,*}$.
$\calA(t^{(k)}_{s+1,j,r_k},t-1,1,\delta)\in[n^C/2^{j+k+11},n^C/2^{j+k+10}]$, $\calA(t^{(k)}_{s+1,j,r_k},t,1,\delta)>n^C/2^{j+k+10}$, and $r<100\cdot 2^{j+10}$
$t^{(\ell)}_{s+1,j,r_{\ell+1}}\gets t$ .
Demarcate $\sdiffest(t^{(\ell)}_{s+1,j,r_\ell},t^{(\ell)}_{s+1,j,r_{\ell+1}},t,\gamma_j,\eta,\delta)$.
Update splitting time
Start a new instance $\calA(t^{(\ell)}_{s+1,j,r_{\ell+1}},t,1,\delta)$.

Subroutine $\mergesw$ of alg:sliding: removes extraneous subroutines
[1]
Let $s$ be the number of instances of $\calA$.
$i\in[s]$, $j\in[\beta]$, and $k\in[C\log n]$
Difference estimator maintenance
Let $r_k$ be the number of instances of timestamps $t^{(k)}_{s+1,j,*}$.
Merges two algorithms with “small” contributions
$\calA(t^{(k)}_{i,j,\ell-1},t^{(k)}_{i,j,\ell+1},1,\delta)\le n^C/2^{k+j+10}$
Merge (add) the sketches for $\calA(t_{i,j,k-1},t_{i,j,k},1,\delta)$ and $\calA(t_{i,j,k},t_{i,j,k+1},1,\delta)$.
Merge (add) the sketches for $\sdiffest(t_{i,j,k-1},t_{i,j,k},t,\gamma_j,\eta,\delta)$ and $\sdiffest(t_{i,j,k},t_{i,j,k+1},t,\gamma_j,\eta,\delta)$.
Relabel the times $t_{i,j,*}$.
Smooth histogram maintenance
$j\in[\beta]$ and $k\in[C\log n]$
Append the times $t^{(k)}_{i+1,j,*}$ to $\{t^{(k)}_{i,j,*}\}$.
Delete $t_{i+1}$ and all times $t_{i+1,*,*}$.
Relabel the times $\{t_i\}$ and $\{t^{(k)}_{i,j,*}\}$.

Subroutine $\stitchsw$ of alg:sliding: output estimate of $F_p$ on the sliding window
[1]
Let $i$ be the largest index such that $t_i\le m-W+1$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
$c_0\gets t_i$
Stitch sketches
Let $a$ be the smallest index such that $t^{(k)}_{i,j,a}\ge c_{j-1}$
Let $b$ be the largest index such that $t^{(k)}_{i,j,b}\le m-W+1$
$c_j\gets t^{(k)}_{i,j,b}$
$Z:=X-\sum_{j=1}^\beta Y_j$

Recall that we abuse notation so that $W$ represents the active updates in the stream.
Thus we use $F_p(W)$ to denote the $F_p$ moment of the active elements in the sliding window, i.e., if $m<W$, then $F_p(W)=F_p(1:m)$ and if $m\ge W$, then $F_p(W)=F_p(1:m-W+1)$.
We first show that the timestamps $t_1,\ldots,t_s$ mark suffixes of the stream in which the moment roughly double, so that $F_p(t_1,m)\ge\ldots\ge F_p(t_s,m)$ and $2^{s-i}\cdot F_p(t_s,m)\ge F_p(t_i,m)$ for each $i\in[s]$.
Since $W$ is oblivious to the algorithim until the $\stitchsw$ subroutine, it suffices to show that if $t_i\le m-W+1\le t_{i+1}$, then $F_p(W)\le F_p(t_i,m)\le 2F_p(W)$ and $\frac{1}{2}F_p(W)\le F_p(t_{i+1},m)\le F_p(W)$.

We first show that the top level gives a constant factor approximation to $F(W)$.
The intuition behind the lemma is that the maintenance procedure $\mergesw$ only deletes an instance of an algorithm if the instance is sandwiched between two other algorithms whose values are within a factor of $(1-1/8^q)$, where the function is $(\eps,\eps^q)$-smooth.
Thus by the definition of smoothness, we should expect the other two algorithms to always produce values that are within a factor of two, regardless of the subsequent updates of the stream.
This is important because it allows us to translate between the values of various suffixes of the stream, e.g., $F(t_i,m)\le 2F(W)$ implies that additive $\frac{\eps}{2}\cdot F(t_i,m)$ error gives a $(1+\eps)$-multiplicative error to $F(W)$.

Let $i$ be the largest index such that $t_i\le m-W+1$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
Let $\calE$ be the event that all subroutines $\calA$ in alg:sliding succeed.
Then conditioned on $\calE$, $F(W)\le F(t_i,m)\le 2F(W)$ and $\frac{1}{2}F(W)\le F(t_{i+1},m)\le F(W)$.

Observe that in the $\mergesw$ subroutine, we only delete a timestamp $t_{i'}$ if $\calA(t_{i'+2},t,\eta,\delta)\ge(1-1/8^q)\calA(t_{i'},t,\eta,\delta)$ at some point $t$.
Since $\eta=\frac{\eps}{2^{20}q\log\frac{1}{\eps}}\le\frac{1}{1024}$, we have that conditioned on $\calE$, $F(t_{i'+2},t)\left(1+\frac{1}{1024}\right)\ge(1-1/8^q)\left(1-\frac{1}{1024}\right)F(t_{i'},t)$.
Thus, $F(t_{i'+2},t)\ge(1-1/4^q)F(t_{i'},t)$.

We have either $t_i=m-W+1$ and $t_{i+1}=m-W+2$ in which case the statement is trivially true or timestamps $t_i$ and $t_{i+1}$ at some point $t\le m$ must have satisfied $F(t_{i+1},t)\ge(1-1/4^q)F(t_i,t)$ so that $t_i+1$ was removed from the set of timestamps.
Thus, $F(t_{i+1},t)\ge(1-1/4^q)F(t_i,t)$ and recall that we assume $F$ is $(\eps,\eps^q)$-smooth.
By the definition of smoothness, $F(t_{i+1},t)\ge(1-1/4^q)F(t_i,t)$ implies $F(t_{i+1},m)\ge\frac{1}{2}\cdot F(t_i,m)$ for all $m\ge t$.
Since $t_i\le m-W+1$, then $F(t_i,m)\ge F(m-W+1,m)=F(W)\ge F(t_{i+1},m)$ and the conclusion follows.

We now show that our difference estimators are well-defined and thus give good approximations to the differences that they estimate.
Although this sounds trivial, we remark that a pre-condition to a $(\gamma,\eps,\delta)$-difference estimator to succeed on the approximation of a difference $F(v+u_1)-F(u_1)$, we must have $F(v+u_1)-F(u_1)\le\gamma\cdot F(v+u_1)$, which requires proving properties about the specific partition of the stream.
On the other hand, since $\guessupdatesw$ partitions the stream into blocks for each difference estimator based on their contribution, we show that the pre-condition holds by construction.

Let $i$ be the largest index such that $t_i\le m-W+1$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
Let $\calE$ be the event that all subroutines $\calA$ and $\sdiffest$ in alg:sliding succeed.
Then conditioned on $\calE$, we have that for each $j\in[\beta]$ and all $\ell$, $\sdiffest(t^{(k)}_{i,j,\ell-1},t_{i,j,\ell},t,\gamma_j,\eta,\delta)$ gives an additive $\eta\cdot F(t^{(k)}_{i,j,\ell}:t)$ approximation to $F(t^{(k)}_{i,j,\ell-1}:t)-F(t^{(k)}_{i,j,\ell}:t)$.

Recall that for a suffix-pivoted difference estimator to be well-defined, we require $F(t^{(k)}_{i,j,\ell-1}:t^{(k)}_{i,j,\ell})\le\gamma_j\cdot F(t^{(k)}_{i,j,\ell}:x)$

at some time $x$.
Since $\gamma_j=2^{3-j}$ and $\guessupdatesw$ creates a new partition at level $j$ when $\calA(t^{(k)}_{s+1,j,r_k},t-1,1,\delta)\le n^C/2^{j+k+10}$, then it follows that $F(t^{(k)}_{i,j,\ell-1}:t^{(k)}_{i,j,\ell})\le\gamma_j\cdot F(t^{(k)}_{i,j,\ell}:x)$.
Thus the conditions for a suffix-pivoted difference estimator hold, so $\sdiffest(t^{(k)}_{i,j,\ell-1},t^{(k)}_{i,j,\ell},m,\gamma_j,\eta,\delta)$ gives an additive $\eta\cdot F(t^{(k)}_{i,j,\ell}:t)$ approximation to $F(t^{(k)}_{i,j,\ell-1}:m)-F(t^{(k)}_{i,j,\ell}:m)$ by the guarantees of the difference estimator.

We now lower bound the values of each difference.
This is important for bounding the number of difference estimators that are used to stitch together the estimate at the end of the stream.
For example, without a lower bound on the difference estimators at each level, it could be possible that we use a linear number of difference estimators to form our estimate of $F(W)$, in which case the space would be too large.
Using the following lower bound on the difference estimator, we ultimately show only a logarithmic number of difference estimators is used to form our estimate of $F(W)$.
The intuition behind the proof of lem:sliding:delta:lower is that if the contributions of the difference estimators of two consecutive blocks are both small, then $\mergesw$ will end up merging the blocks.
Hence, we should expect the contribution of any two consecutive blocks to be sufficiently large.

Let $i$ be the largest index such that $t_i\le m-W+1$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
Let $\calE$ be the event that all subroutines $\calA$ and $\sdiffest$ in alg:sliding succeed.
For any $\ell\in[r_k-2]$, let $u$ denote the frequency vector between times $t^{(k)}_{i,j,\ell}$ and $t^{(k)}_{i,j,\ell+2}$ and let $w$ denote the frequency vector between times $t^{(k)}_{i,j,\ell+2}$ and $t$.
Finally, let $w$ denote the frequency vector between times $t_i$ and $t$.
Then conditioned on $\calE$, we have that

\[F(u+v)-F(v)\ge 2^{-j-8}\cdot F(w).\]

Let $u_1$ denote the frequency vector between times $t^{(k)}_{i,j,\ell}$ and $t^{(k)}_{i,j,\ell+1}$ and $u_2$ denote the frequency vector between times $t^{(k)}_{i,j,\ell+1}$ and $t^{(k)}_{i,j,\ell+2}$.
Recall that $\mergesw$ merges two instances of $\sdiffest$ when

\begin{align*}
\sdiffest(t^{(k)}_{i,j,\ell-1},t^{(k)}_{i,j,\ell},t,\gamma_j,\eta,\delta)+\sdiffest(t^{(k)}_{i,j,\ell},t^{(k)}_{i,j,\ell+1},t,\gamma_j,\eta,\delta)\le 2^{-j-10}\cdot\calA_{i}(t_{i},t,\eta,\delta).
\end{align*}

Since we do not remove $t^{(k)}_{i,j,\ell+1}$ from the list of timestamps, then we have

\[\sdiffest(t^{(k)}_{i,j,\ell-1},t^{(k)}_{i,j,\ell},t,\gamma_j,\eta,\delta)+\sdiffest(t^{(k)}_{i,j,\ell},t^{(k)}_{i,j,\ell+1},t,\gamma_j,\eta,\delta)>2^{-j-10}\cdot\calA_{i}(t_{i},t,\eta,\delta).\]

Since the difference estimators are well-defined by lem:diff:est:well:defined, then $\sdiffest(t^{(k)}_{i,j,\ell},t^{(k)}_{i,j,\ell+1},t,\gamma_j,\eta,\delta)$ is at most a $2$-approximation to $F(u_1+u_2+v)-F(u_2+v)$ and we similarly obtain a $2$-approximation to $F(u_2+v)-F(v)$.

\[F(u)-F(v)=F(u_1+u_2+v)-F(v)\ge 2^{-j-8}\cdot F(w).\]

We next bound the number of level $j$ difference estimators that can occur from the end of the previous level $j-1$ difference estimator to the time when the sliding window begins.
We say a difference estimator $\sdiffest$ is active if $\ell\in[a_j,b_j]$ for the indices $a_j$ and $b_j$ defined in alg:sliding.
The active difference estimators in each level will be the algorithms whose output are subtracted from the initial rough estimate to form the final estimate of $F_2(W)$.
The intuition behind the proof of lem:sliding:active:indices is that lem:sliding:delta:lower lower bounds the contributions of the difference estimators of two consecutive blocks.
Hence there cannot be too many active difference estimators in a level or else their contributions will be too large for the level.

Let $i$ be the largest index such that $t_i\le m-W+1$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
Let $\calE$ be the event that all subroutines $\calA$ and $\sdiffest$ in alg:sliding succeed.
For each $j\in[\beta]$, let $a_j$ be the smallest index such that $t_{i,j,a_j}\ge c_{j-1}$ and let $b_j$ be the largest index such that $t_{i,j,b_j}\le m-W+1$.
Then conditioned on $\calE$, we have $b_j-a_j\le 512$.

Conditioned on $\calE$, we have that for each $j\in[\beta]$ and all $\ell$,

\[2^{-j-8}\cdot F(W)<F(t^{(k)}_{i,j,\ell},t)-F(t^{(k)}_{i,j,\ell+2},t),\]

by lem:sliding:delta:lower.
By lem:sw:top:constant, $F_p(t_i,m)\le 2F_p(W)$.
Thus by a telescoping argument, we have that for $j=1$, $a_j-b_j<512$.

For $j>1$, suppose by way of contradiction that $b_j-a_j\ge 512$.
Let $k=b_j-a_j$ and for $x\in[k]$, let $u_x$ be the frequency vector induced by the updates of the stream from time $a_j+{x-1}$ to $a_j+x$.
Let $u$ be the frequency vector induced by the updates of the stream from time $t_{i,j,k}$ to $m$ and $v$ be the frequency vector induced by the updates from $t_i$ to $m$.
By lem:sliding:delta:lower,

\[F\left(u+\sum_{\ell=1}^k u_{\ell}\right)-F(u)\ge8\cdot2^{-j-8}\cdot F(v),\]

since there are at least $8$ disjoint pairs of tuples $(i,j,\ell)$ and $(i,j,\ell+1)$ if $k>512$.

Thus if $b_j-a_j>512$, then the sum of the outputs of the active difference estimators at level $j$ is more than $8\cdot2^{-j-8}\cdot F(v)$.
In particular since $t^{(k)}_{i,j,a_j}\ge c_{j-1}$, the sum of the outputs of the active difference estimators at level $j$ after $c_{j-1}$ is at least $8\cdot2^{-j-8}\cdot F(v)$.
However, by lem:sliding:delta:lower, each difference estimator at level $j-1$ has output at least $2^{-j-7}\cdot F(u)>8\cdot 2^{-j-8}\cdot F(v)$.
Specifically, the difference estimator from times $t^{(k)}_{i,j,c_{j-1}}$ to $t^{(k)}_{i,j,c_{j}}$ must have output at least $2^{-j-7}\cdot F(u)>8\cdot 2^{-j-8}\cdot F(v)$.
Therefore, there exists some other $z>c_{j-1}$ such that $t^{(k)}_{i,j-1,z}\le m-W+1$, which contradicts the maximality of $c_{j-1}$ at level $j-1$.

We next upper bound the value of each difference estimator.
This is important for upper bounding the error associated with the sliding window possibly not beginning exactly where a difference estimator begins.
For example, if a difference estimator exactly computes $F(1:10)-F(4:10)$ but the sliding window consists of the last eight updates, i.e., $F(3:10)$, then the error of our estimator is still only lower bounded by the difference.
Thus it is crucial to not only upper bound the error of the difference estimator, but also the value of the difference estimator.
The intuition behind the proof of lem:sliding:delta:upper is that the subroutine $\mergesw$ only creates a new block for each difference estimator when the contribution is in a particular range.
Specifically, the contribution cannot be too large or else a new block would have already been formed.
Then by smoothness of the function, the contribution of difference estimator cannot grow to be too large regardless of the subsequent updates in the stream.

Let $i$ be the largest index such that $t_i\le m-W+1$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
Let $\calE$ be the event that all subroutines $\calA$ and $\sdiffest$ in alg:sliding succeed.
Then conditioned on $\calE$, we have that for each $j\in[\beta]$ and each $\ell$ that either $t^{(k)}_{i,j,\ell+1}=t^{(k)}_{i,j,\ell}+1$ or $F(t^{(k)}_{i,j,\ell},t)-F(t^{(k)}_{i,j,\ell+1},t)\le 2^{-j/q-7/q}\cdot F(t^{(k)}_{i,j,\ell+1},t)$.

Suppose $t^{(k)}_{i,j,\ell+1}\neq t^{(k)}_{i,j,\ell}+1$.
Then at some time $x$, the timestamp $t^{(k)}_{i,j,\ell}+1$ must have been merged by subroutine $\mergesw$.

\[\sdiffest(t^{(k)}_{i,j,\ell},t^{(k)}_{i,j,\ell'},x,\gamma_j,\eta,\delta)+\sdiffest(t^{(k)}_{i,j,\ell'},t^{(k)}_{i,j,\ell+1},x,\gamma_j,\eta,\delta)\le 2^{-j-10}\cdot\calA_{i}(t_{i},x,\eta,\delta).\]

Let $u_1$ be frequency vector representing the updates from time $t^{(k)}_{i,j,\ell}$ to $t^{(k)}_{i,j,\ell'}-1$, $u_2$ represent times $t^{(k)}_{i,j,\ell'}$ to $t^{(k)}_{i,j,\ell+1}$, and $u$ represent times $t^{(k)}_{i,j,\ell}$ to $t^{(k)}_{i,j,\ell+1}$, so that $u_1+u_2=u$.
Let $x_1$ represent the updates between time $t^{(k)}_{i,j,\ell+1}$ and $x$ and let $x_2$ represent the updates between time $x+1$ and $t$.
Since the difference estimators are well-defined by lem:diff:est:well:defined, we have that $\sdiffest(t^{(k)}_{i,j,\ell},t^{(k)}_{i,j,\ell'},x,\gamma_j,\eta,\delta)$ is at most a $2$-approximation to $F(u_1+u_2+x_1)-F(u_2+x_1)$ and we similarly obtain a $2$-approximation to $F(u_2+x_1)-F(x_1)$.

\[F(u+x_1)-F(x_1)=F(u_1+u_2+x_1)-F(x_1)\le 2^{-j-7}\cdot F(x_1).\]

By the $(\eps,\eps^q)$ smoothness of $F$, we thus have that for any vector $x_2$,

\[F(u+v)-F(v)=F(u+x_1+x_2)-F(x_1+x_2)\le 2^{-j/q-7/q}\cdot F(x_1+x_2)=2^{-j/q-7/q}\cdot F_p(v).\]

Finally, we show the correctness of alg:sliding.
The main intuition behind lem:sw:frame:correct is that there are two sources of error.
The first source of error originates from the boundaries of the blocks corresponding to the difference estimator not aligning with the beginning of the sliding window.
This error, resulting from no difference estimator being assigned to compute the exactly correct value, corresponds to the elements marked by blue in fig:sliding and cannot be accounted for even if all difference estimators have zero error.
On the other hand, this error is upper bounded by the contribution of a difference estimator at the bottom level, which is bounded by lem:sliding:delta:upper.
The second source of error stems from the approximation error caused by each of the difference estimators.
Since lem:sliding:active:indices bounds the total number of difference estimators being used in our output, we can also upper bound the total approximation error due to the difference estimators.

With high probability, alg:sliding gives a $(1+\eps)$-approximation to the value of $F(W)$.

Let $\calE$ be the event that all algorithms throughout the stream succeed and note that $\PPr{\calE}\ge1-\frac{1}{\poly(n)}$ since $\delta=\frac{1}{\poly(m)}$.
Thus we condition on $\calE$ throughout the remainder of the proof.

Let $f$ be the frequency vector induced by the window and let $i$ be the largest index such that $t_i\le m-W+1$ and let $c_0=t_i$.
Let $u$ be the frequency vector induced by the updates of the stream from time $t_i$ to $m$.
Let $k$ be the smallest integer such that $n^C/2^k\le\calA(t_i,m,1,\delta)$.
For each $j\in[\beta]$, let $a_j$ be the smallest index such that $t^{(k)}_{i,j,a_j}\ge c_{i-1}$ and let $b_j$ be the largest index such that $t^{(k)}_{i,j,b_j}\le m-W+1$.
Note that by construction of the $\guessupdatesw$ forming a new timestamp for all levels $\ell>k$ each time a new timestamp at level $k$ is formed, then it follows that $t_{i,j,a_j}=c_{i-1}$.
Let $u_j$ be the frequency vector induced by the updates of the stream from time $a_j$ to $b_j$.
Let $v$ be the frequency vector induced by the updates of the stream from $c_\beta$ to $m-W+1$.
Thus, we have $u=\sum_{j=1}^\beta u_j+v+f$, so it remains to show that:

* $F(v+f)-F(f)\le\frac{\eps}{2}\cdot F(f)$

* We have an additive $\frac{\eps}{2}\cdot F(f)$ approximation to $F(v+f)$.

Combined, these two statements show that we have a multiplicative $(1+\eps)$-approximation of $F_p(f)$.

To show that $F(v+f)-F(f)\le\frac{\eps}{2}\cdot F(f)$, let $\ell$ be the index such that $t^{(k)}_{i,\beta,\ell}=c_\beta$, so that $t^{(k)}_{i,\beta,\ell}\le m-W+1\le t^{(k)}_{i,\beta,\ell+1}$.
Note that if $t^{(k)}_{i,\beta,\ell}=m-W+1$ then $v=0$ and so the claim is trivially true.
Otherwise by the definition of the choice of $c_\beta$, we have that $t^{(k)}_{i,\beta,\ell+1}>m-W+1$ so that $t^{(k)}_{i,\beta,\ell+1}>t^{(k)}_{i,\beta,\ell}+1$.

By lem:sliding:delta:upper, it follows that $F(t^{(k)}_{i,\beta,\ell},m)-F(t^{(k)}_{i,\beta,\ell+1},m)\le 2^{-\beta/q}\cdot F_p(t_{i,\beta,k+1},m)$.
Since $\beta=\ceil{\log\frac{100\cdot 4^q}{\eps^q}}$, then it follows that $F(t^{(k)}_{i,\beta,\ell},m)-F(t^{(k)}_{i,\beta,\ell+1},m)\le\frac{\eps}{4}\cdot F(t^{(k)}_{i,\beta,\ell+1},m)$.
By lem:sw:top:constant, we have that $\frac{\eps}{4}\cdot F(t^{(k)}_{i,\beta,\ell+1},m)\le 2F(W)=2F(f)$.
Thus, $F(t^{(k)}_{i,\beta,\ell},m)-F(t^{(k)}_{i,\beta,\ell+1},m)\le\frac{\eps}{2}\cdot F(f)$.
Since the updates from the times between $t^{(k)}_{i,\beta,\ell}$ and $m$ form the vector $v+f$, we have
$F(v+f)-F(t^{(k)}_{i,\beta,\ell+1},m)\le\frac{\eps}{2}\cdot F(f)$.
Since $t^{(k)}_{i,\beta,\ell+1}>m-W+1$ then by the monotonicity of $F$, we have that $F(v+f)-F(f)\le\frac{\eps}{2}\cdot F(f)$, as desired.

We next show that we have an additive $\frac{\eps}{2}\cdot F(f)$ approximation to $F(v+f)$.
If we define

\[\Delta_j:=F\left(u-\sum_{k=1}^{j-1} u_k\right)-F\left(u-\sum_{k=1}^j u_k\right),\]

then we have

\[\sum_{j=1}^\beta\Delta_j=F(u)-F(v+f).\]

Observe that $\Delta_j$ is approximated by the active level $j$ difference estimators.
By lem:sliding:active:indices, there are at most $512$ active indices at level $j$.
Since the difference estimators are well-defined by lem:diff:est:well:defined and each difference estimator $\sdiffest$ uses accuracy parameter $\eta=\frac{\eps}{2^{20}q\log\frac{1}{\eps}}$, then the additive error in the estimation of $F(v+f)$ incurred by $Y_j$ is at most

\[512\cdot\frac{\eps}{2^{20}q\log\frac{1}{\eps}}\cdot F(u)=\frac{\eps}{2^{11}q\log\frac{1}{\eps}}\cdot F(u).\]

Summing across all $\beta\le2^9q\log\frac{1}{\eps}$ levels, then the total error in the estimation $Z$ of $F(v+f)$ across all levels $Y_j$ with $j\in[\beta]$ is at most

\[\frac{\eps}{4}\cdot F(u)\le\frac{\eps}{2}\cdot F(f).\]

Thus, we have an additive $\frac{\eps}{2}\cdot F(f)$ approximation to $F(v+f)$ as desired.
Since $F(v+f)-F(f)\le\frac{\eps}{2}\cdot F(f)$, then alg:sliding outputs a $(1+\eps)$-approximation to $F(W)$.

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)}}$.

We first observe that correctness follows from lem:sw:frame:correct for $\delta'=\O{\frac{1}{\poly(m)}}$.
To analyze the space complexity, note that we maintain $\O{\log n}$ guesses for the value of $F$ at the end of the stream, since $F$ is monotonic and polynomially bounded.
For each guess, we maintain $\O{\log\frac{1}{\eps}}$ granularities whose space complexity in total forms a geometric series that sums to $S_F(m,\delta',\eps)\cdot\polylog\frac{1}{\eps}$.
Finally, we repeat this procedure for each of the $\O{\log n}$ indices $i$ corresponding to the timestamps maintained at the top level by the smooth histogram, again because $F$ is monotonic and polynomially bounded.
Therefore, the total space used is $\frac{1}{\eps^2}\cdot S_F(m,\delta',\eps)\cdot\poly\left(\log m,\log\frac{1}{\eps}\right)$.

§.§ Moment Estimation for p in (0,2]

To improve alg:sliding for $F_p$ moment estimation with $p\in(0,2]$, we remove the additional $\O{\log n}$ overhead associated with making $\O{\log n}$ guesses for the value of $F$ at the end of the stream.
Instead, we note that since we maintain a constant factor approximation to the value of $F_p$ due to the smooth histogram, it suffices to partition the substream into blocks for the difference estimators based on the ratio of the difference to the constant factor approximation to the value of $F_p$.
We also recall the following useful characterization of the smoothness of the $F_p$ moment function.

[23]
The $F_p$ function is $\left(\eps,\frac{\eps^p}{p}\right)$-smooth for $p\ge 1$ and $(\eps,\eps)$-smooth for $0<p\le 1$.

Moreover, we require constructions of suffix-pivoted difference estimators for $F_p$ moment estimation with $p\in(0,2]$.
However, we claim that the previous constructions, i.e., the fixed-prefix difference estimator based on Li's geometric estimator for $p\in(0,2)$ and the fixed-prefix difference estimator based on the inner product sketch for $p=2$ are already valid suffix-pivoted difference estimators.
This is because the key property to approximating the difference $F_p(v+u_1)-F_p(u_1)$ in “small” space is that $F_p(v)$ is small.
We can express the variance of both Li's geometric estimator and the inner product sketch in terms of $F_p(v)$ so that smaller values of $F_p(v)$ correspond to smaller variance for the estimators.
Hence even if $F_p(v+u_2)-F_p(u_2)$ is much larger than $F_p(v+u_1)-F_p(u_1)$ for some $u_2\succeq u_1$, as long as $F_p(v+u_1)-F_p(u_1)\le\gamma\cdot F_p(v+u_1)$, then $F_p(v)\le\gamma\cdot F_p(v+u_1)\le F_p(v+u_2)$.
Therefore, the variance for our difference estimators is at most $\gamma F_p(v+u_2)^2$, so we only need to run $\O{\frac{\gamma}{\eps^2}}$ independent copies of the difference estimators.

The remaining aspects of our algorithms are the same as alg:sliding; for completeness, we give the modified algorithms in alg:sliding:smallp.

Moment Estimation in the Sliding Window Model
[1]
Stream $u_1,\ldots,u_m\in[n]$ of updates to coordinates of an underlying frequency vector, accuracy parameter $\eps\in(0,1)$, window parameter $W>0$
Robust $(1+\eps)$-approximation to $F_p$
$\delta\gets\frac{1}{\poly(n,m)}$, $\eta\gets\frac{\eps}{1024\log\frac{1}{\eps}}$, $\varphi\gets\sqrt{2}$ be a parameter
$\beta\gets\ceil{\log\frac{100\max(p,1)}{\eps^{\max(p,1)}}}$, $\gamma_j\gets 2^{3-j}$ for all $j\in[\beta]$
each update $u_t\in[n]$, $t\in[m]$
Create new subroutines for each update
Removes extraneous subroutines
Estimate $F_p$ on sliding window

Subroutine $\updatesw$ for moment estimation
[1]
Let $s$ be the number of instances of $\calA$.
$t_{s+1}\gets t$
Start a new instance $\calA(t_{s+1},t,\eta,\delta)$.
Start a new instance $\hhest(t_{s+1},t,\eta,\delta)$.
Start instances of each granularity
$t_{s+1,j,0}\gets t$
Start a new instance $\sdiffest(t_{s+1},t_{s+1,j,1},t,\gamma_j,\eta,\delta)$.
Start a new instance $\calA(t_{s+1,j,0},t_{s+1,j,1},1,\delta)$.

Subroutine $\mergesw$ for moment estimation with $p\in[1,2]$
[1]
Let $s$ be the number of instances of $\calA$ and $p\in[1,2]$.
$i\in[s]$, $j\in[\beta]$
Difference estimator maintenance
Let $r$ be the number of times $t_{i,j,*}$
Merges two algorithms with “small” contributions
$\calA(t_{i,j,k-1},t_{i,j,k+1},1,\delta)\le 2^{-j-10}\cdot\calA(t_{i},t,\eta,\delta)$
Merge (add) the sketches for $\calA(t_{i,j,k-1},t_{i,j,k},1,\delta)$ and $\calA(t_{i,j,k},t_{i,j,k+1},1,\delta)$.
Merge (add) the sketches for $\sdiffest(t_{i,j,k-1},t_{i,j,k},t,\gamma_j,\eta,\delta)$ and $\sdiffest(t_{i,j,k},t_{i,j,k+1},t,\gamma_j,\eta,\delta)$.
Relabel the times $t_{i,j,*}$.
Smooth histogram maintenance
Append the times $t_{i+1,j,*}$ to $\{t_{i,j,*}\}$.
Delete $t_{i+1}$ and all times $t_{i+1,*,*}$.
Relabel the times $\{t_i\}$ and $\{t_{i,j,*}\}$.

Subroutine $\stitchsw$ of alg:sliding for moment estimation
[1]
Let $i$ be the largest index such that $t_i\le m-W+1$.
$c_0\gets t_i$
Stitch sketches
Let $a$ be the smallest index such that $t_{i,j,a}\ge c_{j-1}$
Let $b$ be the largest index such that $t_{i,j,b}\le m-W+1$
$c_j\gets t_{i,j,b}$
$Z:=X-\sum_{j=1}^\beta Y_j$

We show alg:sliding:smallp gives a $(1+\eps)$-approximation to $F_p(W)$.
For $p\in(0,1]$, the algorithm is nearly identical to that of $p\in[1,2]$.
However due to sub-additivity, the $\mergesw$ subroutine now merges two sketches when the sum of their contributions from their difference estimator is small, rather than the sum of their moments is small.
We also show alg:sliding:smallp with the modified $\mergesw$ subroutine gives a $(1+\eps)$-approximation to $F_p(W)$ for $p\in(0,1]$.

For $p\in(0,2]$, alg:sliding:smallp outputs a $(1+\eps)$-approximation to $F_p(W)$.

Given $\eps>0$ and $p\in(0,2]$, there exists a one-pass algorithm in the sliding window model that outputs a $(1+\eps)$-approximation to the $L_p$ norm with probability at least $\frac{2}{3}$.
The algorithm uses $\O{\frac{1}{\eps^2}\log^3 n\log^3\frac{1}{\eps}}$ bits of space for $p=2$.
For $p\in(0,2)$, the algorithm uses space $\O{\frac{1}{\eps^2}\log^3 n(\log\log n)^2\log^3\frac{1}{\eps}}$.

Consider alg:sliding and note that it suffices to output a $(1+\eps)$-approximation to the $F_p$-moment of the window.
Thus correctness follows from lem:sliding:correctness:rangep.

To analyze the space complexity for $p=2$, we can use the strong tracker of thm:strong:F2 and the difference estimator of lem:diff:est:F2.
Observe that running a single instance of these subroutines with accuracy parameter $\eta$ and failure probability $\delta$ requires space $\O{\frac{\log n}{\eta^2}\left(\log\log n+\log\frac{1}{\eta}+\log\frac{1}{\delta}\right)}$.
We set the probability of failure to be $\delta=\frac{1}{\poly(n,m)}$ so that by a union bound, all algorithms in the stream are simultaneously correct at all points in time, with probability $1-\frac{1}{\poly(n)}$.

By lem:sliding:instances, we run $\O{2^j}$ instances of the suffix difference estimator at level $j$ for each $i$, with accuracy $\eta=\O{\frac{\eps}{\log\frac{1}{\eps}}}$, ratio parameter $\gamma=2^{3-j}$, and $\delta=\frac{1}{\poly(n,m)}$.
Hence, the total space used by level $j$ for a fixed $i$ is

\[\O{2^j\cdot\frac{\gamma\,\log^2 n}{\eta^2}}=\O{\frac{1}{\eps^2}\log^2 n\log^2\frac{1}{\eps}}.\]

Summing across all $j\in[\beta]$ for $\beta=\O{\log\frac{1}{\eps}}$ levels, then the total space is for a fixed $i$ is $\O{\frac{1}{\eps^2}\log^2 n\log^3\frac{1}{\eps}}$.

Since $i=\O{\log n}$, then the total space is $\O{\frac{1}{\eps^2}\log^3 n\log^3\frac{1}{\eps}}$.

For $p<2$, we can use the strong tracker of thm:strong:Fp:smallp and the difference estimator of lem:diff:est:Fp:smallp.
Since a single instance of these subroutines with accuracy parameter $\eta=\O{\frac{\eps}{\log\frac{1}{\eps}}}$ and failure probability $\delta=\frac{1}{\poly(n,m)}$ requires space at most $\O{\frac{\log^2 n}{\eta^2}(\log\log n)^2}$, then the total space is $\O{\frac{1}{\eps^2}\log^3 n(\log\log n)^2\log^3\frac{1}{\eps}}$.

§.§ Entropy Estimation in the Sliding Window Model

In this section, we show how our adversarially robust $F_p$ estimation algorithms gives a black-box algorithm for entropy estimation.
For a frequency vector $v\in\mathbb{R}^n$, we define the Shannon entropy by $H=-\sum_{i=1}^n v_i\log v_i$.

Any algorithm that gives an $\eps$-additive approximation of the Shannon Entropy $H(v)$ also gives a $(1+\eps)$-multiplicative approximation of the function $h(v):=2^{H(v)}$ (and vice versa).

Thus for the remainder of the section, we focus on obtaining a $(1+\eps)$-multiplicative approximation of $h(v)=2^{H(v)}$.

For $k=\log\frac{1}{\eps}+\log\log m$ and $\eps'=\frac{\eps}{12(k+1)^3\log m}$, there exists an efficiently computable set $\{y_0,\ldots,y_k\}$ with $y_i\in(0,2)$ for all $i$ and an efficiently computable deterministic function that takes $(1+\eps')$-approximations to $F_{y_i}(v)$ and outputs a $(1+\eps)$-approximation to $h(v)=2^{H(v)}$.

The set $\{y_0,\ldots,y_k\}$ in lem:entropy:reduction can computed as follows, described by [47].
Let $\ell=\frac{1}{2(k+1)\log m}$ and $f(z)=\frac{(k^2\ell)z-\ell(k^2+1)}{2k^2+1}$.
Then for each $y_i$, we have $y_i=1+f(\cos(i\pi/k))$, so that the set $\{y_0,\ldots,y_k\}$ in lem:entropy:reduction can be computed in linear time.
A $(1+\eps)$-multiplicative approximation to $h(v)=2^{H(v)}$ can then be computed from $2^{P(0)}$, where $P(x)$ is the degree $k$ polynomial interpolated at the points $y_0,\ldots,y_k$, so that $P(y_i)=F_{y_i}(v)$ for each $i$.

Given $\eps>0$, there exists a sliding window algorithm that outputs an additive $\eps$-approximation to Shannon entropy and uses $\tO{\frac{\log^5 n}{\eps^2}}$ bits of space and succeeds with probability at least $\frac{2}{3}$.

By obs:entropy:addmult and lem:entropy:reduction, it suffices to obtain adversarially robust $(1+\eps')$-approximation algorithms to $F_{y_i}(v)$ for all $y_i\in(0,2)$ in the set $\{y_0,\ldots,y_k\}$, where $k=\log\frac{1}{\eps}+\log\log m$ and $\eps'=\frac{\eps}{12(k+1)^3\log m}$.
By thm:sliding:main with accuracy parameter $\eps'$, we can obtain such robust algorithms approximating each $F_{y_i}(v)$, using space $\tO{\frac{1}{(\eps')^{2}}\log^2 n}$.
Moreover, with a rescaling of the failure probability $\delta'=\frac{\delta}{\poly(n,m)}$ in both lem:diff:est:Fp:smallp and thm:strong:Fp:smallp, then all algorithms simultaneously succeed with probability at least $1-\delta$.
Hence for $\eps'=\frac{\eps}{12(k+1)^3\log m}$ and $\log m=\O{\log n}$, each of the $\O{k}$ algorithms use space $\tO{\frac{1}{\eps^2}\log^5 n}$.
Since $k=\log\frac{1}{\eps}+\log\log m$, the overall space complexity follows.

§.§ Moment Estimation for Integer p>2

In this section, we describe our algorithm to estimate the $F_p$ moment in the sliding window model, for integer $p>2$.
Suppose that we have vectors $u$ and $v$ such that the vector $u$ arrives before the vector $v$ and $F_p(u)\le\gamma F_p(v)\le 2^p F_p(u)$, for some $\gamma\le 1$.
A crucial subroutine in alg:sliding is the $\mergesw$ subroutine, which controls the number of blocks in which the substream is partitioned into, at each granularity, and thus gives efficient bounds on the space of the algorithm.
alg:mergesw:smallp merges separate blocks based on their contribution to the value of the difference $F_p(u+v)-F_p(v)$.
Rather than using such a merge subroutine in this section, we will again create $\O{\log n}$ parallel instances as in alg:mergesw:frame, corresponding to exponentially increasing guesses $2^i$ for the value of $F_p(v)$ and incur the additional $\O{\log n}$ overhead in space.
We will then partition blocks based on their $F_p$ values in comparison to the guess of $F_p(v)$.
Now if each block $u$ is required to satisfy $F_p(u)\le\gamma F_p(v)\le 2^p F_p(u)$ for some $\gamma\approx\frac{1}{2^j}$, then we can assume our guess for $F_p(v)$ is incorrect if the partitioning creates more than $2^j$ blocks.
Hence, we can again assume that each block $u$ satisfies $F_p(u)\le\gamma F_p(v)\le 2^p F_p(u)$, at the cost of an additional $\O{\log n}$ overhead in space.

As in sec:sliding:smallp, it remains to find a difference estimator for $F_p(u+v)-F_p(v)$, i.e., an algorithm with space dependency $\tO{\frac{\gamma}{\eps^2}\,n^{1-2/p}}$.
Observe that $F_p(u+v)-F_p(v)=\sum_{k=1}^p\binom{p}{k}\langle u^k,v^{p-k}\rangle$.
We estimate each term $\langle u^k,v^{p-k}\rangle$ separately.

We first use a heavy-hitter algorithm $\hhest$ to simultaneously find all heavy-hitters $a\in[n]$ such that $u_a\ge\eps\gamma^{1/p}\,L_p(v)$ across all vectors $u$ induced by the blocks.
These coordinates form a set $\calH$ and we read off the corresponding coordinates of $v$ to estimate $\sum_{a\in\calH}\langle u^k,v^{p-k}\rangle$ for each $k$.
For $a\notin\calH$, we analyze separate algorithms for estimating $\sum_{a\notin\calH}\langle u,v^{p-1}\rangle$ and $\sum_{a\notin\calH}\langle u^k,v^{p-k}\rangle$ for $k\ge 2$, though the analysis is similar for both algorithms.
Thus we require the following modification to subroutine $\stitchsw$.

Subroutine $\stitchsw$ of alg:sliding: output estimate of $F_p$ on the sliding window
[1]
Let $i$ be the largest index such that $t_i\le m-W+1$.
$c_0\gets t_i$
Stitch sketches
Let $a$ be the smallest index such that $t_{i,j,a}\ge c_{j-1}$
Let $b$ be the largest index such that $t_{i,j,b}\le m-W+1$
$c_j\gets t_{i,j,b}$
each heavy-hitter $k$ output by $\calH:=\hhest(t_i,m,\eta,\delta)$
Let $g_k$ be the estimated frequency of $k$ in times $[c_{\beta},m]$.
Let $h_k$ be the estimated frequency of $k$ in times $[m-W+1,m]$.
$Z:=X-\sum_{j=1}^\beta Y_j-\sum_{k\in\calH} W_k$

Our analysis uses a level set argument.
For a sufficiently large constant $\alpha>0$, let $i,j\in[\alpha\log n]$.
Then we define the contribution $C_{i,j,k}$ of level set $L_{i,j}$ for $\langle u^k,v^{p-k}\rangle$ by

\[\sum_{a\in n}\left[u_a^kv_a^{p-k}\bfone\left(u_a\in\left[\frac{\gamma^{1/p} L_p(v)}{2^i},\frac{\gamma^{1/p} L_p(v)}{2^{i-1}}\right]\right)\bfone\left(v_a\in\left[\frac{L_p(v)}{2^j},\frac{L_p(v)}{2^{j-1}}\right]\right)\right].\]

Then we say contribution $C_{i,j,k}$ of level set $L_{i,j}$ is significant if $C_{i,j,k}\ge\frac{\eps}{p^{p+1}\log^2 n}\,F_p(v)$.

If $C_{i,j,k}$ is significant, then $2^{|i-j|}\le\frac{\gamma^{k/(p(p-k))}p^{(p+1)/(p-k)}\log^{2/(p-k)} n}{\eps^{1/(p-k)}}$.

Suppose without loss of generality that $i\le j$, so that $j=i+\ell$ for some $\ell\ge 0$.
Because $F_p(u)\le\gamma F_p(v)$, then there can be at most $2^{ip}$ indices $a\in[n]$ such that $u_a\in\left[\frac{\gamma^{1/p} L_p(v)}{2^i},\frac{\gamma^{1/p} L_p(v)}{2^{i-1}}\right]$.
Hence, we have

\[C_{i,j,k}\le 2^{ip}\cdot\left(\frac{\gamma^{1/p} L_p(v)}{2^i}\right)^k\cdot\left(\frac{L_p(v)}{2^j}\right)^{p-k}=\frac{\gamma^{k/p}}{2^{\ell(p-k)}}\,F_p(v).\]

Since $C_{i,j,k}$ is significant, then $C_{i,j,k}\ge\frac{\eps}{p^{p+1}\log^2 n}\,F_p(v)$, which implies that $2^{\ell(p-k)}\le\frac{\gamma^{k/p}p^{p+1}\log^2 n}{\eps}$ and thus $2^j\le 2^i\,\frac{\gamma^{k/(p(p-k))}p^{(p+1)/(p-k)}\log^{2/(p-k)} n}{\eps^{1/(p-k)}}$.

We first run a heavy-hitters algorithm to find all indices $a\in[n]$ such that

\[u_a\ge\frac{\eps}{100p^{p+1}\log^2 n}\gamma^{1/p} L_p(v)\ge\frac{\eps}{100p^{p+1}\log^2 n} L_p(u),\]

which takes $\tO{\frac{1}{\eps^2}\,n^{1-2/p}}$ space, since $F_p(u)\le\gamma F_p(v)$.
Thus we bound the variance for a significant level set $L_{i,j}$ with $2^i\ge\frac{\eps}{100p^{p+1}\log^2 n}$.

* Find a list $\calH$ that includes all $a\in[n]$ with $u_a\ge\frac{\eps}{100p^{p+1}\log^2 n}\|u\|_p$.

* Using $\countsketch$, obtain an estimate $\widehat{u_a}$ to $u_a$ with additive error $\frac{\eps}{100p^{p+1}\log^2 n}\|u\|_p$ for each $a\in\calH$ and let $h\in\mathbb{R}^n$ be the vector such that $h_a=\widehat{u_a}$ if $a\in\calH$ and zero otherwise.

* Perform perfect $L_2$ sampling on $w:=u-h$ to obtain a set $\calS$ of size $k=\O{\frac{\gamma}{\eps^2}n^{1-2/p}}$.

* Obtain an estimate $\widehat{w_a}$ to $w_a$ for each $a\in\calS$.

* Let $\widehat{W}$ be a $(1+\eps)$-approximation to $\|w\|_2^2$.

* Output $W+\sum_{k=1}^{p-1}\binom{p}{k}\left(\sum_{a\in\calH}\widehat{v_a}^k,u_a^{p-k}+W\cdot\sum_{a\in\calS}\widehat{w_a}^{k-2},u_a^{p-k}\right)$.

For integer $p>2$, there exists an algorithm that uses space $\tO{\frac{\gamma}{\eps^2}n^{1-2/p}}$ and outputs an additive $\eps\cdot F_p(u)$ approximation to $\langle u^k,v^{p-k}\rangle$ with high probability for any $k\ge 2$.

We first show that our algorithm gives an additive $\frac{\eps}{p^{p+1}} F_p(v)$ approximation to $\langle u^k,v^{p-k}\rangle$ with $k\ge 2$.
To that end, we show that our algorithm gives an additive $\frac{\eps}{p^{p+1}\log^2 n} F_p(v)$ approximation to each contribution $C_{i,j,k}$ of level set $L_{i,j}$.
Let $h\in\mathbb{R}^n$ be the vector such that $h_a=\widehat{u_a}$ if $a\in\calH$ and zero otherwise and let $w:=u-h$.

We use $\sampler$ to sample indices $j_1,\ldots,j_\ell\in[n]$ with so that each sample is a coordinate $a\in[n]$ with probability $\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}$.
We obtain unbiased estimates to $\widehat{w_{j_1}^{k-2}},\ldots,\widehat{w_{j_\ell}^{k-2}}$ of $w_{j_1}^{k-2},\ldots,w_{j_\ell}^{k-2}$ through lem:coor:exp:var.
We also obtain a $(1+\O{\eps})$-approximation unbiased estimate $W$ of $\|w\|_2^2$.
Thus for each $b\in[\ell]$, the product $\widehat{w_{j_b}^{k-2}}\cdot W\cdot v_{j_b}^{p-k}$ satisfies

\begin{align*}
\Ex{\widehat{w_{j_b}^{k-2}}\cdot W\cdot v_{j_b}^{p-k}}&=\sum_{a\in\calH}\ip{\widehat{u_a}^{k}}{v_a^{p-k}}+\sum_{i,j}\sum_{a\in L_{i,j}\cap\calH}\left(\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^{k-2}\cdot(1\pm\O{\eps})\|w\|_2^2\cdot v_a^{p-k}\\
&+\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}\left(\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^{k-2}\cdot(1\pm\O{\eps})\|w\|_2^2\cdot v_a^{p-k}.
\end{align*}

Observe that since $\widehat{u_a}$ is an additive $\eps\gamma^{1/p}\,L_p(v)$-approximation to $u_a$ for $a\in\calH$, then $|w_a|\le\eps|u_a|$, so that the second summation is at most $\O{\eps}\,\langle u^k, v^{p-k}\rangle$.
Moreover, we have $w_a=u_a$ for $a\in[n]\setminus\calH$, so that

\begin{align*}
\Ex{\widehat{w_{j_b}^{k-2}}\cdot W\cdot v_{j_b}^{p-k}}&\in(1\pm\O{\eps})|\ip{w^{k}}{v^{p-k}}|+\frac{1}{\poly(n)}.
\end{align*}

For $a\in L_{i,j}\setminus\calH$, we have $w_a\le u_a\le\eps\gamma^{1/p}\,L_p(v)$.
Thus, the variance is at most

\begin{align*}
\Var\left(\widehat{w_{j_b}^{k-2}}\cdot W\cdot v_{j_b}^{p-k}\right)&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}\left(\frac{w_a^2}{\|w\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^{2k-4}\cdot(1\pm\O{\eps})\|w\|_2^4\cdot v_a^{2p-2k}\\
&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}(1\pm\O{\eps})w_a^{2k-2}\cdot\|w\|_2^2\cdot v_a^{2p-2k}\\
&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}(1\pm\O{\eps})\frac{\eps^p\gamma^2\,(L_p(v))^{2p-2}}{2^{2ip}}\frac{\gamma^{2k/p}p^{p(2p+2)}\log^4 n}{\eps^2}\,\|w\|_2^2\\
&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}\frac{Cn^{1-2/p}\eps^p\gamma\,(F_p(v))^2\log^4 n}{2^{2ip}\eps^2},
\end{align*}

for some constant $C>0$.
Hence, we have

\begin{align*}
\Var\left(\widehat{w_{j_b}^{k-2}}\cdot W\cdot v_{j_b}^{p-k}\right)&\le\sum_{i,j}2^{ip}\cdot\frac{Cn^{1-2/p}\eps^p\gamma\,(F_p(v))^2\log^4 n}{2^{2ip}\eps^2}\\
&\le\O{\log^2 n}\cdot\frac{Cn^{1-2/p}\eps^p\gamma\,(F_p(v))^2\log^4 n}{\eps^2}.
\end{align*}

Thus by setting $\ell=\O{\frac{\gamma}{\eps^2}n^{1-2/p}}$, we obtain an additive $\frac{\eps}{p^{p+1}}\cdot F_p(v)$ approximation to $\langle u^k,v^{p-k}\rangle$ for $k\ge2$, with constant probability.
We can then boost this probability to $1-\frac{\delta}{\poly(n)}$ by repeating $\O{\log\frac{n}{\delta}}$ times.

We use a similar approach to estimate $\langle u,v^{p-1}\rangle$.

* Use a set of exponential random variables to form a vector $W$ of duplicated and scaled coordinates of $w$.

* Hash the coordinates of $W$ into a $\countsketch$ data structure with $\O{\log n}$ buckets.

* Use the same exponential random variables to perform perfect $L_2$ sampling on $v$ to obtain a coordinate $(i,j)$ and an unbiased estimate $\widehat{v_{i,j}}$ to $v_{i,j}$.

* Let $\widehat{V}$ be an unbiased estimate of $\|v\|_2^2$ with second moment $\O{\|v\|_2^4}$.

* Query $\countsketch$ for an unbiased estimate $\widehat{w_{i,j}}$ to $w_{i,j}$ and set an estimator as $\widehat{V}\cdot\widehat{w_{i,j}}\left(\widehat{v_{i,j}}\right)^{p-3}$.

* Output the mean of $\tO{\frac{\gamma}{\eps^2}\cdot n^{1-2/p}}$ such estimators.

For integer $p>2$, there exists an algorithm that uses space $\tO{\frac{\gamma}{\eps^2}n^{1-2/p}}$ and outputs an additive $\eps\cdot F_p(u)$ approximation to $\langle u,v^{p-1}\rangle$ with high probability.

We use $\sampler$ to sample indices $j_1,\ldots,j_\ell\in[n]$ with so that each sample is a coordinate $a\in[n]$ with probability $\frac{v_a^2}{\|v\|_2^2}+\frac{1}{\poly(n)}$.
We obtain unbiased estimates to $\widehat{v_{j_1}^{p-1}},\ldots,\widehat{v_{j_\ell}^{p-1}}$ of $v_{j_1}^{p-1},\ldots,w_{j_\ell}^{p-1}$ through lem:coor:exp:var.
We also obtain a $(1+\O{\eps})$-approximation unbiased estimate $V$ of $\|v\|_2^2$.
Thus for each $b\in[\ell]$, the product $\widehat{w_{j_b}}\cdot V\cdot v_{j_b}^{p-3}$ satisfies

\begin{align*}
\Ex{\widehat{w_{j_b}}\cdot V\cdot v_{j_b}^{p-3}}&=\sum_{a\in\calH}\langle\widehat{u_a},v_a^{p-1}\rangle+\sum_{i,j}\sum_{a\in L_{i,j}\cap\calH}\left(\frac{v_a^2}{\|v\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a\cdot(1\pm\O{\eps})\|v\|_2^2\cdot v_a^{p-3}\\
&+\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}\left(\frac{v_a^2}{\|v\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a\cdot(1\pm\O{\eps})\|w\|_2^2\cdot v_a^{p-3}.
\end{align*}

Observe that since $\widehat{u_a}$ is a $(1+\eps)$-approximation to $u_a$ for $a\in\calH$, then $|w_a|\le\eps|u_a|$, so that the second summation is at most $\O{\eps}\,\langle u, v^{p-1}\rangle$.
Moreover, we have $w_a=u_a$ for $a\in[n]\setminus\calH$, so that

\begin{align*}
\Ex{\widehat{w_{j_b}}\cdot V\cdot v_{j_b}^{p-3}}&\in(1\pm\O{\eps})|\langle w, v^{p-1}\rangle|+\frac{1}{\poly(n)}.
\end{align*}

For $a\in L_{i,j}\setminus\calH$, we have $w_a\le u_a\le\eps\gamma^{1/p}\,L_p(v)$.
Thus, the variance is at most

\begin{align*}
\Var\left(\widehat{w_{j_b}}\cdot V\cdot v_{j_b}^{p-3}\right)&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}\left(\frac{v_a^2}{\|v\|_2^2}+\frac{1}{\poly(n)}\right)\cdot w_a^2\cdot(1\pm\O{\eps})\|v\|_2^4\cdot v_a^{2p-6}\\
&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}(1\pm\O{\eps})w_a^2\cdot\|v\|_2^2\cdot v_a^{2p-6}\\
&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}(1\pm\O{\eps})\frac{\eps^p\gamma^{2/p}\,(L_p(v))^{2p-2}}{2^{2ip}}\frac{\gamma^{2k/p}p^{p(2p+2)}\log^4 n}{\eps^2}\,\|v\|_2^2\\
&\le\sum_{i,j}\sum_{a\in L_{i,j}\setminus\calH}\frac{Cn^{1-2/p}\eps^p\gamma^{2/p}\,(F_p(v))^2\log^4 n}{2^{2ip}\eps^2},
\end{align*}

for some constant $C>0$.

\begin{align*}
\Var\left(\widehat{w_{j_b}}\cdot V\cdot v_{j_b}^{p-3}\right)&\le\sum_{i,j}2^{ip}\cdot\frac{Cn^{1-2/p}\eps^p\gamma^{2/p}\,(F_p(v))^2\log^4 n}{2^{2ip}\eps^2}\\
&\le\O{\log^2 n}\cdot\frac{Cn^{1-2/p}\eps^p\gamma\,(F_p(v))^2\log^4 n}{\eps^2}.
\end{align*}

Hence for $\gamma\ge\O{\eps^p}$, we have that by setting $\ell=\O{\frac{\gamma}{\eps^2}n^{1-2/p}}$, we obtain an additive $\frac{\eps}{p^{p+1}}\cdot F_p(v)$ approximation to $\langle u,v^{p-1}\rangle$, with constant probability.
We can then boost this probability to $1-\frac{\delta}{\poly(n)}$ by repeating $\O{\log\frac{n}{\delta}}$ times.

For integer $p>2$, there exists a $(\gamma,\eps,\delta)$-difference estimator for $F_p$ that uses space $\tO{\frac{\gamma n^{1-2/p}}{\eps^2}}$.

By applying the same argument as lem:sw:frame:correct using the difference estimators in this section, we have:

For integer $p>2$, alg:sliding outputs a $(1+\eps)$-approximation to $F_p(W)$.

Given $\eps>0$ and integer $p>2$, there exists a one-pass algorithm in the sliding window model that outputs a $(1+\eps)$-approximation to the $L_p$ norm with probability at least $\frac{2}{3}$ and uses $\tO{\frac{1}{\eps^2}\,n^{1-2/p}}$ bits of space.

Consider alg:sliding and note that it suffices to output a $(1+\eps)$-approximation to the $F_p$-moment of the window.
Thus correctness follows from lem:sliding:correctness:largep.

We use the strong tracker of thm:strong:Fp:largep and the difference estimator of lem:sw:diff:est:Fp:largep.
By lem:sliding:instances, we run $\O{2^j}$ instances of the suffix difference estimator at level $j$ for each $i$, with accuracy $\eta=\O{\frac{\eps}{\log\frac{1}{\eps}}}$, ratio parameter $\gamma=2^{3-j}$, and $\delta=\frac{1}{\poly(n,m)}$.
Hence, the total space used by level $j$ for a fixed $i$ is

\[\tO{2^j\cdot\frac{\gamma\,n^{1-2/p}}{\eta^2}}=\tO{\frac{n^{1-2/p}}{\eps^2}}.\]

Summing across all $j\in[\beta]$ for $\beta=\O{\log\frac{1}{\eps}}$ levels and all values of $i=\O{\log n}$, then the algorithm uses $\tO{\frac{1}{\eps^2}\,n^{1-2/p}}$ bits of space in total.

§ ACKNOWLEDGEMENTS

We would like to thank Zhili Feng for discussions in the early stages of this work.
This work was supported by National Science Foundation (NSF) Grant No. CCF-1815840, National Institute of Health (NIH) grant 5R01 HG 10798-2, and a Simons Investigator Award.

We would also like to thank Moshe Shechner and Uri Stemmer for pointing out an error in our bounded flip number algorithm for dynamic streams in a previous version of this paper.
In this version, we have introduced the notion of twist number to resolve this issue and refer to their follow-up work [2] for more details.

[1]
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, and David P. Woodruff.
Streaming complexity of svms.
In Approximation, Randomization, and Combinatorial Optimization.