# High Probability Frequency Moment Sketches

Sumit Ganguly
Indian Institute of Technology,
Kanpur, India
<EMAIL_ADDRESS>David P. Woodruff
School of Computing,
Carnegie Mellon University,
Pittsburg, USA
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of sketching the $p$-th frequency moment of a vector,
$p>2$, with multiplicative error at most $1\pm\epsilon$ and _with high
confidence_ $1-\delta$. Despite the long sequence of work on this problem,
tight bounds on this quantity are only known for constant $\delta$. While one
can obtain an upper bound with error probability $\delta$ by repeating a
sketching algorithm with constant error probability $O(\log(1/\delta))$ times
in parallel, and taking the median of the outputs, we show this is a
suboptimal algorithm! Namely, we show optimal upper and lower bounds of
$\Theta(n^{1-2/p}\log(1/\delta)+n^{1-2/p}\log^{2/p}(1/\delta)\log n)$ on the
sketching dimension, for any constant approximation. Our result should be
contrasted with results for estimating frequency moments for $1\leq p\leq 2$,
for which we show the optimal algorithm for general $\delta$ is obtained by
repeating the optimal algorithm for constant error probability
$O(\log(1/\delta))$ times and taking the median output. We also obtain a
matching lower bound for this problem, up to constant factors.

##  1 Introduction

The frequency moments problem is a very well-studied and foundational problem
in the data stream literature. In the data stream model, an algorithm may use
only sub-linear memory and a single pass over the data to summarize a data
stream that appears as a sequence of incremental updates. A data stream may be
viewed as a sequence of $m$ records of the form
$((i_{1},v_{1}),(i_{2},v_{2}),\ldots,(i_{m},v_{m}))$, where,
$i_{j}\in[n]=\\{1,2,\ldots,n\\}$ and $v_{j}\in{\mathbb{R}}$. The record
$(i_{j},v_{j})$ changes the $i_{j}$th coordinate $x_{i_{j}}$ of an underlying
$n$-dimensional vector $x$ to $x_{i_{j}}+v_{j}$. Equivalently, for $i\in[n]$,
$x_{i}=\sum_{j:i_{j}=i}v_{j}$. Note that $v_{j}$ may be positive or negative,
which corresponds to the so-called turnstile model in data streams. Also, the
$i$-th coordinate of $x$ is sometimes referred to as the frequency of item
$i$, though note that it can be negative in the turnstile model. The $p$-th
moment of $x$ is defined to be $F_{p}=\sum_{i\in[n]}\lvert x_{i}\rvert^{p}$,
for a real number $p\geq 0$, which for $p\geq 1$ corresponds to the $p$-th
power of the $\ell_{p}$-norm $\|x\|_{p}^{p}$ of $x$.

The $F_{p}$ estimation problem with approximation parameter $\epsilon$ and
failure probability $\delta$ is: design an algorithm that makes one pass over
the input stream and returns $\hat{F}_{p}$ such that
$\text{Pr}\bigl{[}\lvert\hat{F}_{p}-F_{p}\rvert\leq\epsilon F_{p}\bigr{]}\geq
1-\delta$. Such an algorithm is also referred to as an
$(\epsilon,\delta)$-approximation of $F_{p}$. This is a problem that is among
the ones that has received the most attention in the data stream literature,
and we only give a partial list of work on this problem [AMS99, And, AKO10,
ANPW13, BYJKS02, BGKS06, BO10, CKS03, CK04, Gan04a, Gan04b, Gan11, Ind00,
IW05, KNPW11b, KNW10a, KNW10b, LW13, MW10, WW15].

We study the class of algorithms based on linear sketches, which store only a
sketch $S\cdot x$ of the input vector $x$ and a (possibly randomized) matrix
$A$. This model is well-studied, both for the problem of estimating norms and
frequency moments [ANPW13, HW13, LW13, PW12], and for other problems such as
estimating matrix norms [LNW14], and matching size [AKLY16, Kon15]. The
efficiency is measured in terms of the sketching dimension which is the
maximum number of rows of a matrix $S$ used by the algorithm. Since the
algorithm is randomized, it may choose different $S$ based on its randomness,
so the maximum is taken over its randomness. Linear sketches are particularly
useful for data streams since given an update $(i_{j},v_{j})$, one can update
$Sx$ as $S(x+v_{j}e_{i_{j}})=Sx+Sv_{j}e_{i_{j}}$, where $e_{i_{j}}$ is the
standard unit vector in the $i_{j}$-th direction. They are also used in
distributed environments, since given $S\cdot x$ and618 $S\cdot y$, one can
add these to obtain $S\cdot(x+y)$, the sketch of $x+y$.

When $0<p\leq 2$, one can achieve a sketching dimension of
$O(\epsilon^{-2}\log(1/\delta))$ independent of $n$ [AMS99, KNPW11b, KNW10b],
while for $p=0$ the sketching dimension is
$O(\epsilon^{-2}(\log(1/\epsilon)+\log\log n)\log(1/\delta))$ [KNW10a]. For
$p=2$ there is a sketching lower bound of
$\Omega(\epsilon^{-2}\log(1/\delta))$ [KMN11], which implies an optimal
algorithm for general $\delta$ is to run an optimal algorithm with error
probability $1/3$ and take the median of $O(\log(1/\delta))$ independent
repetitions. As a side result, we show in the full version a lower bound of
$\Omega(\epsilon^{-2}\log(1/\delta))$ for any $1\leq p<2$, which shows this
strategy of amplifying the success probability by $O(\log 1/\delta)$
independent repetitions is also optimal for any $1\leq p<2$.

Perhaps surprisingly, for $p>2$, the sketching dimension needs to be
polynomial in $n$, as first shown in [PW12], with the best known lower bounds
being $\Omega(n^{1-2/p}\log n)$ [ANPW13] for constant $\epsilon$ and $\delta$,
and $\Omega(n^{1-2/p}\epsilon^{-2})$ for constant $\delta$ [LW13]. Regarding
upper bounds, we present the long list of bounds in Table 1. The best known
upper bound is
$O(n^{1-2/p}\epsilon^{-2}\log(1/\delta)+n^{1-2/p}\epsilon^{-4/p}\log
n\log(1/\delta))$ [Gan11]. This is tight only when $\epsilon$ and $\delta$ are
constant, in which case it matches [ANPW13], or when $\delta$ is constant and
$\epsilon<1/{\mathrm{poly}}(\log n)$, since it matches [LW13].

$F_{p}$ Algorithm | Sketching Dimension
---|---
[IW05] | $O(n^{1-2/p}\epsilon^{-O(1)}\log^{O(1)}n\log(1/\delta))$
[BGKS06] | $O(n^{1-2/p}\epsilon^{-2-4/p}\log n\log(M)\log(1/\delta))$
[MW10] | $O(n^{1-2/p}\epsilon^{-O(1)}\log^{O(1)}n\log(1/\delta))$
[AKO10] | $O(n^{1-2/p}\epsilon^{-2-6/p}\log n\log(1/\delta))$
[BO10] | $O(n^{1-2/p}\epsilon^{-2-4/p}\log n\cdot g(p,n)\log(1/\delta))$
[And] | $O(n^{1-2/p}\log n\epsilon^{-O(1)}\log(1/\delta))$
[Gan11], Best upper bound | $O(n^{1-2/p}\epsilon^{-2}\log(1/\delta)+n^{1-2/p}\epsilon^{-4/p}\log n\log(1/\delta))$

Table 1:  Here, $g(p,n)=\min_{c\textrm{ constant }}g_{c}(n)$, where
$g_{1}(n)=\log n$, $g_{c}(n)=\log(g_{c-1}(n))/(1-2/p)$. We start the upper
bound timeline with [IW05], since that is the first work which achieved an
exponent of $1-2/p$ for $n$. For earlier work which achieved worse exponents
for $n$, see [AMS99, CK04, Gan04a, Gan04b].

###  1.1 Our Contributions

In this work, we show optimal upper and lower bounds of
$\Theta(n^{1-2/p}\log(1/\delta)+n^{1-2/p}\log^{2/p}(1/\delta)\allowbreak\log
n)$ on the sketching dimension for $F_{p}$-estimation, for any $p>2$, and for
any constant $\epsilon$. Our upper bound shows, perhaps surprisingly, that the
optimal bound is not to run $O(\log(1/\delta))$ independent repetitions of a
constant success probability algorithm and report the median of the outputs.
Indeed, such an algorithm would give a worse $O(n^{1-2/p}\log(1/\delta)\log
n)$ sketching dimension.

For general $\epsilon$, our upper bound is
$O(n^{1-2/p}\epsilon^{-2}\log(1/\delta)+n^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta)\log
n)$ and our lower bound is
$\Omega(n^{1-2/p}\epsilon^{-2}\log(1/\delta)+n^{1-2/p}\epsilon^{-2/p}\log^{2/p}(1/\delta)\log
n)$, which differ by at most an $\epsilon^{-2/p}$ factor. Our results thus
come close to resolving the complexity for general $\epsilon$ as well.

Our results should be contrasted to $1\leq p\leq 2$, for which the optimal
sketching dimension for such $p$ is $\Theta(\epsilon^{-2}\log(1/\delta))$, and
so for these $p$ it is optimal to run $O(\log(1/\delta))$ independent
repetitions of a constant probability algorithm. Here we strengthen the
$\Omega(\epsilon^{-2}\log(1/\delta))$ bound for $p=2$ of [KMN11] by showing
the same bound for $1\leq p\leq 2$.

####  1.1.1 Overview of Upper Bound

In order to obtain a confidence of $1-\delta$, we use the
$d=\lceil\log(1/\delta)\rceil$th moment of an estimate $\hat{F}_{p}$ of
$F_{p}$. Since we are unable to use the $d$th moment of the Taylor polynomial
estimator of [Gan15], we employ a different estimator $X_{i}$ for estimating
individual coordinates $\lvert x_{i}\rvert$ and use it as $X_{i}^{p}$ to
estimate $\lvert x_{i}\rvert^{p}$. This estimator is based on (a) using random
$q$th roots of unity for sketches instead of standard Rademacher variables,
and (b) taking the _average_ of the estimates from those tables where the item
does not collide with the set of top-$k$ estimated heavy hitters.

The Shelf Structure. The algorithm uses two structures, namely, a ghss-like
structure from [Gan15] and a new shelf structure , which is our main
algorithmic novelty (both formally defined later). The shelf structure is
necessary when the failure probability is $\delta=n^{-\omega(1)}$; otherwise,
for $\delta=n^{-\Theta(1)}$, somewhat surprisingly the ghss structure of
[Gan15] alone suffices with parameter
$C=n^{1-2/p}(\epsilon^{-2}\log(1/\delta)/\log(n)+\epsilon^{-4/p}\log^{2/p}(1/\delta))$
and number of measurements $O(C\log n)$, which requires a some-what intricate
$d$-th moment analysis of the ghss structure.

Figure 1: Shelf structure and level sets for each shelf index $j$ whose
contribution to $F_{p}$ is estimated accurately.

The shelf structure is partitioned into shelves, indexed from $j=0,\ldots,J$,
for a value $J$ which is specified below. Each shelf consists of a pair of
CountSketch like structures, $\textsf{HH}_{j}$ and $\textsf{AvgEst}_{j}$. The
number of buckets in the tables of the $j$th shelf is $H_{j}$ and the number
of tables in the $j$th shelf of the $\textsf{HH}_{j}$ structure is $w_{j}$ and
of the $\textsf{AvgEst}_{j}$ structure is $2w_{j}$. We set
$H_{J}=\Theta(n^{1-2/p}\epsilon^{-2})$ and $w_{J}=\Theta(\log(1/\delta))$,
while $H_{0}=\Theta(n^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta))$ and
$w_{0}=s=\Theta(\log n)$. In particular, the shelf numbered zero coincides
with the ghss level zero. The input vector $x$ is provided as input to all the
shelves’ structures. The levels of the ghss structure and the shelves of the
shelf structure can also be viewed as a single structure starting from shelf
numbered $J,J-1,\ldots,0$, and level numbers $1,2\ldots,L$. Here we consider
the interesting case when $H_{J}=o(H_{0})$, otherwise, (i.e., when
$H_{J}=\Omega(H_{0})$) there are just two shelves and $J=1$. The table height
$H_{j}=H_{0}b^{j}$ decays geometrically with parameter $0<b<1$ and the table
width $w_{j}=w_{0}a^{j}$ increases geometrically with parameter $a>1$. Note
that the parameters $a$ and $b$ determine $J$. By requiring that $\lvert
1-ab\rvert=\Omega(1)$, we ensure that the total number of measurements of the
shelf structure is $\sum_{j=0}^{J}H_{j}w_{j}=O(H_{0}w_{0}+H_{J}w_{J})$, no
matter which value of $J$ we choose. For the shelf structure, frequency-wise
thresholds are defined as $U_{j}=O(\hat{F}_{2}/H_{j})^{1/2}$, for
$j=0,1,\ldots,J$. The shelf frequency group corresponding to shelf $j$ is
$S_{j}=[U_{j},U_{j+1})$, where, $U_{J+1}=\infty$ and $U_{0}=T_{0}$. We
sometimes conflate $S_{j}$ with the set of items whose frequency belongs to
$S_{j}$. The frequency group $G_{0}$ is defined as $[T_{0},U_{1}]$ and
coincides with $S_{0}$.

So why a shelf structure? Suppose for simplicity that $\epsilon$ is a
constant. Consider a vector $x$ which has a constant number of “large”
coordinates of value $\Theta(n^{1/p})$, and $\Theta(n)$ remaining “small”
coordinates of absolute value $O(1)$. Then we need to find all the large
coordinates to accurately estimate $F_{p}$ up to a small constant factor. This
is well-known to be possible with $\Theta(n^{1-2/p})$ buckets in the $J$-th
shelf, since with probability $1-\delta$, each of the large coordinates will
not collide with any other large coordinate in more than a small constant
fraction of tables. Note that in each table, in each bucket containing a large
coordinate, the “noise” in the bucket from small coordinates will be
$Cn^{1/p}$ for an arbitrarily small constant $C>0$ with constant probability,
and so this will happen in most buckets containing a large coordinate in most
tables with probability $1-\delta$.

However, now consider a vector $x$ which has $\Theta(\log(1/\delta))$ “large-
ish” coordinates of value $\Theta(n^{1/p}/\log^{1/p}(1/\delta))$, and
$\Theta(n)$ remaining “small” coordinates of absolute value $O(1)$, as before.
Then we again need to find most of the “large-ish” coordinates to accurately
estimate $F_{p}$ up to a constant factor. We also cannot subsample and try to
estimate how many large-ish coordinates there are from a subsample. Indeed,
since there are only $O(\log(1/\delta))$ total large-ish coordinates, sub-
sampling would not accurately estimate this total with probability at least
$1-\delta$. However, to find these “large-ish” coordinates, we need to
increase the number of buckets from $\Theta(n^{1-2/p})$ to
$\Theta(n^{1-2/p}\cdot\log^{2/p}(1/\delta))$ just so that in a bucket
containing one of these coordinates, with constant probability the noise will
not be too large. But if we then want this to happen for a $1-\delta$ fraction
of tables, we still need $\Theta(\log(1/\delta))$ tables, which gives overall
$\Theta(n^{1-2/p}\cdot\log^{1+2/p}(1/\delta))$ measurements, which is above
our desired total of
$O(n^{1-2/p}(\log(1/\delta)+\log(n)\log^{2/p}(1/\delta)))$ measurements.

So what went wrong? The key idea in our analysis is to relax the requirement
of trying to recover all the larg-ish coordinates with probability $1-\delta$.
Suppose instead of $\Theta(\log(1/\delta))$ tables we just use $\Theta(\log
n)$ tables. Then with probability $1-1/n$, there may be two large-ish
coordinates which collide and cancel with each other in every single table,
and we have no way of recovering them. However, we are able to show that with
probability $1-\delta$, only $O(\log(1/\delta)/\log n)$ large-ish coordinates
will fall into this category, and neglecting this roughly $(1-1/\log n)$
fraction of the large-ish coordinates will not affect our estimate of $F_{p}$
by more than a constant factor. And indeed, our $0$-th shelf has exactly
$\Theta(n^{1-2/p}\cdot\log^{2/p}(1/\delta))$ buckets and $\Theta(\log n)$
tables, so is exactly suited for finding these large-ish coordinates. In
general, we can show that one of our shelves will be able to handle every
vector with coordinates of magnitude between the large and large-ish
coordinates. Again, by choosing the shelf structure carefully, the total
number of measurements is dominated by that in the zero-th plus the $J$-th
shelf, giving us $O(n^{1-2/p}(\log(1/\delta)+\log(n)\log^{2/p}(1/\delta)))$
total measurements, and explaining where the $\log^{2/p}(1/\delta)$ in the
upper bound comes from.

The Non-Large-ish Coordinates. Our shelves are designed to estimate the
contribution to $F_{p}$ from all coordinates of absolute value at least
$\Theta(n^{1/p}/\log^{1/p}(1/\delta))$. For coordinates of smaller value, we
can now afford to sub-sample and apply the same $0$-th shelf structure to
estimate their contribution to $F_{p}$. We apply the ghss structure, which is
analogous to the structure presented in [Gan15] and has $L+1$ levels
corresponding to $l=0,\ldots,L$, and consists of a pair of CountSketch like
structures $\textsf{HH}_{l}$ and $\textsf{AvgEst}_{l}$ at each level. The sub-
sampling technique and the associated frequency-wise thresholds and frequency
groups are defined analogously (with new parameters) to [Gan15].

A notable difference with [Gan15] is that the AvgEst structures in the ghss
and shelf structures use complex $q$th roots of unity and return the average
of table estimates instead of the median of table estimates used by
CountSketch, which are novelties in this context, though have been used for
other data stream problems [KNPW11a]. We have that
$\mathbf{E}\left[X_{i}^{p}\right]=\lvert x_{i}\rvert^{p}(1\pm n^{-\Omega(1)})$
for our estimator $X_{i}$ of $\lvert x_{i}\rvert$, and thus $X_{i}^{p}$
provides a nearly unbiased estimator of $\lvert x_{i}\rvert^{p}$.
Additionally, we use averaging in the definition of $X_{i}$ instead of the
median to allow for a tractable, though intricate calculation of the $d$-th
moment of the sum of the $p$-th powers of $X_{i}$.

####  1.1.2 Overview of Lower Bounds

We give an overview for the case of constant $\epsilon$. In both cases we
start by applying Yao’s minimax principle for which we fix $S$ and then design
a pair of distributions $\alpha$ and $\beta$ which must be distinguished by an
$(\epsilon,\delta)$-approximation algorithm for $F_{p}$. We can also assume
the rows of $S$ are orthonormal, since a change of basis to the row space of
$S$ can always be applied in post-processing.

Our $\Omega(n^{1-2/p}\epsilon^{-2/p}(\log^{2/p}1/\delta)\log n)$ bound. This
is our technically more involved lower bound. We first upper bound the
variation distance using the $\chi^{2}$-divergence as in [ANPW13] and work
only with the latter. We let $\alpha=N(0,I_{n})$ be an $n$-dimensional
isotropic Gaussian distribution, while $\beta$ is a distribution formed by
sampling an $x\sim N(0,I_{n})$, together with a random subset $T\subset[n]$ of
size $O(\log(1/\delta))$, and outputting $z=x+\sum_{i\in
T}(Cn^{1/p}/t^{1/p})e_{i}$, where $e_{i}$ is the $i$-th standard unit vector
and $C>0$ is a constant. For $y\sim\alpha$ and $z\sim\beta$, one can show that
with probability $1-O(\delta)$, one has that $\|z\|_{p}^{p}$ is a constant
factor larger than $\|y\|_{p}^{p}$, since $\|y\|_{p}^{p}$ and $\|x\|_{p}^{p}$
are concentrated at $\Theta(n)$, while $\sum_{i\in T}C^{p}n/t=\Theta(n)$.

A common technique in upper bounds, including our own, is the notion of
subsampling, whereby a random fraction of roughly $1/2^{i}$ of the $n$
coordinates are sampled, for each value of $i\in O(\log n)$, and information
is then gathered for each $i$ and combined into an overall estimate of
$F_{p}$. We choose our hard distributions so that subsampling does not help.
Indeed, if one subsamples half of the coordinates of $z\sim\beta$, with
probability $\Omega(\delta)$ all of the coordinates in $T$ will be removed, at
which point $z$ is indistinguishable from $y\sim\alpha$. Therefore, our pair
of distributions suggests itself as being hard for
$(\Theta(1),\delta)$-approximate $F_{p}$ algorithms.

What drives our analysis is conditioning our distributions on an event
$\mathcal{G}$ which only happens with probability $\Omega(\delta)$. Note that
for any algorithm which can distinguish samples from $\alpha$ from those from
$\beta$ with probability at least $1-\delta$, it must still have probability
$9/10$, say, of distinguishing the distributions given an event $\mathcal{G}$
which occurs for samples drawn from $\beta$. The event $\mathcal{G}$
corresponds to every $i\in T$ having the property that the corresponding
column $S_{i}$ of our sketching matrix $S$ has squared length at most $2r/n$,
where $r$ is the number of rows of $S$. By a Markov bound, half of the columns
of $S$ have this property, and since $T$ has size $O(\log 1/\delta)$, with
probability $\Omega(\delta)$, event $\mathcal{G}$ occurs.

We analyze the $\chi^{2}$-divergence of the distributions $\alpha$ and $\beta$
conditioned on $\mathcal{G}$. One technique helpful for this is an equality
given by Fact 69, which states that for $p$ a distribution on
${\mathbb{R}}^{n}$, that $\chi^{2}(N(0,I_{n})\ast p,N(0,I_{n}))={\bf
E}[e^{\langle X,X^{\prime}\rangle}]-1,$ where $X$ and $X^{\prime}$ are
independently drawn from $p$. This equality was used in [ANPW13, LNW14, Woo14]
among other places. In our case, the inner product of $X$ and $X^{\prime}$
corresponds to an inner product $P$ of two independent random sums of $t$
columns of $S$, restricted to only those columns with squared length at most
$2r/n$. Let the $t$ columns forming $X$ be denoted by $T$ and the $t$ columns
forming $X^{\prime}$ be denoted by $U$.

Critical to our analysis is bounding ${\bf E}[P^{j}]$ for large powers of $j$,
see Lemma 71. One can think of indexing the rows of $S^{T}S$ by $T$ and the
columns of $S^{T}S$ by $U$, where $S^{T}S$ is an $n\times n$ matrix. Let $M$
denote the resulting submatrix. The inner product of interest is then
$e_{T}^{T}Me_{U}$, where $e_{T}=\sum_{i\in T}e_{i}$ and $e_{U}=\sum_{i\in
U}e_{i}$.

Our bound in Lemma 71 is very sensitive to minor changes. Indeed, if instead
of showing ${\bf
E}[P^{j}]\leq\left(\frac{t^{2}}{r^{1/2}}\right)\cdot\left(\frac{16r}{n}\right)^{j}$,
we had shown ${\bf
E}[P^{j}]\leq\left(\frac{t^{2}}{r^{1/2}}\right)\cdot\left(\frac{16rt}{n}\right)^{j}$
or ${\bf
E}[P^{j}]\leq\left(\frac{t^{2}}{r^{1/2}}\right)\cdot\left(\frac{16r\log
n}{n}\right)^{j}$, our resulting bound for the $\chi^{2}$-divergence would be
larger than $1$. For instance, a natural approach is to instead consider
$e_{T}=\sum_{i\in T}\sigma_{i}e_{i}$ and $e_{U}=\sum_{i\in U}\sigma_{i}e_{i}$
where the $\sigma_{i}$ are independent random signs (i.e.,
$\Pr[\sigma_{i}=1]=\Pr[\sigma_{i}=-1]=1/2$), which would correspond to
redefining the distribution $\beta$ above to sample $z=x+\sum_{i\in
T}(Cn^{1/p}/t^{1/p})\sigma_{i}e_{i}$. Without further conditioning the
$\sigma_{i}$ variables, the $\chi^{2}$-divergence can be as large as
$n^{\Theta(\log(1/\delta))}$. This is because with probability roughly
$2^{-2t}$, over the choice of the $\sigma_{i}$, one has $\sum_{i\in
T}\sigma_{i}e_{i}$ and $\sum_{i\in U}\sigma_{i}e_{i}$ both being very well
aligned with the top singular vector of $M$ (if say, $S$ were a random matrix
with orthonormal rows), at which point our desired inner product is too large.
Instead, by setting all $\sigma_{i}=1$, that is, by considering
$e_{T}=\sum_{i\in T}e_{i}$ and $e_{U}=\sum_{i\in U}e_{i}$ as we do, we rule
out this possibility.

We prove Lemma 71 by expanding ${\bf E}[P^{j}]$ into a sum of products, each
having the form $\prod_{w=1}^{j}|\langle S_{a_{w}},S_{b_{w}}\rangle|$ where
the $S_{a_{w}},S_{b_{w}}$ are columns of $S$. One thing that matters in such
products is the multiplicities of duplicate columns that appear in a product.
We split the summation by what we call $y$-patterns. We can think of a
$y$-pattern as a partition of $\\{1,2,\ldots,j\\}$ into $y$ non-empty pieces.
We can also define a $z$-pattern as a partition of $\\{1,2,\ldots,j\\}$ into
$z$ non-empty pieces. We analyze the expectation for a particular pair $P,Q$,
where $P$ is a $y$-pattern and $Q$ is a $z$-pattern for some
$y,z\in\\{1,2,\ldots,j\\}$, that is, we only sum over pairs of $j$-tuples
$a_{1},\ldots,a_{j}$ and $b_{1},\ldots,b_{j}$ for which for each non-empty
piece $\\{d_{1},\ldots,d_{\ell}\\}$ in $P$, where $d_{i}\in\\{1,2,\ldots,j\\}$
for all $i$ and $\ell\leq j$, we have
$a_{d_{1}}=a_{d_{2}}=\cdots=a_{d_{\ell}}$. Similarly for each
$\\{e_{1},\ldots,e_{m}\\}$ in $Q$, where $e_{i}\in\\{1,2,\ldots,j\\}$ for all
$i$ and $m\leq j$, we have $b_{e_{1}}=b_{e_{2}}=\cdots=b_{e_{m}}$. We also
require if $d,d^{\prime}\in\\{1,2,\ldots,j\\}$ are in different pieces of $P$,
then $a_{d}\neq a_{d^{\prime}}$. Similarly, if
$e,e^{\prime}\in\\{1,2,\ldots,j\\}$ are in different pieces of $Q$, then
$b_{e}\neq b_{e^{\prime}}$. Thus, each pair of $j$-tuples is valid for exactly
one pair $P,Q$ of patterns.

The valid pairs of $j$-tuples for $P$ and $Q$ define a bipartite multi-graph
as follows. In the left partition we create a node for each non-empty piece of
$P$, and in the right partition we create a node for each non-empty piece of
$Q$. We include an edge from a node $a$ in the left to a node $b$ in the right
if $i\in a$ and $i\in b$ for some $i\in\\{1,2,\ldots,j\\}$. If there is more
than one such $i$, we include an edge with multiplicity corresponding to the
number of such $i$. This bipartite graph only depends on $P$ and $Q$. We
consider a maximum matching in this multi-graph, and we upper bound the
contribution of valid pairs for $P$ and $Q$ based on that matching. By summing
over all pairs $P,Q$, we obtain our bound on ${\bf E}[P^{j}]$.

Our $\Omega(n^{1-2/p}\epsilon^{-2}\log(1/\delta))$ bound. This bound uses the
same distributions $\alpha$ and $\beta$ as in [LW13], where an
$\Omega(n^{1-2/p}\epsilon^{-2})$ bound was shown, but we strengthen it to hold
for general $\delta$. To do so, we use an exact characterization of the
variation distance between multi-variate Gaussians with shifted mean by
relating it to the univariate case (given in the full version), and a strong
concentration of bounded Lipshitz functions with respect to the Euclidean norm
(given in the full version). These enable us to show with probability
$1-O(\delta)$, vectors sampled from $\alpha$ and $\beta$ have $\l_{p}$-norm
differing by a $1+\epsilon$ factor. By the definition of $\alpha$ and $\beta$,
we can then reduce the problem to distinguishing an isotropic Gaussian from an
isotropic Gaussian plus a small multiple of a fixed column of $S$, which
typically has small norm since $S$ has orthonormal rows. We then apply a bound
as derived above (see full version).

Our $\Omega(\epsilon^{-2}\log(1/\delta))$ bound for $1\leq p<2$. This lower
bound uses similar techniques to our lower bound of
$\Omega(n^{1-2/p}\epsilon^{-2}\log(1/\delta))$, but considers distinguishing
an isotropic Gaussian $N(0,I_{n})$ from an $N(0,(1+\epsilon)I_{n})$ random
variable. Here we set $n=\Theta(\epsilon^{-2}\log(1/\delta))$, and show the
$p$-norms of samples from the two distributions differ by a
$(1+\epsilon)$-factor with probability $1-\delta$. Using that $S$ has
orthonormal rows, the images of the two distributions under our sketching
matrix $S$ correspond to $N(0,I_{r})$ and $N(0,(1+\epsilon)I_{r})$, where $r$
is the number of rows of $S$. The result then follows by using the product
structure of Hellinger distance.

##  2 Our Lower Bounds

We first present an overview of the lower bounds in a little more detail. We
defer both our $\Omega(n^{1-2/p}\epsilon^{-2}\log(1/\delta))$ lower bound for
$p>2$ and our $\Omega(\epsilon^{-2}\log(1/\delta))$ lower bound for $1\leq
p<2$ entirely to the Appendix. Here we focus on our lower bound of
$\Omega(n^{1-2/p}\epsilon^{-2/p}(\log^{2/p}(1/\delta))\log n)$ for $p>2$. See
also Section 1 for an overview of all of our lower bounds.

We assume $\delta$-Bound4, which is that
$\log(1/\delta)\leq(n^{1-2/p}\varepsilon^{-2/p}(\log^{2/p}1/\delta)\log
n)^{1/4}n^{-c^{\prime}}$, for a sufficiently small constant $c^{\prime}>0$.
Since $p>2$ is an absolute constant, independent of $n$, this just states that
$\delta\geq 2^{-n^{c^{\prime\prime}}}$ for a sufficiently small constant
$c^{\prime\prime}>0$. There are other bounds - $\delta$-Bound1,
$\delta$-Bound2, and $\delta$-Bound3 \- see the full version in the Appendix,
but these are not assumptions but rather implied by relations between the
various parameters (e.g., otherwise the
$\Omega(n^{1-2/p}\epsilon^{-2}\log(1/\delta))$ lower bound is stronger).

Let $p$ and $q$ be probability density functions of continuous distributions.
The $\chi^{2}$-divergence from $p$ to $q$ is
$\chi^{2}(p,q)=\int_{x}\left(\frac{p(x)}{q(x)}-1\right)^{2}q(x)dx.$

###### Fact 1

([Tsy08], p.90) For any two distributions $p$ and $q$, we have
$D_{TV}(p,q)\leq\sqrt{\chi^{2}(p,q)}$.

We need a fact about the distance between a Gaussian location mixture to a
Gaussian distribution.

###### Fact 2

(p.97 of [IS03]) Let $p$ be a distribution on $\mathbb{R}^{n}$. Then
$\chi^{2}(N(0,I_{n})\ast p,N(0,I_{n}))={\bf E}[e^{\langle
X,X^{\prime}\rangle}]-1,$ where $X$ and $X^{\prime}$ are independently drawn
from $p$.

Let $T$ be a sample of $t\mathbin{\stackrel{{\scriptstyle\rm
def}}{{=}}}\log_{3}(1/\sqrt{\delta})$ coordinates $i\in[n]$ without
replacement.

Case 1: Suppose $y\sim N(0,I_{n})$, and let $\alpha^{\prime}$ be the
distribution of $y$.

Case 2: Let $z=x+\sum_{i\in
T}\frac{C^{\prime}\epsilon^{1/p}E_{n-t}}{t^{1/p}}e_{i},$ where $x\sim
N(0,I_{n})$ and $E_{n-t}={\bf E}_{x\sim N(0,I_{n-t})}[\|x\|_{p}]$. Note that
$x$ and $T$ are independent. Also, $C^{\prime}>0$ is a sufficiently large
constant. Let $\beta^{\prime}$ be the distribution of $z$.

In the full version (in the Appendix) we show that for the sketching algorithm
to be correct, $D_{TV}(\bar{\alpha^{\prime}},\bar{\beta^{\prime}})\geq
1-2\delta$, where $\bar{\alpha^{\prime}}$ is the distribution of $S\cdot y$
for $y\sim\alpha^{\prime}$ and $\bar{\beta^{\prime}}$ is the distribution of
$S\cdot z$ for $z\sim\beta^{\prime}$.

Fix an $r\times n$ matrix $S$ with orthonormal rows. Important to our proof
will be the existence of a subset $W$ of $n/2$ of the columns for which
$\|S_{i}\|^{2}\leq 2r/n$ for all $i\in W$. To see that $W$ exists, consider a
uniformly random column $S_{i}$ for $i\in[n]$. Then ${\bf
E}[\|S_{i}\|^{2}]=r/n$ and so by Markov’s inequality, at least a
$1/2$-fraction of columns $S_{i}$ satisfy $\|S_{i}\|^{2}\leq 2r/n$. We fix $W$
to be an arbitrary subset of $n/2$ of these columns.

Suppose we sample $t$ columns of $S$ without replacement, indexed by
$T\subset[n]$. Let $\mathcal{G}$ be the event that the set $T$ of sampled
columns belongs to the set $W$.

###### Lemma 3

$\Pr[\mathcal{G}]\geq\sqrt{\delta}$.

Let $\alpha_{G}=\bar{\alpha^{\prime}}\mid\mathcal{G}$ and
$\beta_{G}=\bar{\beta^{\prime}}\mid\mathcal{G}$. By the triangle inequality,
$1-2\delta\leq
D_{TV}(\bar{\alpha^{\prime}},\bar{\beta^{\prime}})\leq\Pr[\mathcal{G}]D_{TV}(\alpha_{g},\beta_{G})+1-\Pr[\mathcal{G}]\leq\frac{\sqrt{\delta}}{2}D_{TV}(\alpha_{G},\beta_{G})+1-\frac{\sqrt{\delta}}{2},$
which implies that $1-4\sqrt{\delta}\leq D_{TV}(\alpha_{G},\beta_{G})$. We can
assume $\delta$ is less than a sufficiently small positive constant, and so it
suffices to show for sketching dimension
$r=o(n^{1-2/p}\varepsilon^{-2/p}(\log^{2/p}1/\delta)\log n)$, that
$D_{TV}(\alpha_{G},\beta_{G})\leq 1/2$. By Fact 1, it suffices to show
$\chi^{2}(\alpha_{G},\beta_{G})\leq 1/4$.

Since $S$ has orthonormal rows, $\bar{\alpha^{\prime}}$ is distributed as
$N(0,I_{r})$. Note that, by definition of $\alpha$, we in fact have
$\bar{\alpha^{\prime}}=\alpha_{G}$ since conditioning on $\mathcal{G}$ does
not affect this distribution. On the other hand, $\beta_{G}$ is a Gaussian
location mixture, that is, it has the form $N(0,I_{r})\ast p$, where $p$ is
the distribution of a random variable chosen by sampling a set $T$ subject to
event $\mathcal{G}$ occurring and outputting $\sum_{i\in
T}\frac{C^{\prime}\epsilon^{1/p}E_{n-t}S_{i}}{t^{1/p}}$. We can thus apply
Fact 2 and it suffices to show for
$r=o(n^{1-2/p}\varepsilon^{-2/p}(\log^{2/p}1/\delta)\log n)$ that
$\mathbf{E}\left[e^{\frac{(C^{\prime})^{2}\epsilon^{2/p}E_{n-t}^{2}}{t^{2/p}}\langle\sum_{i\in
T}S_{i},\sum_{j\in U}S_{j}\rangle}\right]-1\leq\frac{1}{4},$ where the
expectation is over independent samples $T$ and $U$ conditioned on
$\mathcal{G}$. Note that under this conditioning $T$ and $U$ are uniformly
random subsets of $W$.

To bound the $\chi^{2}$-divergence, we define variables $x_{T,U}$, where
$x_{T,U}=\frac{(C^{\prime})^{2}\epsilon^{2/p}E_{n-t}^{2}}{t^{2/p}}\langle\sum_{i\in
T}S_{i},\allowbreak\sum_{j\in U}S_{j}\rangle$. Consider the following, where
the expectation is over independent samples $T$ and $U$ conditioned on
$\mathcal{G}$:

$\displaystyle\mathbf{E}\biggl{[}\mathrm{exp}\biggl{\\{}\frac{(C^{\prime})^{2}\epsilon^{2/p}E_{n-t}^{2}}{t^{2/p}}\langle\sum_{i\in
T}S_{i},\sum_{j\in
U}S_{j}\rangle\biggr{\\}}\biggr{]}=\mathbf{E}\bigl{[}e^{x_{T,U}}\bigr{]}=\sum_{0\leq
j<\infty}\mathbf{E}\biggl{[}\frac{x_{T,U}^{j}}{j!}\biggr{]}$
$\displaystyle=1+\sum_{j\geq
1}\frac{(C^{\prime})^{2j}\varepsilon^{2j/p}E_{n-t}^{2j}}{t^{2j/p}j!}\mathbf{E}\left[\langle\sum_{i\in
T}S_{i},\sum_{j\in U}S_{j}\rangle^{j}\right]$ $\displaystyle=1+\sum_{j\geq
1}\frac{O(1)^{2j}\varepsilon^{2j/p}n^{2j/p}}{t^{2j/p}j!}\mathbf{E}\left[\langle\sum_{i\in
T}S_{i},\sum_{j\in U}S_{j}\rangle^{j}\right].$

The final equality uses that $E_{n-t}=\Theta(n^{1/p})$ and here $O(1)^{2j}$
denotes an absolute constant raised to the $2j$-th power. We can think of $T$
as indexing a subset of rows of $S^{T}S$ and $U$ indexing a subset of columns.
Let $M$ denote the resulting $t\times t$ submatrix of $S^{T}S$. Then
$\langle\sum_{i\in T}S_{i},\sum_{j\in
U}S_{j}\rangle=\sum_{i,j\in[t]}M_{i,j}\leq\sum_{i,j\in[t]}|M_{i,j}|\mathbin{\stackrel{{\scriptstyle\rm
def}}{{=}}}P$, and we seek to understand the value of ${\bf E}[P^{j}]$ for
integers $j\geq 1$.

The following lemma is the key to the argument; its proof is described in
Section 1. The proof is based on defining $y$-patterns and looking at
matchings in an associated bipartite multi-graph.

###### Lemma 4

For integers $j\geq 1$, ${\bf
E}[P^{j}]\leq\left(\frac{t^{2}}{r^{1/2}}\right)\cdot\left(\frac{16r}{n}\right)^{j}.$

Given the previous lemma, by $\delta$-Bound4, we have
$\frac{t^{2}}{r^{1/2}}=\frac{1}{n^{\Omega(1)}}$, and therefore Lemma 4
establishes that ${\bf
E}[P^{j}]\leq\frac{1}{n^{\Omega(1)}}\cdot\left(\frac{16r}{n}\right)^{j}.$ We
thus have,

$\displaystyle\mathbf{E}\biggl{[}\mathrm{exp}\biggl{\\{}\frac{(C^{\prime})^{2}\epsilon^{2/p}E_{n-t}^{2}}{t^{2/p}}\langle\sum_{i\in
T}S_{i},\sum_{j\in U}S_{j}\rangle\biggr{\\}}\biggr{]}$
$\displaystyle=\mathbf{E}[e^{x_{T,U}}]=1+\frac{1}{n^{\Omega(1)}}\cdot\sum_{j\geq
1}\frac{O(1)^{2j}\epsilon^{2j/p}n^{2j/p}}{j!t^{2j/p}}\cdot\left(\frac{r}{n}\right)^{j}$
$\displaystyle=1+\frac{1}{n^{\Omega(1)}}\cdot\sum_{j\geq 1}\frac{(c\log
n)^{j}}{j!}$ $\displaystyle\leq 1+\frac{1}{n^{\Omega(1)}}\cdot e^{c(\log n)}$
$\displaystyle\leq 1+\frac{1}{4},$

since $c>0$ is an arbitrarily small constant independent of the constant in
the $n^{\Omega(1)}$. The proof is complete.

For $1\leq p<2$, we now show that the sketching dimension is
$\Omega(\epsilon^{-2}\log(1/\delta))$, which as discussed in Section 1,
matches known upper bounds up to a constant factor.

###### Theorem 5

The sketching dimension for $(\epsilon,\delta)$-approximating $F_{p}$ for
$1\leq p<2$ is $\Omega(\epsilon^{-2}\log(1/\delta))$.

##  3 Algorithm

As outlined earlier, the algorithm uses two level-based structures, namely,
ghss, which is similar to the ghss structure presented in [Gan15], and the
shelf structure. The shelf structure is needed only when
$\delta=n^{-\omega(1)}$, otherwise, the ghss structure suffices. The ghss has
$L+1$ levels, corresponding to $l=0,1,\ldots,L$, and the shelf structure has
$J$ shelves numbered $0,1,\ldots,J$. In particular, shelf 0 is identical to
ghss level 0.

###  3.1 Estimating $F_{p}$

_ghss structure._ Corresponding to each ghss level $l\in\\{0,1,\ldots,L-1\\}$,
a pair of CountSketch like structures named
$\textsf{HH}_{l}=\textsf{HH}(C_{l},s)$ and
$\textsf{AvgEst}_{l}=\textsf{AvgEst}(C_{l},2s)$ are kept. Both structures
$\textsf{HH}(C_{l},s)$ and $\textsf{AvgEst}(C_{l},2s)$ are very similar to
CountSketch structures and have $s$ and $2s$ independent repetitions
respectively, with $16C_{l}$ buckets in each repetition (table). Here,
$s=\Theta(\log n)$. Recall that
$C=n^{1-2/p}(\epsilon^{-2}\log(1/\delta)/\log(n)+\epsilon^{-4/p}\log^{2/p}(1/\delta))$,
$C=C_{0}=\Theta(p^{2}n^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta))$ and
$C_{l}=C_{0}\alpha^{l}$, for $l=0,1,2,\ldots,L-1$, where,
$\alpha=1-(1-2/p)\nu$ and $\nu$ is a constant (e.g., 0.01). The number of
levels is $L=\lceil\log_{2\alpha}(n/C)\rceil$. The final level $L$ of the ghss
structure uses an $\ell_{2}/\ell_{1}$ deterministic sparse-recovery algorithm
[CRT06, Don06]. We will show that the number of items that are subsampled into
level $L$ is $O(C_{L})$ with probability $1-O(\delta)$ and therefore by the
theorems proved in [CRT06, Don06], by using $O(C_{L}\log(n/C_{L}))$
measurements, all these item frequencies are recovered deterministically.
Following [Gan15], the ghss structure subsamples the stream hierarchically
using independent random hash functions
$g_{1},\ldots,g_{L}:[n]\rightarrow\\{0,1\\}$. All items are mapped to level 0;
an item is mapped to each of levels $1$ through $l$ iff
$g_{1}(i)=\ldots=g_{l}(i)=1$, where, the $g_{l}$’s are $O(\log(1/\delta)+\log
n)$-wise independent.

_HH and AvgEst structures._ The HH$(C_{l},s)$ is a CountSketch structure
[CCFC04]. The $\textsf{AvgEst}_{l}=$ AvgEst$(C_{l},2s)$ structure is similar,
except that instead of Rademacher sketches, it uses random $q$th roots of
unity sketches, where, $q\geq\Theta(\log(1/\delta)+\log n)$. At level $l$ and
for table indexed $r\in[2s]$, the corresponding hash function is
$h_{lr}:[n]\rightarrow[16C_{l}]$, and the sketch for bucket index $b$ is given
by $T_{lr}[b]=\sum_{h_{lr}(i)=b}x_{i}\omega_{lr}(i)$, where,
$\\{\omega_{lr}(i)\\}_{i\in[n]}$ is a random family of $q$th roots of unity
that is $O(\log(1/\delta)+\log n)$-wise independent. The hash functions across
the tables and distinct levels, and the seeds of the family of the random
roots of unity used by the $\textsf{AvgEst}_{l}$ structures are independent.

_Shelf structure._ The shelves, indexed from $j=0,\ldots,J$, each also consist
of an analogous pair of structures, namely, HH$(H_{j},w_{j})$ and
AvgEst$(H_{j},2w_{j})$, each of which are CountSketch-like structures. The
number of independent repetitions in the $\textsf{HH}(H_{j},w_{j})$ and
$\textsf{AvgEst}(H_{j},2w_{j})$ structures are $w_{j}$ and $2w_{j}$
respectively. The number of buckets per hash table is $O(H_{j})$ in either of
the structures. The $\textsf{HH}(H_{j},w_{j})$ is exactly a CountSketch
structure. Analogous to the $\textsf{AvgEst}_{l}$ structures of the ghss
levels, the AvgEst structures of the shelves also use sketches using $q$th
roots of unity, instead of Rademacher sketches. In particular, $H_{0}=C_{0}$
and $w_{0}=s$, ensuring that shelf 0 coincides with level 0 of ghss. Further,
$H_{J}=\Theta(n^{1-2/p}\epsilon^{-2})$ and $w_{J}=O(\log(1/\delta))$. We
therefore have two cases, namely, (1) $H_{J}=\Omega(H_{0})$, or, (2)
$H_{J}=o(H_{0})$. We consider each of the two cases next.

In case (1), $H_{J}=\Omega(H_{0})\geq cH_{0}$ for some constant $c$. The total
number of sketches used by the $J$th shelf is $(cH_{0})O(\log(1/\delta))$. Up
to constant factor, therefore, the $J$th shelf has higher width (i.e., higher
number $O(\log(1/\delta))$) of independent repetitions compared to shelf 0
(which has $O(\log n)$ independent repetitions) and has same or higher height
(i.e., number of buckets in a repetition) namely $O(H_{0})$. In this case, one
can set $J=1$, and have only two shelves. This considerably simplifies the
analysis.

The other case, namely, when, $H_{J}=o(H_{0})$ is more interesting. Here, we
let $H_{j}=H_{0}b^{j}$, for a geometric decay parameter $b<1$ and
$b=\Omega(1)$. The latter constraint $b=\Omega(1)$ is a technical constraint
whose need becomes clear from the analysis. The table widths increase
geometrically as $w_{j}=w_{0}a^{j}$, for a parameter $a>1$. The total
measurements used by the shelf structure is
$\sum_{j=0}^{J}H_{j}w_{j}=H_{0}w_{0}\sum_{j=0}^{J}(ab)^{j}=O(\max(H_{0}w_{0},H_{J}w_{J}))$,
provided, $\lvert 1-ab\rvert=\Omega(1)$, or, equivalently,
$\lvert\ln(ab)\rvert=\Omega(1)$. The entire stream $\mathcal{S}$ is provided
as input to each of the shelves $j=0,1,\ldots,J$, that is, there is no
sampling.

_Frequency groups, thresholds, estimates and samples_. Let $B=\Theta(C)$ and
$\bar{\epsilon}=(B/C)^{1/2}=\Theta(1/p)$. Let $\hat{F}_{2}$ be an estimate for
$F_{2}=\left\lVert{x}\right\rVert_{2}^{2}$ satisfying
$F_{2}\leq\hat{F}_{2}\leq(1+O(1/p))F_{2}$ with probability $1-O(\delta)$.
(Throughout the paper, it suffices to let $O(\delta)$ denote $\delta/100$. In
general, it is $c\delta$ for any constant $c$ that can be embedded into the
constants of the structures used by the algorithm). Define frequency
thresholds for ghss levels as follows: $T_{0}=(\hat{F}_{2}/B)^{1/2}$,
$T_{l}=\left(2\alpha\right)^{-l/2}T_{0}$ and $Q_{l}=T_{l}(1-\bar{\epsilon})$,
for $l\in[L-1]$. Let $Q_{L},T_{L}=0^{+}$ (i.e., $a\geq T_{L}$ iff $a>0$). For
shelf $j=0,\ldots,J$, let $E_{j}=\bar{\epsilon}^{2}H_{j}$. For shelf $j$,
define the frequency threshold $U_{j}=(\hat{F}_{2}/E_{j})^{1/2}$ and let
$U_{J+1}=\infty$. For ghss level indices $l=0,\ldots,L-1$, let $\hat{x}_{il}$
denote the estimate for $x_{i}$ obtained using $\textsf{HH}_{l}$, and
(overloading notation), for shelf indices, $j=0,\ldots,J$, let $\hat{x}_{ij}$
denote the estimate for $x_{i}$ obtained from the HH structure of shelf $j$.
For $l=L$, $\hat{x}_{iL}$ denotes the estimate returned from the
$\ell_{2}/\ell_{1}$ sparse recovery structure at level $L$.

_Discovering Items._ We say that $i$ is _discovered_ at shelf $j\in[J]$,
provided,
$(1-\bar{\epsilon})U_{j}\leq\lvert\hat{x}_{ij}\rvert\leq(1+\bar{\epsilon})U_{j+1}$
and $j\in[J]$ is the _highest_ numbered shelf with this property. We say that
$i$ is discovered at ghss level $l\in\\{0,\ldots,L\\}$, if $i$ is not
discovered at any shelf indexed $j\in[J]$, and $l$ is the _smallest_ level
such that $T_{l}(1-\bar{\epsilon})<\hat{x}_{il}\leq
T_{l-1}(1+\bar{\epsilon})$. If $i$ is discovered at shelf $j$, then, $i$ is
included in the shelf sample $\bar{S}_{j}$. If $i$ is discovered at level
$l\in[0,1,\ldots,L]$ and $\lvert\hat{x}_{il}\rvert\geq T_{l}$, then, $i$ is
included in the level sample $\bar{G}_{l}$. If $i$ is discovered at level $l$
and $T_{l}(1-\bar{\epsilon})<\lvert\hat{x}_{il}\rvert<T_{l}$ then, $i$ is
placed in $\bar{G}_{l+1}$ iff the random toss of an unbiased coin $K_{i}$
lands heads; and upon tails, $i$is not placed in any sample group. The ghss
level sampling scheme is similar to [Gan15].

_The averaged estimator and nocollision._ For each item $i$ included in a
group sample $\bar{G}_{l}$ or shelf sample $\bar{S}_{j}$, an estimate $X_{i}$
for $\lvert x_{i}\rvert$ is obtained using the corresponding AvgEst structure
of that level or shelf, provided the event nocollision$(i)$ succeeds. If $i$
is sampled into $\bar{G}_{l}$, then nocollision$(i)$ holds if there is a set
$R_{l}(i)\subset[2s]$ of table indices of the AvgEstl structure such that for
each $r\in R_{l}(i)$, $i$ does not collide under the hash function $h_{lr}$
with any of the items that are the top-$C_{l}$ absolute estimated frequencies
using $\textsf{HH}_{l}$. An analogous definition holds if $i$ is included in
the $j$th shelf sample. Assuming nocollision$(i)$ holds, the estimate $X_{i}$
is defined as the average of the estimates obtained from the tables whose
indices are in the set $R_{l}(i)$ ( resp. $R_{j}(i)$ if $i$ was discovered in
shelf $j$), that is,

$X_{i}=(1/\lvert R(i)\rvert)\sum_{r\in
R(i)}T_{r}[h_{r}(i)]\cdot\overline{\omega_{r}(i)}\cdot\textrm{sgn}(\hat{x_{i}})\enspace.$

Further, we check whether $(1-\bar{\epsilon})T_{l}\leq
X_{i}\leq(1+\bar{\epsilon})T_{l-1}$ (resp. $(1-\bar{\epsilon})U_{j}\leq
X_{i}\leq(1+\bar{\epsilon})U_{j+1}$, if $i$ is in shelf $j$ sample),
otherwise, $i$ is dropped from the sample.

_Estimating $F_{p}$._ The estimate for the $p$th frequency moment,
$\hat{F}_{p}$, is the sum of the contribution from the shelf samples
$\bar{S}_{j},j\in[J]$, and the contribution from the sample groups
$\bar{G}_{l}$, $l=0,\ldots,L$. For an item $i\in\bar{G}_{l}$, let $l_{d}(i)$
be the level at which an item $i$ is discovered. Define

$\displaystyle\hat{F}_{p}^{\textsc{shelf}}$
$\displaystyle=\sum_{j=1}^{J}\sum\left\\{X_{i}^{p}\mid
i\in\bar{S}_{j},(1-\bar{\epsilon})U_{j}\leq\lvert
X_{j}\rvert\leq(1+\bar{\epsilon})U_{j+1}\right\\},\text{ and }$
$\displaystyle\hat{F}_{p}^{\textsc{ghss}}$
$\displaystyle=\sum_{l=0}^{L}2^{L}\sum\left\\{X_{i}^{p}\mid
i\in\bar{G}_{l},l_{d}(i)<L,(1-\bar{\epsilon})T_{l_{d}}\leq
X_{i}<(1+\bar{\epsilon})T_{l_{d}-1}\right\\}+2^{L}\sum_{l_{d}(i)=L}\lvert\hat{x}_{i}\rvert^{p}.$

The final estimate is
$\hat{F}_{p}=\hat{F}_{p}^{\textsc{shelf}}+\hat{F}_{p}^{\textsc{ghss}}$.

###  3.2 Analysis

_Notation._ Let $F_{2}^{\text{res}}\left({k}\right)$ be the sum of the squares
of all coordinates except the top-$k$ absolute coordinates. That is, suppose
the items are placed in decreasing order as per their absolute value of
$\lvert x_{i}\rvert$, that is, let $t$ is an ordering (permutation) of the
coordinates $[n]$ such that $\lvert x_{t_{1}}\rvert\geq\lvert
x_{t,2}\rvert\geq\ldots\lvert x_{t_{n}}\rvert$, with ties broken arbitrarily.
Then, for $0\leq k\leq n$, define
$F_{2}^{\text{res}}\left({k}\right)=\sum_{j=k+1}^{n}\lvert
x_{t_{j}}\rvert^{2}\enspace.$

For a ghss level $l\in[L]$, $F_{2}^{\text{res}}\left({l,k}\right)$ is the
random $k$-residual second moment of the frequency vector in the sampled
substream $\mathcal{S}_{l}$. Define the following events.

$\displaystyle(1)$ $\displaystyle~{}\textsc{goodf}_{2}\equiv
F_{2}\leq\hat{F}_{2}\leq(1+0.001/(2p))F_{2},$ $\displaystyle(2)$
$\displaystyle~{}\textsc{smallres}_{l}\equiv
F_{2}^{\text{res}}\left({2C_{l},l}\right)\leq
1.5F_{2}^{\text{res}}\left({\lceil(2\alpha)^{l}C\rceil}\right)/2^{l-1},~{}~{}l=0,1,\ldots,L,$
$\displaystyle(3)$ $\displaystyle~{}\textsc{smallres}\equiv\forall
l\in\\{0,1,\ldots,L\\}~{}\textsc{smallres}_{l},$ $\displaystyle(4)$
$\displaystyle~{}\textsc{goodlastlevel}~{}\equiv(\hat{f}_{iL}=f_{i})\text{ and
}\forall i\not\in\mathcal{S}_{L},(\hat{f}_{iL}=0)\enspace.$

We condition the analysis on the “good event”
$\mathcal{G}\equiv\textsc{goodf}_{2}\wedge\textsc{smallres}\wedge\textsc{goodlastlevel}$,
that we show holds with probability $1-\min(O(\delta),n^{-\Omega(1)})$.

###### Lemma 6

$\mathcal{G}$ holds with probability $1-\min(O(\delta),n^{-\Omega(1)})$.

The range of item frequencies is subdivided into frequency groups , so that
each item belongs to exactly one shelf frequency group or to exactly one ghss
frequency group. The frequency group corresponding to the shelf $j$ is
$[U_{j},U_{j+1})$, for $j=1,\ldots,J$, where, $U_{J+1}=\infty$ and
$U_{0}=T_{0}$. The frequency group corresponding to level $l$ of ghss is
$[T_{l},T_{l-1})$, where, $T_{L}=0$ and $T_{-1}=U_{1}$. Let $S_{j}$ (resp.
$G_{l})$ denote the set of items whose frequency belongs to the frequency
group corresponding to shelf $j$ (resp. group $l$). A few other events are
used in the analysis. If $i\in G_{l}$, then,
$\text{Pr}\left[\textsc{nocollision}(i)\right]\geq
1-\textrm{exp}\left\\{{-\Theta(\log n)}\right\\}$ as shown in [Gan15] (Lemma
30). If $i\in S_{j}$, $\text{Pr}\left[\textsc{nocollision}(i)\right]\geq
1-\textrm{exp}\left\\{{-\Theta(w_{j})}\right\\}$. We condition some parts of
the analysis on the following additional events.

$\begin{array}[]{ll}(5)&~{}\textsc{goodest}(i)\equiv\forall
l\in[0,\ldots,L],i\in\mathcal{S}_{l}\Rightarrow\lvert\hat{x}_{il}-x_{i}\rvert\leq\bigl{(}F_{2}^{\text{res}}\left({2C_{l},l}\right)/{C_{l}}\bigr{)}^{1/2}\\\
(6)&~{}\textsc{accuest}(i)\equiv\forall
l\in[0,\ldots,L],i\in\mathcal{S}_{l}\Rightarrow\lvert\hat{x}_{il}-x_{i}\rvert\leq\bigl{(}F_{2}^{\text{res}}\left({(2\alpha)^{l}C}\right)/(2(2\alpha)^{l}C)\bigr{)}^{1/2}\enspace.\end{array}$

As shown in [Gan15], (a) $\textsc{goodest}(i)$ and $\textsc{accuest}(i)$ each
hold with probability $1-n^{-\Omega(1)}$, and, (b)
$\textsc{goodest}(i)\wedge\textsc{smallres}$ imply the event accuest$(i)$. For
an item $i$ that is discovered at some shelf $j$, the event
$\textsc{goodest}(i)$ is the same as the event $\textsc{accuest}(i)$ and is
defined as
$\lvert\hat{x}_{ij}-x_{i}\rvert\leq\bigl{(}F_{2}^{\text{res}}\left({U_{j}}\right)/U_{j}\bigr{)}^{1/2}$
and holds with probability $1-\textrm{exp}\left\\{{-\Theta(w_{j})}\right\\}$.

Lemma 7 extends the approximate 2-wise independence property of the sampling
scheme of [Gan15] to an approximate $d$-wise independence property.

###### Lemma 7

Let $I=\\{i_{1},\ldots,i_{d}\\}\subset[n]$ and $1\leq h\leq d$. Let
$\textsc{accuest}(\\{i_{1},\ldots,i_{h}\\})\equiv$
$\bigwedge_{k=1}^{h}\textsc{accuest}(i_{k})$. Then, assuming $d$-wise
independence of the hash functions,

$\sum_{\begin{subarray}{c}l_{j}=0,1,\ldots,L,\\\ \forall
j=1,2,\ldots,h\end{subarray}}2^{l_{1}+l_{2}+\ldots+l_{h}}\text{Pr}\left[\bigwedge_{j=1}^{h}i_{j}\in\bar{G}_{l_{j}}\bigl{|}\bigwedge_{j=h+1}^{d}i_{j}\in\mathcal{S}_{l_{j}},\mathcal{G},\textsc{accuest}(\\{i_{1},\ldots,i_{h}\\})\right]\in\\\
\prod_{j=1}^{h}\left(1\pm 2^{\mathsf{level}(i_{j})+1}n^{-c}\right).$

Lemma 9 bounds $\lvert X_{i}-\mathbf{E}\left[X_{i}\right]\rvert$ using the
$2d$th moment method. It uses Lemma 8 as a key component.

###### Lemma 8

Let $Z=\sum_{j=1}^{t}a_{j}\omega(j)\chi(j)$, where,
$\\{\omega(j)\\}_{j=1}^{t}$ is a family of random and $2d$-wise independent
family roots of the equation $x^{q}=1$, $q>2d$ and integral. Let
$\\{\chi(j)\\}$ be a $2d$-wise independent family of indicator variables such
that $\text{Pr}\left[\chi(j)=1\right]=1/C$ and is independent of the
$\omega_{j}$’s. If $\left\lVert{a}\right\rVert_{2}^{2}\geq
4d\left\lVert{a}\right\rVert_{\infty}^{2}C$, then,
$\mathbf{E}\left[(Z\bar{Z})^{d}\right]\leq(2)\left(\frac{d\left\lVert{a}\right\rVert_{2}^{2}}{C}\right)^{d}\enspace.$

###### Lemma 9

Suppose $d\leq O(\log n)$ and even and let $s\geq 300\log(n)$. Then we have
that $\textrm{Pr}\bigl{\\{}\lvert X_{i}-\lvert
x_{i}\rvert\rvert>\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(s/9)C}\right)^{1/2}\mid\textsc{nocollision},\textsc{goodest}\bigr{\\}}<2^{-2d+1}\enspace.$

The use of $q$th roots of unity for the sketches used in the AvgEst structures
allows us nearly unbiased estimators for $X_{i}^{p}$. This was first observed
in [KNPW10].

######  Lemma 10 ([KNPW10])

$\bigl{\lvert}\mathbf{E}\left[X_{i}^{p}\right]-\lvert
x_{i}\rvert^{p}\mid\mathcal{G},\textsc{goodest},\textsc{nocollision}\bigr{\rvert}\leq\lvert
x_{i}\rvert^{p}n^{-\Omega(1)}$.

For $i\in[n]$, let $x_{li}$ be an indicator variable that is 1 iff
$i\in\mathcal{S}_{l}$. Let $X_{i}$ denote $\lvert\hat{x}_{i}\rvert$ when
$l_{d}(i)=L$ and otherwise, let its meaning be unchanged. Let $z_{il}$ be an
indicator variable that is 1 if $i\in\bar{G}_{l}$ and is 0 otherwise. Define

$\hat{F}_{p}=\sum_{i\in[n]}Y_{i},~{}~{}~{}~{}~{}\text{ where,
}Y_{i}=\sum_{l^{\prime}=0}^{L}2^{l^{\prime}}z_{il^{\prime}}X_{i}^{p}\enspace.$

Let $\mathcal{H}=\mathcal{G}\cap\textsc{nocollision}\cap\textsc{goodest}$ and
$G^{\prime}\subset[n]$ be the set of items
$G^{\prime}=\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$.

###### Lemma 11

Let $B\geq O(n^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta)))$. For integral
$0\leq d_{1},d_{2}\leq\lceil\log(1/\delta)\rceil$, we have,
$\mathbf{E}\bigl{[}\left(\sum_{i\in
G^{\prime}}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
G^{\prime}}(\overline{Y_{i}}-\mathbf{E}\left[\overline{Y_{i}}\mid\mathcal{H}\right])\right)^{d_{2}}\big{|}\mathcal{H}\bigr{]}\leq\left(\frac{\epsilon
F_{p}}{20}\right)^{d_{1}+d_{2}}\enspace.$

###  3.3 Analysis for the case $\delta\geq n^{-O(1)}$

For the case $\delta=n^{-O(1)}$, the shelf structure is not needed. Redefine
the group $G_{0}$ to correspond to the frequency range $[T_{0},\infty]$. The
lemmas in this section assume that the family $\\{\omega_{lr}(i)\\}_{i\in[n]}$
are $O(\log(1/\delta)+\log(n))$-wise independent, and independent across $l,r$
and all hash functions are also $O(\log(1/\delta)+\log(n))$-wise independent.

###### Lemma 12

Let $1\leq e,g\leq\lceil\log(1/\delta)\rceil,l\in\text{mid}(G_{0})$ and
$\lvert
x_{l}\rvert\geq\bigl{(}\frac{F_{2}^{\text{res}}\left({C}\right)}{C}\bigr{)}^{1/2}$.
Then,
$\mathbf{E}\left[\left(Y_{l}-\mathbf{E}\left[Y_{l}\mid\mathcal{H}\right]\right)^{e}\left(\overline{Y_{l}}-\mathbf{E}\left[\overline{Y_{l}}\mid
H\right]\right)^{g}\mid\mathcal{H}\right]$ is real and is at most
$\left(\frac{a\lvert
x_{l}\rvert^{2p-2}F_{2}^{\text{res}}\left({C}\right)}{\rho
C}\right)^{(e+g)/2}$ for some constant $a$. Further,
$\bigl{\lvert}\mathbf{E}\left[\left(Y_{l}-\mathbf{E}\left[Y_{l}\mid\mathcal{H}\right]\right)^{e}\right]\mid\mathcal{H}\bigr{\rvert}\leq\lvert
x_{l}\rvert^{pe}n^{-\Omega(e)}\enspace.$

The calculation of the $d$th central moment for the contribution to
$\hat{F}_{p}$ from the items in $\text{mid}(G_{0})$ requires an upper bound on
the following combinatorial sums.

$\displaystyle Q(S_{1},S_{2})$
$\displaystyle=\sum_{q=1}^{\min(S_{1},S_{2})}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S_{1}\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=S_{2}\\\
g_{j}^{\prime}s\geq
1\end{subarray}}\binom{S_{1}}{e_{1},\ldots,e_{q}}\binom{S_{2}}{g_{1},\ldots,g_{q}}$
$\displaystyle=\sum_{\\{i_{1},\ldots,i_{q}\\}}\prod_{r=1}^{q}\lvert
x_{i_{r}}\rvert^{(p-1)(e_{r}+g_{r})}\prod_{r=1}^{q}(e_{r}+g_{r})^{(e_{r}+g_{r})/2},\text{
and }$ (1) $\displaystyle R(S)$ $\displaystyle=\sum_{q=1}^{\lfloor
S/2\rfloor}\sum_{h_{1}+\ldots+h_{q}=S,h_{j}^{\prime}s\geq
2}\binom{S}{h_{1},\ldots,h_{q}}\sum_{\\{i_{1},\ldots,i_{q}\\}}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(p-1)h_{r}}\prod_{r\in[q]}h_{r}^{h_{r}/2}.$ (2)

###### Lemma 13

$Q(S_{1},S_{2})\leq
R(S_{1}+S_{2})\leq\left(16e(S_{1}+S_{2})F_{2p-2}\right)^{(S_{1}+S_{2})/2}$.

###### Lemma 14

Let $C\geq O(n^{1-2/p}/\log(n))\epsilon^{-2}\log(1/\delta))$. Then, for $0\leq
d_{1},d_{2}\leq\log(1/\delta)$, the following expectation is real and is
bounded above as follows.

$\displaystyle\mathbf{E}\left[\biggl{(}\sum_{i\in\text{mid}(G_{0})}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\biggr{)}^{d_{1}}\biggl{(}\sum_{i\in\text{mid}(G_{0})}(\overline{Y_{i}}-\mathbf{E}\left[\overline{Y_{i}}\mid
H\right])\biggr{)}^{d_{2}}\mid\mathcal{H}\right]\leq\left(\frac{\epsilon
F_{p}}{10}\right)^{d_{1}+d_{2}}.$

###### Lemma 15

Let $C\geq
Kn^{1-2/p}\epsilon^{-2}\log(1/\delta)/\log(n)+Ln^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta)$,
where, $K,L$ are constants. Then, for $d=\lceil\log(1/\delta)\rceil$, the
following expectation is real and is bounded as follows.

$\displaystyle\mathbf{E}\left[\bigl{(}\sum_{i\in[n]}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\bigr{)}^{d}\bigl{(}\sum_{i\in[n]}(\overline{Y_{i}}-\mathbf{E}\left[\overline{Y_{i}}\mid\mathcal{H}\right])\bigr{)}^{d}\mid\mathcal{H}\right]\leq\bigl{(}\frac{\epsilon
F_{p}}{5}\bigr{)}^{2d}.$

It follows that
$\text{Pr}\left[\bigl{\lvert}\hat{F}_{p}-F_{p}\bigr{\rvert}\geq(\epsilon/2)F_{p}\right]\leq\delta$.

Since, $\mathcal{H}$ holds with probability $1-2^{-\Theta(s)}=1-1/n^{-c}$, for
any constant $c$ by choosing $s=\Theta(\log n)$ appropriately, we have the
following theorem.

###### Theorem 16

For each $0<\epsilon<1$ and $7/8\geq\delta\geq n^{-c}$, for any constant $c$,
there is a sketching algorithm that $(\epsilon,\delta)$-approximates $F_{p}$
with sketching dimension
$O\bigl{(}n^{1-2/p}\bigl{(}\epsilon^{-2}\log(1/\delta)+\epsilon^{-4/p}\log^{2/p}(1/\delta)\allowbreak\log
n\bigr{)}\bigr{)}$ and update time (per stream update) $O((\log
n)\log(1/\delta)))$.

###  3.4 Analysis for the case $\delta=n^{-\omega(1)}$

We now extend the analysis for failure probability $\delta$ smaller than
$n^{-\Theta(1)}$ and up to $\delta=2^{-n^{\Omega(1)}}$. For the ghss
structure, nocollision and goodest may hold only with probability
$1-n^{-\Theta(1)}$. We first show that the number of items that fail to
satisfy nocollision or goodest is at most $O(\log(1/\delta)/\log n)$ with
probability $1-O(\delta)$. The following lemmas assume the parameter sizes for
$B,C,C_{l},H_{J}$ and $H_{j}$ as described earlier.

###### Lemma 17

With probability $1-O(\delta)$, the number of elements for which goodest or
nocollision fails is at most $O(\log(1/\delta))/(\log n)$.

Thus, it is possible that legitimate items are not discovered, or are dropped
due to collisions, or mistakenly classified and their contribution added to
samples. Let $\text{Error}^{\textsc{ghss}}$ denote the total contribution of
such items to $\hat{F}_{p}^{\textsc{ghss}}$ and let
$\text{Error}^{\textsc{shelf}}$ denote the error arising in the estimate of
$\hat{F}_{p}^{\textsc{shelf}}$ due to analogous errors. As described earlier,
we mainly emphasize the more interesting and complicated case when
$H_{J}=o(H_{0})$ (otherwise, $J=1$).

###### Lemma 18

$\text{Error}^{\textsc{ghss}}\leq O(\epsilon^{2}F_{p}/\log n)$ and
$\text{Error}^{\textsc{shelf}}\leq O(\max(\epsilon^{2}F_{p}/(\log
n),O(\epsilon^{p}F_{p})))$, each with probability $1-\delta/n^{\Omega(1)}$.

We first prove a refinement of Lemma 12.

###### Lemma 19

[Refinement of Lemma 12.] Let $1\leq e,g\leq\lceil\log(1/\delta)\rceil$, $l\in
S_{j}$ and $\log(1/\delta)=\omega(\log n)$. Assume that $\textsc{accuest}(l)$
holds and $H_{j}\geq\Omega(p^{2}E_{J})$ and $\lvert
x_{l}\rvert\geq(F_{2}/E_{j})^{1/2}$. Then the following expectation is real
and is bounded above as follows.

$\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\mid\mathcal{H}\right]\leq c^{h}\lvert
x_{l}\rvert^{-h}\biggl{(}\frac{F_{2}}{H_{j}}\biggr{)}^{h/2}\bigl{(}\min\bigl{(}h/w_{j},1\bigr{)}\bigr{)}^{h/2}$

where, $h=e+g$ and $c$ is an absolute constant. Therefore

$\displaystyle\mathbf{E}\left[\left(Y_{l}-\mathbf{E}\left[Y_{l}\right]\right)^{e}\left(\overline{Y_{l}}-\mathbf{E}\left[\overline{Y_{l}}\right]\right)^{g}\right]\leq
c^{h}\lvert
x_{l}\rvert^{(p-1)h}\left(\frac{F_{2}}{H_{j}}\right)^{h/2}\left(\min\left(h/w_{j},1\right)\right)^{h/2}\enspace.$

Lemma 20 considers the $2d$th central moment of the contribution to
$\hat{F}_{p}^{\textsc{shelf}}$ from all but the outermost shelf, and from the
set of outermost shelf items denoted $S_{J}$, separately. Let
$S^{\prime}=S_{1}\cup\ldots\cup S_{J-1}$.

###### Lemma 20

Let $0\leq d_{1},d_{2}\leq\lceil\log(1/\delta)\rceil$ and integral and
$c_{1},c_{2}$ be constants. Then,

$\displaystyle\mathbf{E}\left[\bigl{(}\sum_{i\in
S^{\prime}}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\bigr{)}^{d_{1}}\bigl{(}\sum_{i\in
S^{\prime}}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\bigr{)}^{d_{2}}\mid\mathcal{H}\right]\leq\left(c_{1}\epsilon
F_{p}\right)^{d_{1}+d_{2}}.$ $\displaystyle\mathbf{E}\left[\bigl{(}\sum_{i\in
S_{J}}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\bigr{)}^{d_{1}}\bigl{(}\sum_{i\in
S_{J}}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\bigr{)}^{d_{2}}\mid\mathcal{H}\right]\leq\left(c_{2}\epsilon
F_{p}\right)^{d_{1}+d_{2}}.$

Combining Lemmas 11, 14 and 20 with Lemma 18, we obtain the following.

###### Lemma 21

$\exists$ constant $c$ s.t. for $1\leq d\leq\lceil\log(1/\delta)\rceil$, the
following holds.

$\mathbf{E}\left[\bigl{(}\sum_{i\in[n]}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\bigr{)}^{d}\bigl{(}\sum_{i\in[n]}(\overline{Y_{i}}-\mathbf{E}\left[\overline{Y_{i}}\mid\mathcal{H}\right])\bigr{)}^{d}\mid\mathcal{H}\right]\leq(c\epsilon
F_{p})^{2d}\enspace.$

Hence, $\text{Pr}\left[\bigl{\lvert}\hat{F}_{p}-F_{p}\bigr{\rvert}\leq\epsilon
F_{p})\right]<\delta\enspace.$

###### Theorem 22

For each $0<\epsilon<1$ and $7/8\geq\delta\geq 2^{-n^{\Omega(1)}}$, there is a
sketching algorithm that $(\epsilon,\delta)$-approximates $F_{p}$ with
sketching dimension
$O\bigl{(}n^{1-2/p}\bigl{(}\epsilon^{-2}\log(1/\delta)+\epsilon^{-4/p}\log^{2/p}(1/\delta)\log
n\bigr{)}\bigr{)}$ and update time (per stream update) $O((\log
n)\log(1/\delta))$.

## References

  * [AKLY16] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev.  Maximum matchings in dynamic graph streams and the simultaneous communication model.  In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1345–1364, 2016.
  * [AKO10] Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak.  Streaming algorithms from precision sampling.  CoRR, abs/1011.1263, 2010.
  * [AMS99] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  JCSS, 58(1):137–147, 1999.
  * [And] Alexandr Andoni.  High frequency moment via max stability.  Available at http://web.mit.edu/andoni/www/papers/fkStable.pdf.
  * [ANPW13] Alexandr Andoni, Huy L. Nguyen, Yury Polyanskiy, and Yihong Wu.  “Tight Lower Bound for Linear Sketches of Moments”.  In Proceedings of International Conference on Automata, Languages and Programming, (ICALP), July 2013.  Version published as arXiv:1306.6295, June 2013.
  * [BGKS06] Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha.  Simpler algorithm for estimating frequency moments of data streams.  In SODA, pages 708–713, 2006.
  * [BO10] Vladimir Braverman and Rafail Ostrovsky.  Recursive sketching for frequency moments.  CoRR, abs/1011.2571, 2010.
  * [BYJKS02] Z. Bar-Yossef, T.S. Jayram, R. Kumar, and D. Sivakumar.  “An information statistics approach to data stream and communication complexity”.  In Proceedings of ACM Symposium on Theory of Computing STOC, pages 209–218, 2002.
  * [CCFC04] Moses Charikar, Kevin Chen, and Martin Farach-Colton.  “Finding frequent items in data streams”.  Theoretical Computer Science, 312(1):3–15, 2004.  Preliminary version appeared in Proceedings of ICALP 2002, pages 693-703.
  * [CK04] Don Coppersmith and Ravi Kumar.  An improved data stream algorithm for frequency moments.  In SODA, 2004.
  * [CKS03] Amit Chakrabarti, Subhash Khot, and Xiaodong Sun.  Near-optimal lower bounds on the multi-party communication complexity of set disjointness.  In CCC, pages 107–117, 2003.
  * [CRT06] Emmanuel Candès, Justin Romberg, and Terence Tao.  “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”.  IEEE Trans. Inf. Theory, 52(2):489–509, February 2006.
  * [Don06] David L. Donoho.  “Compressed Sensing”.  IEEE Trans. Inf. Theory, 52(4):1289–1306, April 2006.
  * [Due10] Lutz Duembgen.  “Bounding Standard Gaussian Tail Probabilities”.  ArXiv e-prints, 1012.2063, 2010.
  * [Gan04a] Sumit Ganguly.  Estimating frequency moments of data streams using random linear combinations.  In RANDOM, 2004.
  * [Gan04b] Sumit Ganguly.  A hybrid algorithm for estimating frequency moments of data streams, 2004\.  Manuscript.
  * [Gan11] Sumit Ganguly.  Polynomial estimators for high frequency moments.  CoRR, abs/1104.4552, 2011.
  * [Gan12] Sumit Ganguly.  “Precision vs. Confidence Tradeoffs for $\ell_{2}$-Based Frequency Estimation in Data Streams”.  In Proceedings of International Symposium on Algorithms, Automata and Computation (ISAAC), LNCS Vol. 7676, pages 64–74, 2012.
  * [Gan15] Sumit Ganguly.  “Taylor Polynomial Estimator for Estimating Frequency Moments”.  In Proceedings of International Conference on Automata, Languages and Programming, (ICALP), 2015.  Full version in arXiv:1506.01442.
  * [HW13] Moritz Hardt and David P. Woodruff.  How robust are linear sketches to adaptive inputs?  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 121–130, 2013.
  * [Ind00] Piotr Indyk.  “Stable Distributions, Pseudo Random Generators, Embeddings and Data Stream Computation”.  In Proceedings of IEEE FOCS, pages 189–197, 2000.
  * [IS03] Y. I. Ingster and L.A. Suslina.  “Non-parametric goodness-of-fit testing under Gaussian models”, volume 169 of Lecture Notes in Statistics.  Springer-Verlag, 2003.
  * [IW05] P. Indyk and D. Woodruff.  Optimal approximations of the frequency moments of data streams.  In STOC. ACM, 2005.
  * [KMN11] Daniel M. Kane, Raghu Meka, and Jelani Nelson.  Almost optimal explicit johnson-lindenstrauss families.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011\. Proceedings, pages 628–639, 2011.
  * [KMV10] Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant.  Efficiently learning mixtures of two gaussians.  In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 553–562, 2010.
  * [KNPW10] Daniel Kane, Jelani Nelson, Ely Porat, and David Woodruff.  “Fast Moment Estimation in Data Streams in Optimal Space”.  In Proceedings of 2011 ACM Symposium on Theory of Computing, version arXiv:1007.4191v1 July, 2010.
  * [KNPW11a] Daniel Kane, Jelani Nelson, Ely Porat, and David Woodruff.  “Fast Moment Estimation in Data Streams in Optimal Space”.  In Proceedings of 2011 ACM Symposium on Theory of Computing, version arXiv:1007.4191v1 July, 2011.
  * [KNPW11b] Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff.  Fast moment estimation in data streams in optimal space.  In STOC, pages 745–754, 2011.
  * [KNW10a] Daniel M. Kane, Jelani Nelson, and David Woodruff.  “An Optimal Algorithm for the Distinct Elements Problem”.  In Proceedings of ACM International Symposium on Principles of Database Systems (PODS), pages 41–52, 2010.
  * [KNW10b] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  “On the Exact Space Complexity of Sketching and Streaming Small Norms”.  In Proceedings of ACM Symposium on Discrete Algorithms (SODA), 2010\.
  * [Kon15] Christian Konrad.  Maximum matching in turnstile streams.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 840–852, 2015.
  * [LNW14] Yi Li, Huy L. Nguyen, and David P. Woodruff.  On sketching matrix norms and the top singular vector.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1562–1581, 2014.
  * [LW13] Yi Li and David Woodruff.  “A Tight Lower Bound for High Frequency Moment Estimation with Small Error”.  In Proceedings of International Workshop on Randomization and Computation (RANDOM), 2013.
  * [MW10] Morteza Monemizadeh and David P. Woodruff.  $1$-pass relative-error $l_{p}$-sampling with applications.  In SODA, 2010.
  * [Pol] D. Pollard.  “Chapter 3: Total Variation Distance Between Measures”.  http://www.stat.yale.edu/~pollard/Courses/607.spring05/handouts/Totalvar.pdf.
  * [PW12] Eric Price and David P. Woodruff.  Applications of the shannon-hartley theorem to data streams and sparse recovery.  In ISIT, 2012.
  * [SSS93] J. Schmidt, A. Siegel, and A. Srinivasan.  “Chernoff-Hoeffding Bounds with Applications for Limited Independence”.  In Proceedings of ACM Symposium on Discrete Algorithms (SODA), pages 331–340, 1993.
  * [Tsy08] Alexandre B. Tsybakov.  “Introduction to Nonparametric Estimation”.  Springer, 1 edition, 2008.
  * [Wai] M. Wainwright.  “Chapter 2: Basic Tail and Concentration Bounds”.  http://www.stat.berkeley.edu/~mjwain/stat210b/Chap2_TailBounds_Jan22_2015.pdf.
  * [Woo14] David P. Woodruff.  “Sketching as a Tool for Numerical Linear Algebra”.  Foundations and Trends in Theoretical Computer Science 10:1-2, Now Publications, 2014.
  * [WW15] Omri Weinstein and David P. Woodruff.  The simultaneous communication of disjointness with applications to data streams.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 1082–1093, 2015.

##  Appendix A Proofs for our Algorithm

We first present some details of the ghss structure that were originally
presented in summary form in Section 3.

_ghss sampling._ For the ghss structure, the input stream $\mathcal{S}$ is
sub-sampled hierarchically to produce random sub-streams
$\mathcal{S}_{0},\mathcal{S}_{1},\ldots,\mathcal{S}_{L}$, corresponding to
each of the levels $0,\ldots,L$. The stream $\mathcal{S}_{0}$ is the entire
input stream. For each $l=1,\ldots,L$, $\mathcal{S}_{l}$ is obtained by
sampling each item $i$ appearing in $\mathcal{S}_{l-1}$ with probability
$1/2$. If $i$ is sampled, then all its records $(i,v)$ are included in
$\mathcal{S}_{1}$, otherwise none of its records are included. The sampling
uses independently chosen random hash functions $g_{1},g_{2},\ldots,g_{L}$
each mapping $[n]\rightarrow\\{0,1\\}$. $i$ is included in $\mathcal{S}_{l}$
iff $g_{1}(i)=1,g_{2}(i)=1,\ldots,g_{l}(i)=1$. The $g_{l}$’s are chosen from a
$O(\log(1/\delta)+\log n)$-wise independent hash family.

Let $C=C_{0}=\Theta(p^{2}n^{1-2/p}\epsilon^{4/p}\log^{2/p}(1/\delta))$ be the
height of CountSketch and AvgEst structures at level 0 of the ghss structure.
The height of the CountSketch and AvgEst structures at level $l$ of the ghss
structure is defined as

$C_{l}=\alpha^{l}C_{0},~{}~{}~{}l=0,1,\ldots,L\enspace.$

Let $\bar{\epsilon}=1/(54p)$ be a constant. Let $B$ be another parameter
closely related to $C$ as follows.

$B=\bar{\epsilon}^{2}C,\text{ and let }B_{l}=\bar{\epsilon}^{2}C_{l},\text{
for }l=0,1,\ldots,L\enspace.$

The level-wise frequency thresholds are defined as follows.

$\displaystyle T_{0}$
$\displaystyle=\left(\frac{\hat{F}_{2}}{B}\right)^{1/2},T_{l}=\left(\frac{1}{(2\alpha)}\right)^{1/2}T_{0}=\left(\frac{\hat{F}_{2}}{2^{l}B_{l}}\right)^{1/2}l=0,1,\ldots,L-1\enspace.$

$T_{L}$ is defined as $0^{+}$, that is, $a>T_{L}$ iff $a>0$. Another threshold
$Q_{l}$ is used for defining when an item is discovered at level $l$, and is
defined as follows.

$\displaystyle Q_{l}=T_{l}(1-\bar{\epsilon})~{}~{}l=0,1,\ldots,L-1\enspace.$

Similarly, $Q_{L}$ is defined as $0^{+}$.

The ghss level groups are sets of items identified with frequency ranges and
essentially follows the scheme of [Gan15]. The group $G_{l}$ consists of all
items in the frequency range $[T_{l},T_{l-1})$, for $l=0,1,\ldots,L-1$. That
is, However, the group $G_{0}$ consists of the frequency range
$[T_{0},U_{1})$, that is, $T_{-1}$ is identified with $U_{1}$ of the shelf
structure. The group $G_{L}$ is identified with the frequency range
$(T_{0},T_{L-1})$. The ratio $T_{l-1}/T_{l}=(2\alpha)^{1/2}$, for
$l=0,1,\ldots,L-1$. More precisely, we have the following group definitions.

$\displaystyle G_{l}$ $\displaystyle=\\{i:T_{l}\leq\lvert
x_{i}\rvert<T_{l-1}\\},~{}~{}l=0,1,\ldots,L-1$ $\displaystyle G_{L}$
$\displaystyle=\\{i:0<\lvert x_{i}\rvert<T_{L-1}\\}$

where, for the definition of the group $G_{0}$ it is assumed that
$T_{-1}=U_{1}$ (and $T_{0}=U_{0}$).

For analysis purposes, the ghss level groups $G_{0},G_{1},\ldots,G_{L}$ are
partitioned into subsets $\text{lmargin}(G_{l}),\text{mid}(G_{l})$ and
$\text{rmargin}(G_{l})$ [Gan15] as follows.

$\displaystyle\text{lmargin}(G_{l})$ $\displaystyle=\\{i:T_{l}\leq\lvert
x_{i}\rvert<T_{l}(1+\bar{\epsilon}),$ $\displaystyle\text{rmargin}(G_{l})$
$\displaystyle=\\{i:T_{l-1}(1-2\bar{\epsilon})\leq\lvert
x_{i}\rvert<T_{l-1}\\},\text{ and }$ $\displaystyle\text{mid}(G_{l})$
$\displaystyle=\\{i:T_{l}+T_{l}\bar{\epsilon}\leq\lvert
x_{i}\rvert<T_{l-1}-2T_{l-1}\bar{\epsilon}\\}\enspace.$

For $G_{0}$, there is no $\text{rmargin}(G_{0})$ defined, and analogously for
$G_{L}$, there is no $\text{lmargin}(G_{L})$ defined. Instead, mid$(G_{0})$
and $\text{mid}(G_{L})$ are extended as follows.

$\displaystyle\text{mid}(G_{0})$ $\displaystyle=\\{i:\lvert x_{i}\rvert\geq
T_{0}(1+\bar{\epsilon})\\},$ $\displaystyle\text{mid}(G_{L})$
$\displaystyle=\\{i:0<\lvert x_{i}\rvert<T_{L-1}(1-2\bar{\epsilon})\\}$

Throughout the analysis, we will obtain bounds on expressions involving
probability of events conditioned on $\mathcal{G}$. It is often much easier to
prove the same expressions without conditioning on $\mathcal{G}$, and then
deriving upper and lower bounds on the probability conditioned by
$\mathcal{G}$. The following lemma from [Gan15] (Fact 21) is useful for this
purpose.

######  Lemma 23 (Fact 21 in [Gan15].)

Let $E$ and $G$ be a pair of events. Then,

$\left\lvert\text{Pr}\left[E\mid
F\right]-\text{Pr}\left[E\right]\right\rvert\leq\frac{1-\text{Pr}\left[F\right]}{\text{Pr}\left[F\right]}$

###  A.1 Proofs

The following lemma is a slight modification of Lemma 33 of [Gan15] by
reducing the conditions on which the probability event depends. It may be
noted that the event $\mathcal{G}$ of [Gan15] has been considerably trimmed to
define the event denoted by $\mathcal{G}$ in this work.

######  Lemma 24 ( Modified from [Gan15])

Let $i\in G_{l}$.

  1. 1.

If $i\in\text{mid}(G_{l})$, then,

$\bigl{\lvert}2^{l}\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]-1\bigr{\rvert}\leq
2^{l}\min(O(\delta),n^{-\Omega(1)})\enspace.$

Further, conditional on $\mathcal{G}\wedge\textsc{accuest}(i)$, (i)
$i\in\bar{G}_{l}$ iff $i\in\mathcal{S}_{l}$, and, (ii) $i$ may not belong to
any $\bar{G}_{l^{\prime}}$, for $l^{\prime}\neq l$.

  2. 2.

If $i\in\text{lmargin}(G_{l})$, then

$\displaystyle\bigl{\lvert}2^{l+1}\text{Pr}\left[i\in\bar{G}_{l+1}\mid\mathcal{G},\textsc{goodest}(i)\right]+2^{l}\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]-1\bigr{\rvert}$
$\displaystyle\leq 2^{l}\min(O(\delta),n^{-\Omega(1)})\enspace.$

Further, conditional on $\mathcal{G}\wedge\textsc{goodest}(i)(i)$, $i$ may
belong to either $\bar{G}_{l}$ or $\bar{G}_{l+1}$, but not to any other
sampled group.

  3. 3.

If $i\in\text{rmargin}(G_{l})$, then

$\displaystyle\bigl{\lvert}2^{l}\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]+2^{l-1}\text{Pr}\left[i\in\bar{G}_{l-1}\mid\mathcal{G},\textsc{goodest}(i)\right]-1\bigr{\rvert}$
$\displaystyle\leq 2^{l}\min(O(\delta),n^{-\Omega(1)})\enspace.$

Further, conditional on $\mathcal{G}\wedge\textsc{accuest}(i)$, $i$ can belong
to either $\bar{G}_{l-1}$ or $\bar{G}_{l}$ and not to any other sampled group.

The proof of Lemma 24 is similar to the proof of Lemma 33 in [Gan15]. We
provide an outline here to emphasize the slight generality of the current
version. The main difference in the statement is that the event $\mathcal{G}$
here is the conjunction of significantly fewer events than the event
$\mathcal{G}$ defined in [Gan15].

  * Proof:

Let $i\in\text{mid}(G_{l})$. Suppose $i\in\mathcal{S}_{l}$. We are given that
$\mathcal{G}$ and $\textsc{goodest}(i)$ hold. It is easy to see that
smallres$\wedge$ goodest$(i)$ imply $\textsc{accuest}(i)$, which therefore
also holds. We therefore have,

$\lvert\hat{x}_{il}-x_{i}\rvert\leq\frac{F_{2}^{\text{res}}\left({\lceil(2\alpha)^{l}C}\right)}{4(2\alpha)^{l}C}\leq\bar{\epsilon}\left(\frac{\hat{F_{2}}}{(4)2^{l}B_{l}}\right)^{1/2}\leq\bar{\epsilon}T_{l}$

where the first inequality follows from accuest$(i)$ and the second uses
$\textsc{goodf}_{2}$ followed by a relaxation using the definitions of the
thresholds. Thus

$\lvert\hat{x}_{il}\rvert\geq\lvert
x_{i}\rvert-\bar{\epsilon}T_{l}\geq(1+\bar{\epsilon})T_{l}-\bar{\epsilon}T_{l}=T_{l}\enspace.$

Since, $T_{l}>Q_{l}$, $\lvert\hat{x}_{il}\rvert>Q_{l}$ and by the definition
of discovery of item, $i$ qualifies to be discovered at level $l$. Further, a
direct calculation shows that if $i\in\mathcal{S}_{r}$ for any $r<l$ then, $i$
cannot be discovered at any level $r<l$. Indeed, by accuest$(i)$ we have,
$\lvert\hat{x}_{ir}-x_{i}\rvert\leq\bar{\epsilon}T_{r}$ and therefore,

$\displaystyle\lvert\hat{x}_{ir}\rvert$ $\displaystyle\leq\lvert
x_{i}\rvert+\bar{\epsilon}T_{r}<(1-2\bar{\epsilon})T_{l-1}+\bar{\epsilon}T_{r}\leq(1-\bar{\epsilon})T_{r}\leq
Q_{r}$

that is, $i$ is not discovered at any level $r<l$. A similar calculation shows
that $i$ is not discovered at any shelf $j\in[J]$.

Thus, under the presumptions of $\mathcal{G}\wedge\textsc{goodest}(i)$, if
$i\in\mathcal{S}_{l}$, then $i$ is discovered at level $l$ and is not
discovered at any lower level, that is, $l$ is the lowest level at which $i$
is discovered. Secondly, $\lvert\hat{x}_{il}\rvert\geq T_{l}$ implying that
$i$ is included into the group sample at level $l$, that is,
$i\in\bar{G}_{l}$.

Therefore, for any level $l\geq 1$,

$\displaystyle\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i),i\in\mathcal{S}_{l}\right]=1$

By law of total probability,

$\displaystyle\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]$
$\displaystyle=\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i),i\in\mathcal{S}_{l}\right]\text{Pr}\left[i\in\mathcal{S}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]$
$\displaystyle~{}~{}+\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i),i\not\in\mathcal{S}_{l}\right]\text{Pr}\left[i\not\in\mathcal{S}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]$
$\displaystyle=1\cdot\text{Pr}\left[i\in\mathcal{S}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]+0\cdot\text{Pr}\left[i\not\in\mathcal{S}_{l}\mid\mathcal{G},\textsc{goodest}(i),i\not\in\mathcal{S}_{l}\right]$
$\displaystyle=\text{Pr}\left[i\in\mathcal{S}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]$
$\displaystyle\in\text{Pr}\left[i\in\mathcal{S}_{l}\right]\pm\left(\frac{1-\text{Pr}\left[\mathcal{G},\textsc{goodest}(i)\right]}{\text{Pr}\left[\mathcal{G},\textsc{goodest}(i)\right]}\right),~{}~{}~{}~{}\text{
by Lemma~{}\ref{lem:fact}}$
$\displaystyle=2^{-l}\pm\min(n^{-\Omega(1)},O(\delta))\enspace.$

The last step is obtained as follows. $\textsc{accuest}(i)$ is implied by
$\textsc{smallres}\wedge\textsc{goodest}(i)$. Since $s=\Theta(\log n)$,
$\mathcal{G}$ holds with probability
$1-\min(O(\delta),\textrm{exp}\left\\{{-\Omega(s)}\right\\}=n^{-\Omega(1)})$
and goodest$(i)$ holds with probability $1-n^{-\Omega(1)}$. Multiplying by
$2^{l}$ on both sides and substracting 1, we get

$\displaystyle\left\lvert
2^{l}\text{Pr}\left[i\in\bar{G}_{l}\mid\mathcal{G},\textsc{goodest}(i)\right]-1\right\rvert\leq
2^{l}\min(n^{-\Omega(1)},O(\delta))\enspace.$

Items 2 and 3 in the statement of the lemma can be proved in a similar manner
by following the steps in the proof of Lemma 33 of [Gan15] and simplifying
them in the above manner.

Suppose it is given that $i$ belongs to ghss group $G_{l}$, for some level
$l$. Then, let $\mathsf{level}(i)$ denote this value of $l$. From the
definition of threholds $T_{l^{\prime}}$, for $l^{\prime}\in[0,\ldots,L]$ this
equals Let $\mathsf{level}(i)$ denote the true “level” of $i$, that is,

$\displaystyle\mathsf{level}(i)=\begin{cases}0&\text{ if
}x_{i}^{2}\geq\hat{F}_{2}/B\\\ \left\lfloor
2\log_{2\alpha}\left(\hat{F}_{2}/(x_{i}^{2}B)\right)\right\rfloor&\text{
otherwise.}\end{cases}$

Let $i$ be an item that belongs to ghss group $G_{l}$, where,
$l=\mathsf{level}(i)$. Assuming $\mathcal{G}$ and $\textsc{goodest}(i)$, by
Lemma 24, $i$ may either be correctly classified into
$\bar{G}_{\mathsf{level}(i)}$. However, if $i\in\text{lmargin}(G_{l})$, then
due to estimation errors of $\hat{x}_{il}$, $i$ may be classified to belong to
either $\bar{G}_{\mathsf{level}(i)}$ or to $\bar{G}_{\mathsf{level}(i)+1}$.
Finally, if $i\in\text{rmargin}(G_{l})$, then due to estimation errors again
$i$ may be classified to belong to either $\bar{G}_{\mathsf{level}(i)}$ or to
$\bar{G}_{\mathsf{level}(i)-1}$. In each case, assuming $\mathcal{G}$ and
$\textsc{goodest}(i)$, there is zero probability that $i$ would be classified
into a third group.

In certain equations, it is sometimes needed to sum or iterate over the
possible groups each item $i$ can be sampled into. Under the conditions
$\mathcal{G}$ and $\textsc{goodest}(i)$, it then suffices to iterate over only
the three groups $\mathsf{level}(i)-1,\mathsf{level}(i),\mathsf{level}(i)+1$.
Given $i\in[n]$ and $l\in\\{0,1,\ldots,L\\}$, we use the notation
$l~{}\textsf{~{}consist. with~{}}i$ to denote that
$l\in\\{\mathsf{level}(i)-1,\mathsf{level}(i),\mathsf{level}(i)+1\\}$.

###### Lemma 25

Let $i_{1},\ldots,i_{d}\in[n]$. Then,

$\displaystyle\sum_{l_{1}\textsf{~{}consist.
with~{}}~{}i_{1}}2^{l_{1}}\text{Pr}\left[i_{1}\in\bar{G}_{l_{1}}|\bigwedge_{j=h+1}^{d}i_{j}\in\mathcal{S}_{l_{j}},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip 72.26999pt=1\pm
2^{\mathsf{level}(i_{1})}\min(n^{-\Omega(1)},O(\delta))\enspace.$

  * Proof:

_Case 1:_ $i\in\text{mid}(G_{l})$. Then, conditional on $\mathcal{G}$ and
$\textsc{goodest}(i)$, as shown in the proof of Lemma 24, we have, (i)
$i\in\bar{G}_{l}$ iff $i\in\mathcal{S}_{l}$, and (ii) $i\not\in\bar{G}_{r}$,
for any $r\neq l$. Therefore, in this case,

$\sum_{l_{1}\text{ consist. with
}i_{1}}2^{l_{1}}\text{Pr}\left[i_{1}\in\bar{G}_{l_{1}}\left|\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}\right.,\mathcal{G},\textsc{goodest}(i)\right]\\\
=2^{l}\text{Pr}\left[i\in\mathcal{S}_{l}\left|\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}\right.,\mathcal{G},\textsc{goodest}(i)\right]$
(3)

Now, we have,
$\text{Pr}\left[i\in\mathcal{S}_{l}\left|\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}\right.\right]=2^{-l}$
assuming that (i) the hash functions $g_{l}$ are each drawn from a $d$-wise
independent family, for each $l\in[L]$, and, (ii) the $g_{l}$’s are
independent across $l$. Therefore, from Lemma 23, we have,

$\left\lvert\text{Pr}\left[i\in\mathcal{S}_{l}\left|\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}\right.,\mathcal{G},\textsc{goodest}(i)\right]-2^{-l}\right\rvert\leq\min(n^{-\Omega(1)},O(\delta))$

Multiplying above equation by $2^{l}$ and substituting in Eqn. (3), we obtain

$\displaystyle
2^{l}\text{Pr}\left[i\in\mathcal{S}_{l}\left|\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}\right.,\mathcal{G},\textsc{goodest}(i)\right]=1\pm
2^{l}\min(n^{-\Omega(1)},O(\delta))\enspace.$

_Case 2:_ $i_{1}\in\text{lmargin}(G_{l})$. Then, conditional on $\mathcal{G}$
and goodest$(i)$, the following statements follow from Lemma 24.

  1. 1.

$i_{1}$ cannot be discovered at level smaller than $l$ (with prob. 1).

  2. 2.

If $i_{1}\in\mathcal{S}_{l}$, then it is discovered at level $l$ (with
probability 1).

  3. 3.

$i_{1}\in\bar{G}_{l}$ iff $i_{1}\in\mathcal{S}_{l}$ and
$\lvert\hat{x}_{i_{1},l}\rvert\geq T_{l}$.

  4. 4.

$i_{1}\in\bar{G}_{l+1}$ iff $i_{1}\in\mathcal{S}_{1}$ and
$\lvert\hat{x}_{i_{1},1}\rvert<T_{l}$ and a random coin $K_{i}$ turns heads.

Let $E_{2,d}$ denote the event

$E_{2,d}=\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}\enspace.$

Therefore,

$\displaystyle\sum_{l_{1}\text{ consist. with
}i_{1}}2^{l_{1}}\text{Pr}\left[i_{1}\in\bar{G}_{l_{1}}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l}\text{Pr}\left[i_{1}\in\bar{G}_{l}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]+2^{l+1}\text{Pr}\left[i_{1}\in\bar{G}_{l+1}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l}\text{Pr}\left[\lvert\hat{x}_{il}\rvert\geq
T_{l},i_{1}\in\mathcal{S}_{l}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
(4) $\displaystyle\hskip
14.45377pt+2^{l+1}\text{Pr}\left[\lvert\hat{x}_{il}\rvert<T_{l},i_{1}\in\mathcal{S}_{l},K_{i}=1|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l}\text{Pr}\left[\lvert\hat{x}_{il}\rvert\geq
T_{l}|i_{1}\in\mathcal{S}_{l},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]\text{Pr}\left[i_{1}\in\mathcal{S}_{l}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip
14.45377pt+2^{l}\text{Pr}\left[\lvert\hat{x}_{il}\rvert<T_{l}|i_{1}\in\mathcal{S}_{l},E_{2,d},\mathcal{G}\right]\text{Pr}\left[i_{1}\in\mathcal{S}_{l},|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l}\text{Pr}\left[i_{1}\in\mathcal{S}_{l}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
(5)

Now, by $d$-wise independence of the hash functions $g_{1},\ldots,g_{l}$, we
have, $\text{Pr}\left[i_{1}\in\mathcal{S}_{l},|E_{2,d}\right]=2^{-l}$.
Therefore,

$\displaystyle\text{Pr}\left[i_{1}\in\mathcal{S}_{l}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]=2^{-l}\pm\min(n^{-\Omega(1)},O(\delta))$

Substituting in Eqn. (5), we have,

$\displaystyle
2^{l}\text{Pr}\left[i_{1}\in\mathcal{S}_{l}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]=1\pm
2^{l}\min(n^{-\Omega(1)},O(\delta))\enspace.$

_Case 3:_ $i_{1}\in\text{rmargin}(G_{l})$. As before, let $E_{2,d}$ denote the
event $\bigwedge_{j=2}^{d}i_{j}\in\mathcal{S}_{l_{j}}$. By Lemma 24 and
assuming $\mathcal{G}$ and goodest$(i)$, we have the following observations.

  1. 1.

It is possible for $i_{1}\in\text{rmargin}(G_{l})$ to be discovered at level
$l-1$. This happens if
$\lvert\hat{x}_{i_{1},l-1}\rvert>Q_{l-1}=T_{l-1}(1-\bar{\epsilon})$.

  2. 2.

It is not possible (i.e., is a zero probability event) that $i_{1}$ is
discovered at levels lower than $l-1$.

  3. 3.

It is also possible for $i_{1}$ to be classified into the sample at level
$l-1$, that is, $i_{1}\in\bar{G}_{l-1}$. This happens iff
$i\in\mathcal{S}_{l-1}$ and $\lvert\hat{x}_{i_{1},l-1}\rvert\geq T_{l-1}$.

  4. 4.

It is possible for $i_{1}$ to be classified into the sample at level $l$, that
is, $i_{1}\in\bar{G}_{l}$. This can happen in one of the two mutually
exclusive ways.

    1. (a)

$i\in\mathcal{S}_{l-1}$ and $Q_{l-1}<\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1}$
and $K_{i}=1$.

    2. (b)

$i\in\mathcal{S}_{l}$ and $\lvert\hat{x}_{i_{1},l-1}\rvert\leq Q_{l-1}$.

The _LHS_ can be written as follows. For $i_{1}\in\text{rmargin}(G_{l})$, the
levels consistent with $i_{1}$ are $l-1$ and $l$. Thus, we have,

$\displaystyle\sum_{l_{1}\text{ consist. with
}i_{1}}2^{l_{1}}\text{Pr}\left[i_{1}\in\bar{G}_{l_{1}}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[i_{1}\in\bar{G}_{l-1}\left|E_{2,d}\right.,\mathcal{G},\textsc{goodest}(i_{1})\right]+2^{l}\text{Pr}\left[i_{1}\in\bar{G}_{l}\left|E_{2,d}\right.,\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert\geq
T_{l-1},i_{1}\in\mathcal{S}_{l-1}\left|E_{2,d}\right.,\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle~{}+2^{l}\text{Pr}\left[Q_{l-1}\leq\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1},K_{i}=1,i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle~{}~{}~{}~{}~{}+2^{l}\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1,i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$ (6)

The final expression is the sum of three terms. We consider these terms
individually and then combine them. The first term can be written as

Term 1
$\displaystyle=2^{l-1}\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert\geq
T_{l-1},i_{1}\in\mathcal{S}_{l-1}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert\geq
T_{l-1}|i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip
72.26999pt\cdot\text{Pr}\left[i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$ (7)

Now,
$\text{Pr}\left[i_{1}\in\mathcal{S}_{l-1}|E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]=2^{-(l-1)}\pm\min(n^{-\Omega(1)},O(\delta))$.
Substituting in Eqn. (A.1), we obtain,

$\displaystyle\text{Term 1}=$
$\displaystyle\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert\geq
T_{l-1}|i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip 72.26999pt\left(1\pm
2^{l-1}\min(n^{-\Omega(1)},O(\delta))\right)\enspace.$ (8)

The second term is

Term 2
$\displaystyle=2^{l}\text{Pr}\left[Q_{l-1}<\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1},K_{i}=1,i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[Q_{l-1}<\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1},i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]\enspace.$ (9)

since, $K_{i}=1$ happens with probability $1/2$ and is independent of all
other random terms occurring in the expression. By definition of conditional
probability, Eqn. (A.1) equals

Term 2
$\displaystyle=2^{l-1}\text{Pr}\left[Q_{l-1}<\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip
72.26999pt\cdot\text{Pr}\left[i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[Q_{l-1}<\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip
72.26999pt\cdot\left(2^{-(l-1)}\pm\min(n^{-\Omega(1)},O(\delta))\right)$
$\displaystyle=\text{Pr}\left[Q_{l-1}<\lvert\hat{x}_{i_{1},l-1}\rvert<T_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip 72.26999pt\cdot\left(1\pm
2^{(l-1)}\min(n^{-\Omega(1)},O(\delta))\right)\enspace.$ (10)

Adding the simplified terms for the first and second expression from Eqns.
(A.1) and (A.1), we obtain,

$\displaystyle\text{ Term 1}+\text{ Term 2}$
$\displaystyle=\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert>Q_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\left(1\pm
2^{(l-1)}\min(n^{-\Omega(1)},O(\delta))\right)\enspace.\enspace.$ (11)

We now consider Term 3. By definition of conditional probability, we have,

Term 3
$\displaystyle=2^{l}\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1,i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle=2^{l}\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G}\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip
72.26999pt\cdot\text{Pr}\left[i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]\enspace.$ (12)

As argued earlier, $\text{Pr}\left[i_{1}\in\mathcal{S}_{l-1}\mid
E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]=2^{-(l-1)}\pm\min(n^{-\Omega(1)},O(\delta))$.
Simplifying by substituting in Eqn. (A.1), we obtain,

Term3
$\displaystyle=2\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip 72.26999pt\cdot\left(1\pm
2^{l-1}\min(n^{-\Omega(1)},O(\delta))\right)\enspace.$ (13)

Consider a related probability
$\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]$. Since, the
event $g_{l}(i_{1})=1$ is independent of (i) the event
$i_{1}\in\mathcal{S}_{l-1}$ (by independence of $g_{l}$ and $g_{r}$’s for all
$r\neq l$), (ii) the event $E_{2,d}$ by independence and $d$-wise independence
of $g_{l}$, and (iii) $\textsc{goodest}(i_{1})$ which considers the inferences
obtained until level $l-1$, we have,

$\displaystyle\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]$
$\displaystyle=\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip 72.26999pt\cdot\text{Pr}\left[g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]\enspace.$
(14)

The second product probability term simplifies to
$(1/2)\pm\min(n^{-\Omega(1)},O(\delta))$. Substituting in Eqn. (A.1), we have,

$\displaystyle\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]$
$\displaystyle=\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]\left(1/2\pm\min(n^{-\Omega(1)},O(\delta))\right)\enspace.$
(15)

Therefore,

$\displaystyle\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1}),\mathcal{G}\right]$
$\displaystyle=\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]\pm\min(n^{-\Omega(1)},O(\delta))$
$\displaystyle=\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]\left(1/2\pm\min(n^{-\Omega(1)},O(\delta))\right)$
$\displaystyle\hskip 72.26999pt\pm\min(n^{-\Omega(1)},O(\delta))\enspace.$
(16)

Substituting in Eqn. (A.1), we have,

Term3
$\displaystyle=2\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1},g_{l}(i_{1})=1\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\mathcal{G},\textsc{goodest}(i_{1})\right]$
$\displaystyle\hskip 72.26999pt\cdot\left(1\pm
2^{l-1}\min(n^{-\Omega(1)},O(\delta))\right)$
$\displaystyle=2\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]\left(1/2\pm\min(n^{-\Omega(1)},O(\delta))\right)$
$\displaystyle\hskip 72.26999pt\pm\min(n^{-\Omega(1)},O(\delta))$
$\displaystyle=\text{Pr}\left[\lvert\hat{x}_{i_{1},l-1}\rvert<Q_{l-1}\mid
i_{1}\in\mathcal{S}_{l-1},E_{2,d},\textsc{goodest}(i_{1})\right]\left(1\pm\min(n^{-\Omega(1)},O(\delta))\right)$
$\displaystyle\hskip 72.26999pt\pm\min(n^{-\Omega(1)},O(\delta))\enspace.$
(17)

Adding Eqns. (A.1) and (A.1), we obtain

$\displaystyle\text{ Term 1 }+\text{ Term 2}+\text{ Term 3}$
$\displaystyle=\left(1\pm
2^{l-1}\min(n^{-\Omega(1)},O(\delta))\right)\pm\min(n^{-\Omega(1)},O(\delta))$
$\displaystyle=1\pm 2^{l}\min(n^{-\Omega(1)},O(\delta))\enspace.$

###### Corollary 26

Let $i_{1},\ldots,i_{d}\in[n]$ and $S\subset\\{i_{1},\ldots,i_{d}\\}$
containing $i_{1}$. Then,

$\displaystyle\sum_{l_{1}\textsf{~{}consist.
with~{}}~{}i_{1}}2^{l_{1}}\text{Pr}\left[i_{1}\in\bar{G}_{l_{1}}\left|\bigwedge_{j=h+1}^{d}i_{j}\in\mathcal{S}_{l_{j}},\mathcal{G},\bigwedge_{j\in
S}\textsc{goodest}(j)\right.\right]$ $\displaystyle=1\pm
2^{\mathsf{level}(i_{1})}\lvert
S\rvert\min(n^{-\Omega(1)},O(\delta))\enspace.$

  * Proof:  The proof proceeds identically as the proof for Lemma 25.

###### Lemma 27

[Re-statement of Lemma 7.] Let $i_{1},\ldots,i_{d}\in[n]$ and distinct $1\leq
h\leq d$. Then,

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\textsf{~{}consist.
with~{}}i_{j}\\\ \forall
j\in[h]\end{subarray}}2^{l_{1}+l_{2}+\ldots+l_{h}}\text{Pr}\left[\left.\bigwedge_{j=1}^{h}i_{j}\in\bar{G}_{l_{j}}\right|\bigwedge_{j=h+1}^{d}i_{j}\in\mathcal{S}_{l_{j}},\mathcal{G},\bigwedge_{j=1}^{d}\textsc{goodest}(i_{j})\right]$
$\displaystyle\in\prod_{j=1}^{h}\left(1\pm
2^{\mathsf{level}(i_{j})+1}\cdot\left(\min(n^{-\Omega(1)},\delta)+dn^{-\Omega(1)}\right)\right)$

  * Proof:  The proof proceeds by induction on $h$.

The base case occurs when $h=1$ and has been proved in Lemma 25 and Corollary
26.

_Induction Case._ Let $E_{h+1,d}$ denote the event
$\bigwedge_{j=h+1}^{d}i_{j}\in\mathcal{S}_{l_{j}}$, $G_{h}$ denote the event
$\bigwedge_{j=1}^{h}i_{j}\in\bar{G}_{l_{j}}$ and
$K_{d}=\bigwedge_{j=1}^{d}\textsc{goodest}(i_{j})$. Also, for simplicity, let
$\delta^{\prime}$ denote $\min(n^{-\Omega(1)},O(\delta))$. In this notation,
the statement of the lemma can be written as

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h+1}}\text{Pr}\left[G_{h}\mid
E_{h+1,d},\mathcal{G},K_{d}\right]\in\prod_{j=1}^{h}(1\pm
2^{\mathsf{level}(i_{j})+1})\left(\delta^{\prime}+dn^{-\Omega(1)}\right)\enspace.$
(18)

We assume that for a fixed $h\in[d-1]$, the induction hypothesis holds, that
is,

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h}}\text{Pr}\left[G_{h}|E_{h+1,d},\mathcal{G},K_{d}\right]\in\prod_{j=1}^{h+1}(1\pm
2^{\mathsf{level}(i_{j})+1})\left(\delta^{\prime}+dn^{-\Omega(1)}\right)\enspace.$

We now have to show that the following equation holds.

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h+1]\end{subarray}}2^{l_{1}+\ldots+l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]\in\prod_{j=1}^{h+1}(1\pm
2^{\mathsf{level}(i_{j})+1})\left(\delta^{\prime}+dn^{-\Omega(1)}\right)\enspace.$

_Induction Case 1:_ Suppose there exists a $j\in[h+1]$ such that
$i_{j}\in\text{mid}(G_{l})$. Without loss of generality, let $j=h+1$ and
$i_{h+1}\in\text{mid}(G_{l})$ (this can be done by rearranging the indices
$j_{1},\ldots,j_{h+1}$, without affecting the statement). Then,

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall j\in[h+1]\end{subarray}}2^{l_{1}+\ldots
l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall j\in\\{1,\ldots,h\\}\end{subarray}}2^{l_{1}+\ldots
l_{h}+l}\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l})|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall j\in\\{1,\ldots,h\\}\end{subarray}}2^{l+l_{1}+\ldots
l_{h}}\text{Pr}\left[G_{h}|i_{h+1}\in\mathcal{S}_{l}\wedge
E_{h+2,d},\mathcal{G},K_{d}\right]\text{Pr}\left[i_{1}\in\mathcal{S}_{l}\mid
E_{h+2,d},\mathcal{G},K_{d}\right]$ (19)

The term

$\displaystyle\text{Pr}\left[G_{h}|i_{h+1}\in\mathcal{S}_{l}\wedge
E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=\text{Pr}\left[G_{h}|E_{h+1,d},\mathcal{G},K_{d}\right]\prod_{j=1}^{h}(1\pm
2^{\mathsf{level}(i_{j})+1}\left(O(\delta)+dn^{-\Omega(1)}\right)$

by the induction hypothesis. The second term in Eqn. (A.1) is evaluated as
follows. By $d$-wise independence, $\text{Pr}\left[i_{1}\in\mathcal{S}_{l}\mid
E_{h+2,d}\right]=2^{-l}$. Also, $\mathcal{G}$ holds with probability
$1-\delta^{\prime}$ and $K_{d}$ holds with probability $1-dn^{-\Omega(1)}$.
Therefore, $\mathcal{G}\wedge K_{d}$ holds with probability
$1-\delta^{\prime}-dn^{-\Omega(1)}$. Hence, by Lemma 23,

$\text{Pr}\left[i_{1}\in\mathcal{S}_{l}\mid
E_{h+2,d},\mathcal{G},K_{d}\right]\in 2^{-l}\pm
O(\delta^{\prime}+dn^{-\Omega(1)})\enspace.$

Therefore, Eqn. (A.1) can be bounded as

$\displaystyle\prod_{j=1}^{h+1}(1\pm
2^{\mathsf{level}(i_{j})+1}\left(O(\delta)+dn^{-\Omega(1)}\right)$

there by proving this case.

_Induction Case 2:_ Suppose there exists an index $j\in[h+1]$ such that
$i_{j}\in\text{lmargin}(G_{l})$. By reordering the indices, we can assume
without loss of generality that $i_{h+1}\in\text{lmargin}(G_{l})$. Conditional
on $\mathcal{G}$ and goodest$(i)$, as shown in Lemma 24, the following holds.

  1. 1.

$i_{h+1}\in\bar{G}_{l}$ iff $i_{h+1}\in\mathcal{S}_{l}$ and
$\lvert\hat{x}_{h+1,l}\rvert\geq T_{l}$.

  2. 2.

$i_{h+1}\in\bar{G}_{l+1}$ iff $i_{h+1}\in\mathcal{S}_{l}$ and
$Q_{l}<\lvert\hat{x}_{h+1,l}\rvert<T_{l}$.

  3. 3.

$i_{h+1}\in\bar{G}_{r}$, for any $r\in[L]\setminus\\{l,l+1\\}$.

Then,

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall j\in[h+1]\end{subarray}}2^{l_{1}+\ldots
l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h}+l}\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l}\wedge\lvert\hat{x}_{i_{h+1},l}\rvert\geq
T_{l})|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle+\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h}+l+1}$ $\displaystyle\hskip
72.26999pt\cdot\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l}\wedge(\lvert\hat{x}_{i_{h+1},l}\rvert<T_{l},K_{i_{h+1}}=1)|E_{h+2,d},\mathcal{G},K_{d}\right]$
(20)

Since the coin toss $K_{i_{h+1}}=1$ occurs with probability 1/2 and is
independent of all the other random bits, the second probability expression in
the _RHS_ of Eqn. (A.1), we have,

$\displaystyle\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l}\wedge\lvert\hat{x}_{i_{h+1},l}\rvert<T_{l},K_{i_{h+1}}=1)|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=(1/2)\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l}\wedge\lvert\hat{x}_{i_{h+1},l}\rvert<T_{l})|E_{h+2,d},\mathcal{G},K_{d}\right]\enspace.$

Thus, the _RHS_ of Eqn. (A.1) is simplified as follows.

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h]\end{subarray}}\left(2^{l_{1}+\ldots+l_{h}+l}\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l}\wedge\lvert\hat{x}_{i_{h+1},l}\rvert\geq
T_{l})|E_{h+2,d},\mathcal{G},K_{d}\right]\right.$
$\displaystyle\left.~{}~{}+2^{l_{1}+\ldots+l_{h}+l+1}(1/2)\text{Pr}\left[G_{h}\wedge(i_{h+1}\in\mathcal{S}_{l}\wedge\lvert\hat{x}_{i_{h+1},l}\rvert<T_{l})|E_{h+2,d},\mathcal{G},K_{d}\right]\right)$
$\displaystyle=\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h}+l}\text{Pr}\left[G_{h}\wedge
i_{h+1}\in\mathcal{S}_{l}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h}+l}\text{Pr}\left[G_{h}|i_{h+1}\in\mathcal{S}_{l}\wedge
E_{h+2,d},\mathcal{G},K_{d}\right]$ $\displaystyle\hskip
72.26999pt\cdot\text{Pr}\left[i_{h+1}\in\mathcal{S}_{l}|E_{h+2,d},\mathcal{G},K_{d}\right]$
(21)

where the first step follows from probability axioms of union of exclusive
events, and the last step follows from the definition of conditional
probability. Now, as discussed earlier in this proof,
$\text{Pr}\left[i_{h+1}\in\mathcal{S}_{l}|E_{h+2,d}\right]=2^{-l}$ and
therefore,
$\text{Pr}\left[i_{h+1}\in\mathcal{S}_{l}|E_{h+2,d},\mathcal{G},K_{d}\right]=2^{-l}\pm\min(O(\delta),n^{-\Omega(1)})+dn^{-\Omega(1)}$.
Also, the event $i_{h+1}\in\mathcal{S}_{l}\wedge E_{h+2,d}=E_{h+1,d}$. Hence,
the probability expression in the _RHS_ of Eqn. (A.1) is

$\displaystyle=\sum_{\begin{subarray}{c}l_{j}\text{ consistent with }i_{j}\\\
\forall
j\in[h]\end{subarray}}2^{l_{1}+\ldots+l_{h}}\text{Pr}\left[G_{h}|E_{h+1,d},\mathcal{G},K_{d}\right](1\pm
2^{l}\min(O(\delta),n^{-\Omega(1)})+dn^{-\Omega(1)})$ $\displaystyle=(1\pm
2^{l}\min(O(\delta),n^{-\Omega(1)})+dn^{-\Omega(1)})\prod_{j=1}^{h}\left(1\pm
2^{l_{j}+1}\min(O(\delta),n^{-\Omega(1)})\right)$

by the induction hypothesis, thereby proving this induction case.

_Induction Case 3:_ For this case, it suffices to assume that for each
$j\in[h+1]$, $i_{j}\in\text{rmargin}(G_{l_{j}})$. Assume that we re-order the
items so that $\lvert x_{i_{h+1}}\rvert\geq\lvert
x_{i_{h}}\rvert\geq\ldots\geq\lvert x_{i_{1}}\rvert$. Let
$\mathsf{level}(i_{h+1})=l$. Therefore, the expression for the _LHS_ is

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\textsf{~{}consist.
with~{}}i_{j}\\\ \forall
j\in[h+1]\end{subarray}}2^{l_{1}+l_{2}+\ldots+l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]\enspace.$
(22)

We are given that $i_{h+1}\in\text{rmargin}(G_{l})$. Conditional on
$\mathcal{G}$ and goodest , we have the following.

  1. 1.

$i_{h+1}$ may be discovered at level $l-1$ (only if
$i_{h+1}\in\mathcal{S}_{l-1})$ or possibly at level $l$ (only if
$i_{h+1}\in\mathcal{S}_{l})$, but at no lower level than $l-1$.

  2. 2.

$i_{h+1}\in\bar{G}_{l-1}$ if $i_{h+1}\in\mathcal{S}_{l-1}$ and
$\lvert\hat{x}_{i_{h+1},l-1}\rvert\geq T_{l-1}$.

  3. 3.

$i_{h+1}\in\bar{G}_{l}$ in one of two mutually exclusive ways.

    1. (a)

$i\in\mathcal{S}_{l-1}$ and
$Q_{l-1}=T_{l-1}(1-\bar{\epsilon}))<\lvert\hat{x}_{i_{h+1},l-1}\rvert<T_{l}$
and the coin toss $K_{i}=1$.

    2. (b)

$i\in\mathcal{S}_{l-1}$ and $g_{l}(i_{h+1})=1$ and
$\lvert\hat{x}_{i_{h+1},l-1}\rvert<Q_{l-1}$.

The probability term in Eqn. (22) can be written as follows.

$\displaystyle\sum_{l_{h+1}\textsf{~{}consist.
with~{}}i_{h+1}}2^{l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h}\wedge
i_{h+1}\in\bar{G}_{l-1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle~{}~{}+2^{l}\text{Pr}\left[G_{h}\wedge
i_{h+1}\in\bar{G}_{l}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},\lvert\hat{x}_{h+1,l-1}\rvert\geq
T_{l-1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle~{}~{}+2^{l}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}<\lvert\hat{x}_{h+1,l-1}\rvert<T_{l-1},K_{i}=1\mid
E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle~{}~{}+2^{l}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},g_{l}(i_{h+1})=1,Q_{l-1}>\lvert\hat{x}_{i_{h+1},l-1}\rvert\mid
E_{h+2,d},\mathcal{G},K_{d}\right]$ (23)

We simplify the above equation to consider the following expression, which we
will relate back to the _RHS_ of Eqn. (A.1).

$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},\lvert\hat{x}_{h+1,l-1}\rvert\geq
T_{l-1}|E_{h+2,d},\right]$
$\displaystyle~{}~{}+2^{l}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}<\lvert\hat{x}_{h+1,l-1}\rvert<T_{l-1},K_{i}=1\mid
E_{h+2,d}\right]$
$\displaystyle~{}~{}+2^{l}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},g_{l}(i_{h+1})=1,Q_{l-1}>\lvert\hat{x}_{i_{h+1},l-1}\rvert\mid
E_{h+2,d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},\lvert\hat{x}_{h+1,l-1}\rvert\geq
T_{l-1}|E_{h+2,d},\right]$
$\displaystyle~{}~{}+2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}<\lvert\hat{x}_{h+1,l-1}\rvert<T_{l-1}\mid
E_{h+2,d}\right]$
$\displaystyle~{}~{}+2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}>\lvert\hat{x}_{i_{h+1},l-1}\rvert\mid
E_{h+2,d}\right]$ (24)

The last step follows since $g_{l}(i_{h+1})$ is independent of $g_{r}$ for
$r\neq l$ and comes from a $d$-wise independent family. So Eqn. (A.1) becomes

$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1}\mid
E_{h+2,d}\right]$ (25)

Each of the summands in the expression of the _RHS_ of Eqn. (A.1) can be
written as follows.

$\displaystyle
2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},\lvert\hat{x}_{h+1,l-1}\rvert\geq
T_{l-1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},\lvert\hat{x}_{h+1,l-1}\rvert\geq
T_{l-1}|E_{h+2,d}\right]\pm
2^{l-1}\left(\delta^{\prime}+dn^{-\Omega(1)}\right)\enspace.$ (26)
$\displaystyle
2^{l}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}<\lvert\hat{x}_{h+1,l-1}\rvert<T_{l-1},K_{i}=1\mid
E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}<\lvert\hat{x}_{h+1,l-1}\rvert<T_{l-1},K_{i}=1\mid
E_{h+2,d}\right]\pm 2^{l-1}(\delta^{\prime}+dn^{-\Omega(1)})$ (27)
$\displaystyle
2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},g_{l}(i_{h+1})=1,Q_{l-1}>\lvert\hat{x}_{i_{h+1},l-1}\rvert\mid
E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1},Q_{l-1}>\lvert\hat{x}_{i_{h+1},l-1}\rvert\mid
E_{h+2,d}\right]\pm 2^{l-1}\left(\delta^{\prime}+dn^{-\Omega(1)}\right)$ (28)

Adding Eqns. (26) through (28), we have,

$\displaystyle\sum_{l_{h+1}\textsf{~{}consist.
with~{}}i_{h+1}}2^{l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1}\mid
E_{h+2,d}\right]\pm 3\cdot 2^{l-1}(\delta^{\prime}+dn^{-\Omega(1)})$ (29)

Further, consider the probability term in the _RHS_ of Eqn. (A.1). We have,

$\displaystyle\text{Pr}\left[G_{h},i_{h+1}\in\mathcal{S}_{l-1}\mid
E_{h+2,d}\right]$ $\displaystyle=\text{Pr}\left[G_{h}\mid
E_{h+2,d},i_{h+1}\in\mathcal{S}_{l-1}\right]\cdot\text{Pr}\left[i_{h+1}\in\mathcal{S}_{l-1}\mid
E_{h+2,d}\right]$ $\displaystyle=2^{-(l-1)}\text{Pr}\left[G_{h}\mid
E_{h+1,d}\right]$

Substituting in Eqn. (A.1), we have,

$\displaystyle\sum_{l_{h+1}\textsf{~{}consist.
with~{}}i_{h+1}}2^{l_{h+1}}\text{Pr}\left[G_{h+1}|E_{h+2,d},\mathcal{G},K_{d}\right]$
$\displaystyle=2^{l-1}\text{Pr}\left[G_{h}\mid E_{h+1,d}\right]\pm 3\cdot
2^{l-1}\left(\delta^{\prime}+dn^{-\Omega(1)}\right)$
$\displaystyle=\text{Pr}\left[G_{h}\mid E_{h+1,d},\mathcal{G},K_{d}\right]\pm
4\cdot 2^{l-1}\left(\delta^{\prime}+dn^{-\Omega(1)}\right)$

Therefore,

$\displaystyle\sum_{\begin{subarray}{c}l_{j}\textsf{~{}consist.
with~{}}i_{j}\\\ \forall
j\in[h+1]\end{subarray}}2^{l_{1}+\ldots+l_{h+1}}\text{Pr}\left[G_{h+1}\mid
E_{h+2,d},\mathcal{G},K_{d}\right]$ $\displaystyle=\prod_{j=1}^{h}(1\pm
2^{\mathsf{level}(i_{j})+1}(\delta^{\prime}+dn^{-\Omega(1)})\pm 4\cdot
2^{l-1}\left(\delta^{\prime}+dn^{-\Omega(1)}\right)$

which proves the property.

###  A.2 $p$th power estimator for $\lvert x_{i}\rvert^{p}$

###### Lemma 28

Let $W=\sum_{j=1}^{n}a_{j}\omega(j)$ where, $\\{\omega(j)\\}_{j=1}^{n}$ is a
2d-wise independent family of randomly chosen roots of $x^{q}=1$ for any
integer $q>d$, where, $d\in{\mathbb{Z}}^{+}$. Then, for any $d\geq 1$,
$\mathbf{E}\left[(W\overline{W})^{d}\right]\leq
d!\left\lVert{a}\right\rVert_{2}^{2d}$, where $a$ is the $n$-dimensional
vector $(a_{1},a_{2},\ldots,a_{n})$.

  * Proof:

$\displaystyle\mathbf{E}\left[(W\overline{W})^{d}\right]$
$\displaystyle=\sum_{e_{1}+\ldots+e_{n}=d}\sum_{g_{1}+\ldots+g_{n}=d}\binom{d}{e_{1},\ldots,e_{n}}\binom{d}{g_{1},\ldots,g_{n}}\prod_{j=1}^{n}a_{j}^{e_{j}+g_{j}}\mathbf{E}\left[\omega_{j}^{e_{j}}\overline{\omega_{j}}^{g_{j}}\right]$
$\displaystyle=\sum_{e_{1}+\ldots+e_{n}=d}\binom{d}{e_{1},\ldots,e_{n}}^{2}a_{j}^{2e_{j}}$
$\displaystyle\leq
d!\sum_{e_{1}+\ldots+e_{n}=d}\binom{d}{e_{1},\ldots,e_{n}}a_{j}^{2e_{j}}$
$\displaystyle=d!\left\lVert{a}\right\rVert_{2}^{2d}$

The first step views $(W\overline{W})^{d}$ as $W^{d}\overline{W}^{d}$ and
takes the product of the multinomial expansion for $W^{d}$ and
$\overline{W}^{d}$; and subsequently uses linearity of expectation. The second
step follows since
$\mathbf{E}\left[\omega_{j}^{e_{j}}\overline{\omega_{j}}^{g_{j}}\right]=0$
unless $e_{j}=g_{j}$, in which case, it is 1.

######  Lemma 29 (Re-statement of Lemma 8.)

Let $Z=\sum_{j=1}^{t}a_{j}\omega(j)\chi(j)$, where,
$\\{\omega(j)\\}_{j=1}^{t}$ is a family of random and $2d$-wise independent
family roots of the equation $x^{q}=1$, $q>2d$ and integral. Let
$\\{\chi(j)\\}$ be a $2d$-wise independent family of indicator variables such
that $\text{Pr}\left[\chi(j)=1\right]=1/C$ and is independent of the
$\omega_{j}$’s. If $\left\lVert{a}\right\rVert_{2}^{2}\geq
4d\left\lVert{a}\right\rVert_{\infty}^{2}C$, then,

$\mathbf{E}\left[(Z\bar{Z})^{d}\right]\leq(2)\left(\frac{d\left\lVert{a}\right\rVert_{2}^{2}}{C}\right)^{d}$

where, $a$ is the $t$-dimensional vector $(a_{1},a_{2},\ldots,a_{t})$.

  * Proof:  [Proof of Lemma 8.] Assume $K=\left\lVert{a}\right\rVert_{\infty}$.

$\mathbf{E}\left[(Z\bar{Z})^{d}\right]=\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{t}=d\\\
e_{j}\text{'s }\geq
0\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{t}=d\\\ g_{j}\text{'s
}\geq
0\end{subarray}}\binom{d}{e_{1},\ldots,e_{t}}\binom{d}{g_{1},\ldots,g_{t}}\\\
\cdot\prod_{u=1}^{t}a_{u}^{e_{u}+g_{u}}\mathbf{E}\left[\omega^{e_{u}}(j)\bar{\omega}^{g_{u}}(j)\right]\mathbf{E}\left[\chi^{e_{u}+g_{u}}(j)\right]~{}~{}$

(by $2d$-wise independence). The expectation is 0 unless $e_{u}=g_{u}$ for
each $u\in[t]$. Therefore,

$\displaystyle\mathbf{E}\left[(Z\bar{Z})^{d}\right]$ (30)
$\displaystyle=\sum_{r=1}^{d}\sum_{e_{1}+\ldots+e_{r}=d,e_{j}\text{'s}\geq
1}\binom{d}{e_{1},\ldots,e_{r}}^{2}\sum_{1\leq i_{1}<\ldots<i_{r}\leq
t}\prod_{u=1}^{r}\frac{a_{i_{u}}^{2e_{u}}}{C}$ $\displaystyle\leq
K^{2d}\sum_{r=1}^{d}\frac{1}{K^{2r}}\sum_{e_{1}+\ldots+e_{r}=d}\binom{d}{e_{1},\ldots,e_{r}}^{2}\sum_{1\leq
i_{1}<\ldots<i_{r}\leq t}\prod_{u=1}^{r}\frac{a_{i_{u}}^{2}}{C}$ (since,
$a_{i_{u}}^{2e_{u}}\leq K^{2e_{u}-2}a_{i_{u}}^{2})$ $\displaystyle\leq
K^{2d}\sum_{r=1}^{d}\frac{d!}{K^{2r}}\sum_{e_{1}+\ldots+e_{r}=d}\binom{d}{e_{1},\ldots,e_{r}}\frac{1}{r!}\left(\frac{\left\lVert{a}\right\rVert_{2}^{2}}{C}\right)^{r}$
(31) $\displaystyle\leq
K^{2d}d!\sum_{r=1}^{d}\frac{1}{r!}\left(\frac{\left\lVert{a}\right\rVert_{2}^{2}}{K^{2}C}\right)^{r}\frac{d^{r}}{(d-r+1)}\cdot
r^{d-r}$ (32)

Eqn. (31) follows by observing that (i) $\sum_{1\leq i_{1}<\ldots<i_{r}\leq
t}\prod_{u=1}^{r}\frac{a_{i_{u}}^{2}}{C}\leq\frac{1}{r!}\left(\frac{\left\lVert{a}\right\rVert_{2}^{2}}{C}\right)^{r}$,
which can be seen by expanding
$\frac{1}{C^{r}}\left(\sum_{j=1}^{t}a_{j}^{2}\right)^{r}$, and, (ii)
$\binom{d}{e_{1},\ldots e_{r}}^{2}\leq d!\binom{d}{e_{1},\ldots,e_{r}}$.
Eqn. (32) is obtained as follows. Let $e^{\prime}_{j}=e_{j}-1$. Then,

$\displaystyle\sum_{e_{1}+\ldots+e_{r}=d,e_{j}\text{'s}\geq 1}$
$\displaystyle\binom{d}{e_{1},\ldots,e_{r}}$
$\displaystyle=\left(\frac{d(d-1)\ldots(d-r+1)}{e_{1}e_{2}\ldots
e_{r}}\right)\sum_{e^{\prime}_{1}+\ldots+e^{\prime}_{r}=d-r,e^{\prime}_{j}\text{'s}\geq
0}\binom{d-r}{e^{\prime}_{1},e^{\prime}_{2},\ldots,e^{\prime}_{r}}$

Now, $\frac{d(d-1)\ldots(d-r)}{e_{1}e_{2}\ldots
e_{r}}\leq\left(\frac{d^{r}}{d-r+1}\right)$, where the product
$e_{1}e_{2}\ldots e_{r}$ is minimized, subject to $e_{1},\ldots,e_{r}\geq 1$
and $e_{1}+\ldots+e_{r}=d$, by letting $e_{1},\ldots,e_{r-1}$ to be 1 and
$e_{r}=d-r+1$. Also,

$\sum_{e^{\prime}_{1}+\ldots+e^{\prime}_{r}=d-r,e^{\prime}_{j}\text{'s}\geq
0}\binom{d-r}{e^{\prime}_{1},e^{\prime}_{2},\ldots,e^{\prime}_{r}}=(\underbrace{1+1+\ldots+1}_{\text{
$r$ times }})^{d-r}=r^{d-r}$

Combining, this gives Eqn. (32).

Consider the sum in Eqn. (32). The ratio of the $r+1$ th term to the $r$th
term, for $r=1,2,\ldots,d-1$, is

$\frac{d\left\lVert{a}\right\rVert_{2}^{2}}{(r+1)K^{2}C}\cdot\left(\frac{d-r+1}{d-r}\right)\cdot\frac{(r+1)^{d-r-1}}{r^{d-r}}\geq\frac{d\left\lVert{a}\right\rVert_{2}^{2}}{2(r+1)^{2}K^{2}C}\geq\frac{4d^{2}}{2(r+1)^{2}}\geq
2\enspace.$

Hence, the sum in Eqn. (32) is a geometrically increasing sequence with common
ratio at least 2. The sum is therefore bounded above by 2 $\times$ the final
term, that is,

$\displaystyle\mathbf{E}\left[(Z\bar{Z})^{d}\right]$ $\displaystyle\leq
2\left(\frac{d\left\lVert{a}\right\rVert_{2}^{2}}{C}\right)^{d}\enspace.$

For $r\in[2s]$, let $\chi_{rij}$ be an indicator variable that is 1 if
$h_{r}(i)=h_{r}(j)$ and is 0 otherwise. For $j\in[n]$, let $\hat{x}_{j}$ be an
estimate for $x_{j}$ obtained using independent means (e.g., CountSketch).

For $i\in[n]$ and $r\in[2s]$, let $X_{ri}$ denote the estimate for $x_{i}$
returned from table $r\in R(i)$. That is,

$\displaystyle
X_{ri}=T[h_{r}(i)]\cdot\overline{\omega_{r}(i)}\cdot\textrm{sgn}(\hat{x}_{i})=\lvert
x_{i}\rvert+\sum_{j\neq
i}x_{j}\omega_{r}(j)\overline{\omega_{r}(i)}\chi_{rij}\textrm{sgn}(\hat{x}_{i})$
(33)

assuming $\textrm{sgn}(\hat{x}_{i})=\textrm{sgn}(x_{i})$. We denote this as
$X_{ri}=\lvert x_{i}\rvert+Z_{ri}$, where, for $r\in R(i)$,

$\displaystyle Z_{ri}=\sum_{j\neq
i}x_{j}\omega_{r}(j)\overline{\omega_{r}(i)}\chi_{rij}\textrm{sgn}(\hat{x}_{i})\enspace.$
(34)

Here, $Z_{ri}$ is the error in the estimation of $\lvert x_{i}\rvert$ from
table $T_{r}$, $r\in R(i)$. Therefore,

$\displaystyle X_{i}=\frac{1}{\lvert R(i)\rvert}\sum_{r\in R(i)}X_{ri}=\lvert
x_{i}\rvert+\frac{1}{\lvert R(i)\rvert}\sum_{r\in R(i)}Z_{ri}=\lvert
x_{i}\rvert+Z_{i}\enspace.$ (35)

where, $Z_{i}$ is the average of the $Z_{ri}$’s, that is,

$\displaystyle Z_{i}=\frac{1}{\lvert R(i)\rvert}\sum_{r\in R(i)}Z_{ri}$ (36)

Let

$\displaystyle Z^{\prime}_{ri}=\sum_{j\neq i}x_{j}\omega_{r}(j)\chi_{rij}$
(37)

which gives

$\displaystyle
Z_{ri}=Z^{\prime}_{ri}\overline{\omega_{r}(i)}\textrm{sgn}(\hat{x}_{i})\enspace.$
(38)

Define

$\displaystyle Z^{\prime}_{i}=\sum_{r\in R(i)}Z^{\prime}_{ri}\enspace.$ (39)

Let goodest define the event $\forall
i\in[n],\lvert\hat{x}_{i}-x_{i}\rvert\leq\left(\frac{F_{2}^{\text{res}}\left({2C}\right)}{2C}\right)^{1/2}$.

###### Lemma 30

[Restatement of Lemma 9.]Suppose $d=O(\log n)$, $s\geq 300\log(n)$ and $s\geq
20d$. Let nocollision$(i)$ hold. Let $\rho=\lvert R(i)\rvert$ be the number of
tables in AvgEstl structure where $i$ does not collide with the
$\overline{\textsc{Topk}}$$(C_{l})$ items and $l$ is the level of discovery of
$i$. Let $\mathcal{H}_{i}$ be the event
$\mathcal{G}\wedge\textsc{nocollision}(i)\wedge\textsc{goodest}(i)$. We have
that,

$\displaystyle\mathbf{E}\left[((X_{i}-\lvert
x_{i}\rvert)^{d}(\overline{X_{i}}-\lvert
x_{i}\rvert)^{d}\mid\mathcal{H}_{i}\right]\leq
2\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(\rho/9)C}\right)^{d},\text{
and }$ $\displaystyle\text{Pr}\left[\lvert X_{i}-\lvert
x_{i}\rvert\rvert>2\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(s/9)C}\right)^{1/2}\mid\mathcal{H}_{i}\right]<2^{-2d+1}\enspace.$

  * Proof:  [Proof of Lemma 30.]

From [Gan12] (Lemma 1b), we have conditional on goodest(i), that,
$F_{2}^{\text{res}}\left({\overline{\textsc{Topk}}(2C)}\right)\leq
9F_{2}^{\text{res}}\left({2C}\right)$. Consider the vector
$x_{[n]\setminus\overline{\textsc{Topk}}(2C)}$. Then, by Lemma 1(a) of
[Gan12], we have

$\displaystyle\left\lVert{x_{[n]\setminus\overline{\textsc{Topk}}(2C)}}\right\rVert_{\infty}\leq(1+\sqrt{2})\left(\frac{F_{2}^{\text{res}}\left({2C}\right)}{2C}\right)^{1/2}\enspace.$
(40)

From Eqn. (33), we have
$\mathbf{E}\left[X_{ri}\mid\mathcal{H}_{i}\right]=\lvert x_{i}\rvert$, and
hence, from Eqn. (35), that $\mathbf{E}\left[X_{i}\right]=\lvert x_{i}\rvert$.
Let $\rho=\lvert R(i)\rvert$. Therefore,
$X_{i}-\mathbf{E}\left[X_{i}\right]=Z_{i}$, and

$\displaystyle X_{i}-\mathbf{E}\left[X_{i}\mid\mathcal{H}_{i}\right]$
$\displaystyle=\rho^{-1}\sum_{r\in R(i)}Z_{ri}$ by Eqn. (35)
$\displaystyle=\rho^{-1}\sum_{r\in
R(i)}Z^{\prime}_{ri}\overline{\omega_{r(i)}}\textrm{sgn}(\hat{x}_{i})$ by Eqn.
(37).

Therefore,

$\displaystyle\mathbf{E}\left[Z_{i}^{d}\overline{Z_{i}}^{d}\mid\mathcal{H}_{i}\right]$
$\displaystyle=\mathbf{E}\left[(X_{i}-\mathbf{E}\left[X_{i}\mid\mathcal{H}_{i}\right])(\overline{X_{i}-\mathbf{E}\left[X_{i}\mid\mathcal{H}_{i}\right]})^{d}\mid\mathcal{H}_{i}\right]$
$\displaystyle=\rho^{-2d}\mathbf{E}\left[\left(\sum_{r\in
R(i)}Z^{\prime}_{ri}\overline{\omega_{r}(i)}\right)^{d}\left(\sum_{r\in
R(i)}\overline{Z^{\prime}_{ri}}\omega_{r}(i)\right)^{d}\mid\mathcal{H}_{i}\right]$
$\displaystyle=\rho^{-2d}\mathbf{E}\left[\left(\sum_{r\in R(i)}\sum_{j\neq
i}x_{j}\omega_{r}(j)\overline{\omega_{r}(i)}\chi_{rji}\right)^{d}\left(\sum_{r\in
R(i)}\sum_{j\neq
i}x_{j}\overline{\omega_{r}(j)}\omega_{r}(i)\chi_{rji}\right)^{d}\biggl{|}\mathcal{H}_{i}\right]$
$\displaystyle=\rho^{-2d}\sum_{\begin{subarray}{c}\sum_{r\in R(i)}\sum_{j\neq
i}e_{rj}=d\\\ e_{rj}\text{'s}\geq
0\end{subarray}}\binom{d}{e_{11},\ldots,e_{\rho
n}}^{2}\prod_{\begin{subarray}{c}r\in R(i)\\\
j\in[n]\setminus\overline{\textsc{Topk}}(C)\end{subarray}}x_{j}^{2e_{rj}}\text{Pr}\left[\bigwedge_{(r,j):e_{rj}\geq
1}\chi_{rij}=1\mid\mathcal{H}_{i}\right]$
$\displaystyle=\rho^{-2d}\mathbf{E}\left[(Z^{\prime}_{i}\overline{Z^{\prime}_{i}})^{d}\mid\mathcal{H}_{i}\right]\enspace.$
(41)

from Eqn. (39) defining $Z^{\prime}_{i}$. In this calculation, we have used
that
$\mathbf{E}\left[(\omega_{u}(j))^{e_{u}}(\overline{\omega_{u}(j)})^{g_{u}}\right]=0$
unless $e_{u}=g_{u}$ (this holds irrespective of the conditioning on
$\mathcal{H}_{i}$, since the family $\omega$ is independent of the other
random variables that define $\mathcal{H}_{i}$.

We can now apply Lemma 8 to obtain a bound on
$\mathbf{E}\left[(Z^{\prime}_{i}\overline{Z^{\prime}_{i}})^{d}\right]$,
conditional on goodest(i) and nocollision(i). Let $a$ be the vector with
$\rho=\lvert R(i)\rvert$ copies of the vector
$x_{[n]\setminus(\overline{\textsc{Topk}}(2C)\cup\\{i\\})}$. Thus, $a$ is a
$\rho n$-dimensional vector, with zeros in all coordinates corresponding to
$i$ and elements of $\overline{\textsc{Topk}}(2C)$. Hence,

$\left\lVert{a}\right\rVert_{2}^{2}=\rho\left\lVert{x_{[n]\setminus\overline{\textsc{Topk}}(2C)}}\right\rVert_{2}^{2}\geq\rho
F_{2}^{\text{res}}\left({2C}\right)\enspace.$

Further, as shown in [Gan15], for any set of
$S\subset[n]\setminus(\overline{\textsc{Topk}}(C)\cup\\{i\\})$,

$\text{Pr}\left[\wedge_{j\in
S}\chi_{rij}=1\mid\textsc{nocollision}(i)\right]=(16C)^{-\lvert S\rvert}(1\pm
n^{-\Omega(1)})\enspace.$

Thus, the same holds conditional on $\mathcal{H}_{i}$.

Now

$\displaystyle
4d\left\lVert{a}\right\rVert_{\infty}^{2}(16C)\leq\frac{4d(1+\sqrt{2})^{2}F_{2}^{\text{res}}\left({2C}\right)(16C)}{(2C)}\leq(200)dF_{2}^{\text{res}}\left({2C}\right)\leq\rho
F_{2}^{\text{res}}\left({2C}\right)\leq\left\lVert{a}\right\rVert_{2}^{2}$

since, $\rho\geq s\geq 300\log(n)$, the premise of Lemma 8 holds.

It follows from Lemma 8 that

$\displaystyle\mathbf{E}\left[(Z^{\prime}_{i}\overline{Z^{\prime}_{i}}))^{d}\mid\mathcal{H}_{i}\right]\leq
2\left(\frac{d\rho(9)F_{2}^{\text{res}}\left({2C}\right)}{C}\right)^{d}\enspace.$
(42)

and, hence from Eqn. (A.2), that

$\displaystyle\mathbf{E}\left[(Z_{i}\overline{Z_{i}})^{d}\right]\leq
2\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(\rho/9)C}\right)^{d}$ (43)

Therefore,

$\text{Pr}\left[\bigl{\lvert}X_{i}-\mathbf{E}\left[X_{i}\right]\bigr{\rvert}>T\mid\mathcal{H}_{i}\right]=\text{Pr}\left[\lvert
Z_{i}\rvert>T\mid\mathcal{H}_{i}\right]=\text{Pr}\left[(Z_{i}\overline{Z_{i}})^{d}>T^{2d}\mid\mathcal{H}_{i}\right]\\\
\leq\frac{\mathbf{E}\left[(Z_{i}\bar{Z_{i}})^{d}\mid\mathcal{H}_{i}\right]}{T^{2d}}\leq
2\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(\rho/9)CT^{2}}\right)^{d}\enspace.$

Letting $\rho\geq s$ and since,
$\mathbf{E}\left[X_{i}\mid\textsc{goodest}(i),\textsc{nocollision}(i)\right]=\lvert
x_{i}\rvert$, we have,

$\text{Pr}\left[\lvert X_{i}-\lvert
x_{i}\rvert\mid\mathcal{H}_{i}\rvert>2\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(s/9)C}\right)^{1/2}\right]\leq
2^{-2d+1}$

The following lemma uses a standard property of $q$th roots of unity, that
$\mathbf{E}\left[\omega^{v}\right]=0$, where, $\omega$ is a randomly chosen
root of $x^{q}=1$ and $0\leq v\leq q-1$.

###### Lemma 31

Assume that the family $\\{\omega(j)\\}$ are $k+1$-wise independent and
randomly chosen roots of $x^{q}=1$, where, $q>k+1$ is any integer. Then, for
$v=1,2\ldots,k$, $\mathbf{E}\left[Z_{i}^{v}\right]=0$.

  * Proof:  [Proof of Lemma 31] For $v=1,2,\ldots,k$ and $l\in R(i)$, we have,

$\displaystyle\mathbf{E}\left[Z_{li}^{v}\right]$
$\displaystyle=\textrm{sgn}^{v}(\hat{x}_{i})\mathbf{E}\left[\overline{\omega_{li}}^{v}\right]\mathbf{E}\left[\left(\sum_{j\neq
i}x_{j}\omega_{lj}\chi_{lij}\right)^{v}\right]$
$\displaystyle=\textrm{sgn}^{v}(\hat{x}_{i})\cdot
0\cdot\left(\sum_{r=1}^{v}\sum_{e_{1}+\ldots+e_{r}=v,e_{j}^{\prime}s\geq
1}\binom{v}{e_{1},\ldots,e_{r}}\sum_{1\leq j_{1}<\ldots<j_{r}\leq
n,j_{u}^{\prime}s\neq
i}\frac{1}{C^{r}}\prod_{u=1}^{r}x_{j_{u}}^{e_{u}}\mathbf{E}\left[\omega_{li}^{e_{u}}\right]\right)$
$\displaystyle=0\cdot 0=0$

since, each of the terms $\mathbf{E}\left[\omega_{li}^{e_{u}}\right]=0$.

Therefore, for $v=1,2,\ldots,k$,
$\mathbf{E}\left[Z_{i}^{v}\right]=\mathbf{E}\left[\left(\sum_{l=1}^{s}Z_{li}\right)^{v}\right]=0$,
since, the $Z_{li}$’s are independent across the $l$’s.

######  Lemma 32 (Restatement of Lemma 10)

Let $\\{\omega_{r}(j)\\}_{j\in[n]}$ be a family of $d+1$-wise independent
variables, where, $d=O(\log n)$, $s\geq 300\log(n)$ and $s\geq 72d$. Further
suppose that $\lvert
x_{i}\rvert>8\left(\frac{F_{2}^{\text{res}}\left({2C}\right)}{2C}\right)^{1/2}$.
Then, with probability $1-n^{-\Omega(1)}$,

$\bigl{\lvert}\mathbf{E}\left[X_{i}^{p}\right]-\lvert
x_{i}\rvert^{p}\mid\mathcal{H}_{i}\bigr{\rvert}\leq\lvert
x_{i}\rvert^{p}n^{-\Omega(1)}\enspace.$

  * Proof:  We have, $X_{i}=\lvert x_{i}\rvert+Z_{i}$, where, $Z_{i}=\frac{1}{\rho}\sum_{r\in R(i)}Z_{ri}$ and
$Z_{ri}=\sum_{j\neq
i}x_{j}\omega_{r}(j)\overline{\omega_{r}(i)}\chi_{rij}\textrm{sgn}(x_{i})$. By
Lemma 9,

$\text{Pr}\left[\lvert
Z_{i}\rvert>2\left(\frac{dF_{2}^{\text{res}}\left({2C}\right)}{(s/9)C}\right)^{1/2}\mid\mathcal{H}_{i}\right]\leq
2^{-2d+1}\enspace.$

Since $s\geq 72d$, $(s/9)/d\geq 8$. Also, since, $d=\Theta(\log n)$,
$2^{-2d+1}=n^{-\Omega(1)}$. Therefore,

$\text{Pr}\left[\lvert
Z_{i}\rvert>\left(\frac{F_{2}^{\text{res}}\left({2C}\right)}{2C}\right)^{1/2}\mid\mathcal{H}_{i}\right]\leq
n^{-\Omega(1)}\enspace.$

Therefore,

$\displaystyle\mathbf{E}\left[X_{i}^{p}\mid\mathcal{H}_{i}\right]$
$\displaystyle=\mathbf{E}\left[\left(\lvert
x_{i}\rvert+Z_{i}\right)^{p}\mid\mathcal{H}_{i}\right]$ $\displaystyle=\lvert
x_{i}\rvert^{p}\mathbf{E}\left[\left(1+\frac{Z_{i}}{\lvert
x_{i}\rvert}\right)^{p}\right]$ $\displaystyle=\lvert
x_{i}\rvert^{p}\left(\sum_{v=0}^{k}\binom{p}{v}\frac{\mathbf{E}\left[Z_{i}^{v}\mid\mathcal{H}_{i}\right]}{\lvert
x_{i}\rvert^{v}}\pm\left\lvert\binom{p}{k+1}\right\rvert 8^{-(k+1)}\right)$
$\displaystyle=\lvert
x_{i}\rvert^{p}\left(1\pm\left(\frac{p}{k+1}\right)^{\lfloor
p\rfloor}8^{-(k+1)}\right)$ $\displaystyle=\lvert x_{i}\rvert^{p}\left(1\pm
n^{-\Omega(1)}\right)$

The second to last step follows, since for $v=1,2,\ldots,k$,
$\mathbf{E}\left[(Z_{i})^{v}\right]=0$, by Lemma 31. The error term is bounded
by an application of Taylor’s remainder term in the expansion of $(1+z)^{p}$,
for $\lvert z\rvert\leq 1/8$. We have also used the fact that for $k>p$,
$\bigl{\lvert}\binom{p}{k+1}\bigr{\rvert}\leq\left(\frac{p}{k+1}\right)^{\lceil
p\rceil}$.

###  A.3 Analysis

For $i\in[n]$, let $x_{li}$ be an indicator variable that is 1 iff
$i\in\mathcal{S}_{l}$. For uniformity of notation, let $X_{i}$ denote
$\lvert\hat{x}_{i}\rvert$ when $l_{d}(i)=L$ and otherwise, let its meaning be
unchanged.

Let $z_{il}$ be an indicator variable that is 1 if $i\in\bar{G}_{l}$ and 0
otherwise.

We can now write $\hat{F}_{p}$ as follows.

$\displaystyle\hat{F}_{p}$
$\displaystyle=\sum_{l=0}^{L}\sum_{\begin{subarray}{c}i\in\bar{G}_{l}\\\
l_{d}(i)<L\end{subarray}}2^{l}X_{i}^{p}=\sum_{i\in[n]}Y_{i},\text{ where,
}Y_{i}=\sum_{l^{\prime}=0}^{L}2^{l^{\prime}}z_{il^{\prime}}X_{i}^{p}\enspace.$
(44)

###  A.4 Analysis of ghss sampled estimate

We now consider the analysis of the ghss sampled estimate. Without loss of
generality, for $l_{d}(i)=l$, let $\lvert R_{l}(i)\rvert=s$.

Let nocollision be defined as the event
$\wedge_{i\in[n]}\textsc{nocollision}(i)$. This means that, for each
$i\in[n]$, (i) if $i\in G_{l}$ and $i$ maps to the random substream
$\mathcal{S}_{l}$, then, $\textsc{nocollision}(i)$ holds at level $l_{d}(i)$,
and (ii) if $i\in S_{j}$ and $\textsc{nocollision}(i)$ holds at the shelf
indexed $j_{d}(i)$, namely the shelf at which the item is discovered (the
largest shelf index). Let $\textsc{nocollision}(J)$ denote $\wedge_{j\in
J}\textsc{nocollision}(j)$. Analogously, for a set $J$, define
$\textsc{goodest}(J)$. For a set $J$, let $\mathcal{H}_{J}$ be the event

$\mathcal{H}_{J}=\mathcal{G}\wedge\textsc{nocollision}(J)\wedge\textsc{goodest}(J)\enspace.$

###### Lemma 33

Let $r\in[0,\ldots,d],s\in\max(0,1-r),\ldots,d-r$ and
$t\in\max(0,1-r),\ldots,d-r$. Let
$\\{i_{1},\ldots,i_{r}\\}\cup\\{j_{1},\ldots,j_{s}\\}\cup\\{k_{1},\ldots,k_{t}\\}\subset\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$
such that $\\{i_{1},\ldots,i_{r}\\}$, $\\{j_{1},\ldots,\allowbreak j_{s}\\}$
and $\\{k_{1},\ldots,k_{t}\\}$ are pair-wise disjoint. Let
$(e_{1},\ldots,e_{r+s})$ and $(g_{1},\ldots,g_{r+t})$ be positive integer
vectors. Suppose $A=\\{v\mid v\in[s],e_{r+v}=1\\}$ and $B=\\{w\mid
w\in[t],g_{r+w}=1\\}$. Let the family $\\{\omega_{lr}(i)\\}_{i}$, be
$k+1=O(\log n)$-wise independent for each fixed $l\in[0,L]$ and $r\in[2s]$,
and is independent across $l\in[0,L]$ and $r\in[2s]$. Let
$\gamma=\textrm{exp}\left\\{{-\Omega(s)}\right\\}=n^{-\Omega(1)}$. Then,

$\displaystyle\mathbf{E}\left[\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}_{J}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}_{J}\right])^{g_{u}}\prod_{v=1}^{s}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])^{e_{r+v}}\right.$
$\displaystyle\left.\hskip
72.26999pt\prod_{w=1}^{t}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])^{g_{r+w}}|\mathcal{H}_{J}\right]$
$\displaystyle\leq\gamma^{\lvert A\rvert+\lvert B\rvert}(1\pm\gamma)^{(\lvert
A\rvert+\lvert B\rvert)^{2}}\prod_{v\in A}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in B}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\mathbf{E}\left[\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}_{J}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}_{J}\right])^{g_{u}}\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])^{e_{r+v}}\right.$
$\displaystyle\left.\hskip 72.26999pt\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])^{g_{r+w}}\mid\mathcal{H}_{J}\right]$

  * Proof:

We have, $\mathbf{E}\left[Y_{s}\mid\mathcal{H}_{J}\right]=\lvert
x_{s}\rvert^{p}(1\pm n^{-\Omega(1)}))$, for
$s\in\\{i_{1},\ldots,i_{r}\\}\cup\\{j_{1},\ldots,j_{s}\\}\cup\\{k_{1},\ldots,k_{t}\\}$.
Let $\gamma=n^{-\Omega(1)}$. Then,