We present two new local differentially private algorithms for frequency estimation.
One solves the fundamental frequency oracle problem; the other solves the well-known heavy hitters identification problem. Consistent with prior art, these are randomized algorithms. As a function of failure probability $\beta$, the former achieves optimal worst-case estimation error for every $\beta$, while the latter is optimal when $\beta$ is at least inverse polynomial in $n$, the number of users.
In both algorithms, server running time is $\tilde{O}(n)$ while user running time is $\tilde{O}(1)$.
Our frequency-oracle algorithm achieves lower estimation error than the prior works of [Bassily et al., 2017] (NeurIPS [Bassily et al., 2017]).
On the other hand, our heavy hitters identification method is as easily implementable as  ([Bassily et al., 2017], [Bassily et al., 2017]) and has superior worst-case error, by a factor of $\Omega(\sqrt{\log n})$.

§ INTRODUCTION

Local differential privacy () is a popular model for collecting data privately [Erlingsson et al., 2014, Fanti et al., 2016, Team, 2017, Tang et al., 2017, Ding et al., 2017]. In this model, there is a server and a set $\mcalU{}$ of $n$ users, each holding an element from some domain $\mcalD{}$. No user $u \in \mcalU{}$ wants to share their data $v^{ (u) } \in \mcalD{}$ directly with the server. To protect sensitive personal information, they run a local randomizer $\mcalA{}^{ (u) }$ to perturb their data. To gather useful statistics, the server aggregates the randomized versions of users' data. The algorithm $A^{ (u) }$ is called differentially private if its output distribution varies little with the input, as defined thus.

Let $\mcalA: \mcalD \rightarrow \mcalY$ be a randomized algorithm mapping an element in $\mcalD{}$ to $\mcalY{}$. $\mcalA$ is called  $\eps$-differentially private if for all $v, v' \in \mcalD$ and all (measurable) $Y \subseteq \mcalY$,

\Pr[ \mcalA (v) \in Y ] \le e^\eps \cdot \Pr [ \mcalA (v') \in Y ]\,.

The parameter $\eps$ characterizes the similarity of the output distributions of $\mcalA (v)$ and $\mcalA (v')$ and is called the privacy budget.

We focus on the fundamental problem of frequency estimation in the setting, which is useful in many security-related scenarios. For example, Google deployed RAPPOR [Erlingsson et al., 2014, Fanti et al., 2016] in the Chrome web browser to learn the frequencies of users’ browser configuration strings. Apple deployed a similar system [Team, 2017, Tang et al., 2017] to identify popular emojis, new words, and media playback preferences etc.  Microsoft deployed mechanisms [Ding et al., 2017] to collect application usage statistics in the Windows Insider Program.

Formally, suppose that $\mcalD{}$ is a finite domain of size $d$. For each $v \in \mcalD{}$, let $f_\mcalU{}[v]$ be the number of users that hold $v$, i.e.,
f_\mcalU{} [ v ] \doteq | \{ u \in \mcalU{} : v^{ (u) } = v \} |.
Aligned with prior art [Bassily and Smith, 2015, Bassily et al., 2017, Bun et al., 2019], we are interested in the following two closely related, but distinct, functionalities of frequency estimation. The relevant parameters are the error threshold, $\lambda$, and the failure probability, $\beta$:

A frequency oracle, denoted as FO, is an algorithm that provides for every $v \in \mcalD{}$, an estimated frequency $\hat f_\mcalU{} [ v ]$, such that $\Pr[ | \hat f_\mcalU{} [ v ] - f_\mcalU{} [ v ] | \ge \lambda ] \le \beta$.

A succinct histogram, denoted as S-Hist, is a set of (element, estimate) pairs $\subseteq \mcalD{} \times \R$, of size $O( n / \lambda)$, such that with probability at least $1 - \beta$: i) $\forall v \in \mcalD{}$, if $f_\mcalU{} [v] \ge \lambda$, $(v, \hat f_\mcalU{} [v] )$ belongs to the set; ii) and if $(v, \hat f_\mcalU{} [ v] )$ is in the set, then $| f_\mcalU{} [v] - \hat f_\mcalU{} [v] | \le \lambda$.

Each element in the Succinct Histogram set is called a heavy hitter.
For a fixed $\eps \le 1$, the goal of algorithm design for both problems in model is to minimize the error threshold $\lambda$, while limiting server/user running time, memory usage, and communication cost etc.

Recently, in an influential paper, [Bassily et al., 2017] [Bassily et al., 2017] proposed two the state-of-the-art frequency oracles, and . These algorithms exhibit low time complexity and memory usage: with server running time $\tilde O(n)$ and memory usage $\tilde O(\sqrt{n})$, user running time $\tilde O(1)$ and memory usage $\tilde O(1)$, each user reports only $1$ bit.
However, these algorithms guarantee only an error of $O ( (1 / \eps) \cdot \sqrt{ n \log ( {n} / {\beta} ) } )$, which is sub-optimal [Bun et al., 2019].

[Bassily et al., 2017] also provided two new succinct histogram algorithms  and  [Bassily et al., 2017, Bassily et al., 2020], which have the same server/user running time and memory usage as their frequency oracles (under the $\tilde O$ notation). Each user reports $O(1)$ bits.
The two algorithm apply different techniques.
The former guarantees error $O ( (1 / \eps ) \cdot  \sqrt{ n \cdot ( \log d ) \cdot \log (n / \beta)  } )$ and the latter guarantees error $O ( (1 / \eps ) \cdot  \sqrt{ n \cdot ( \log (d / \beta) ) \cdot \log (1 / \beta)  } )$, which is improved to $O( (1 / \eps ) \cdot  \sqrt{ n \cdot \log (d / \beta) } )$ by the  algorithm [Bun et al., 2019].
Among the three algorithms, due to its simplicity, only  is implemented in [Bassily et al., 2017].

Therefore, it is of independent interest and remains open to the research community whether the error of  can also be reduced.

Comparison of our frequency oracle ($\oracle$) and succinct histogram ($\ours$) algorithms with the state-of-the-art, where `Mem' stands for `Memory', `Rand' for `Randomness' (the number of random bits required), and `Comm' for `Communication', the number of bits sent.

1c| c]@c@Server
1c| c]@c@User
1c| c]@c@Server
1c| c]@c@User
1c| c]@c@Public
/ User
1c| c]@c@Comm
/ User
1c| c]@c@Worst-Case

1c| $\oracle$
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n} )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot \ln \frac{1}{\beta} } \right)$
1c| $\hrr$ [Nguyên et al., 2016, Cormode et al., 2019]
1c|$\tilde O(d)$
1c|$\tilde O(1)$
1c|$\tilde O( d )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot \ln \frac{1}{\beta} } \right)$
1c| $\freqOracle$ [Bassily et al., 2017]
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n} )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot \ln \frac{n}{\beta} } \right)$
1|c|-4* [origin=c]90$\qquad \textbf{FO}$
1c| $\hashtogram$ [Bassily et al., 2017]
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n} )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot \ln \frac{n}{\beta} } \right)$

1c| $\ours$
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n} )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot (\ln d) \cdot \frac{\ln ( n / \beta ) }{ \ln n } } \right)$
1c| $\algoTreeHist{}$ [Bassily et al., 2017]
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n } )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot ( \ln d ) \cdot \ln \frac{n}{\beta} }  \right)$
1c| c]@c@$\textbf{PrivateExpander}-$
$\textbf{Sketch}$ [Bun et al., 2019]
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n} )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot \ln \frac{d}{\beta} } \right)$
1|c|-5* [origin=c]90$\qquad \textbf{S-Hist}$
1c| $\algoBitstogram{}$ [Bassily et al., 2017]
1c|$\tilde O(n)$
1c|$\tilde O(1)$
1c|$\tilde O( \sqrt{n} )$
1c|$\tilde O(1)$
1c|$\tilde O(1)$
1c|$O \left( \frac{1}{ \eps } \sqrt{ n \cdot ( \ln \frac{d}{\beta} ) \cdot \ln \frac{1}{\beta} }  \right)$

Our Contributions.
In this paper, we introduce the martingale method [Motwani and Raghavan, 1995, Mitzenmacher and Upfal, 2017] into the the analysis of frequency oracle algorithms, and design a new algorithm, called . It achieves the same asymptotic server/user running time and memory usage as and [Bassily et al., 2017, Bassily et al., 2020], but guarantees an optimal estimation error $O( (1 / \eps) \cdot \sqrt{ n \log ( 1 / {\beta} ) } )$.

We also provide a succinct histogram algorithm based on a new prefix search tree, , which improves on .
Our algorithm exploits the benefit of the fast Hadamard transform, which enables us to design a prefix tree with large fanout and to explore more elements without increasing the running time.
improves the worst-case error of  to $O ( (1 / \eps ) \cdot  \sqrt{ n \cdot (\log d ) \cdot ( {\log (n / \beta) }) \ / \ ( { \log n } ) } )$, while keeping the all other complexities the same.
In the case where $\beta = 1 / n^{ O(1) }$, the error of our algorithm matches the lower bound [Bassily et al., 2017, Bun et al., 2019].

Table <ref> details the comparison of and with the prior state of the art.

Local differential privacy offers a privacy guarantee to users, as individuals.
We acknowledge that the calculation of a Succinct Histogram, and the finding of heavy hitters, allows identification of large minority groups in a population.
So the reassurance of individual privacy might not protect against group identification, and could well be a
potential negative societal impact.

§ RELATED WORK

[Bun et al., 2019] [Bun et al., 2019] proves a lower bound
\lambda \in \Omega ( (1 / \eps) \cdot \sqrt{ n \log ( {d} / {\beta} ) } )
for the succinct histogram problem, which also implies a lower bound $\lambda \in \Omega ( (1 / \eps) \cdot \sqrt{ n \log ( 1 / {\beta} ) } )$ for the frequency oracle problem [Let $\beta' = \beta / d$ be the failure probability of the frequency oracle problem. Were we to have $\lambda \in  o( (1 / \eps) \cdot \sqrt{ n \log ( 1 / {\beta'} ) } )$ for the frequency oracle, we could query it for the frequency of all elements in the domain. By a union bound, we could thus construct a succinct histogram with failure probability $\beta$ and with error $o( (1 / \eps) \cdot \sqrt{ n \log ( d / {\beta} ) } )$. A contradiction.].

We briefly document the development of frequency oracles in recent years.
In [Bassily and Smith, 2015], [Bassily and Smith, 2015] [Bassily and Smith, 2015] proposed a frequency oracle that achieves error $O( (1 / \eps) \cdot \sqrt{ n \log ( 1 / {\beta} ) } )$.[The analysis in the paper gives an error bound of $O( (1 / \eps) \cdot \sqrt{ n \log ( d / {\beta} ) } )$ because of union bound over all elements. If only one element is queried, the error is $O( (1 / \eps) \cdot \sqrt{ n \log ( 1 / {\beta} ) } )$ with probability at least $1 - \beta$.]
However, it needs $\tilde O(n^2)$ random bits to describe a random matrix,  and answers a query in $O(n)$ time.
In [Bassily et al., 2017], a similar version with simplified analysis, called ExplicitHist, was studied by [Bassily et al., 2017]'s [Bassily et al., 2017].
ExplicitHist achieves the same estimation error, but requires only $\tilde O(1)$ random bits to describe the random matrix.
It answers a query in $O(n)$ time.
Other optimizations are proposed.
First documented in [Nguyên et al., 2016], and widely used in literature [Bassily et al., 2017, Team, 2017, Cormode et al., 2019], the algorithm uses the Hadamard matrix to replace the random matrix without increasing the estimation error.
The matrix does not need to be generated explicitly and each of its entries can be computed in $\tilde O(1)$ time when needed.
The answers a query in $O( \min \{n, d \} )$ times, or with pre-processing time $\tilde O(d)$, answers each query in $\tilde O(1)$ time.
Finally, [Bassily et al., 2017] [Bassily et al., 2017] also applied Count-Sketch [Charikar et al., 2002] to compress the domain of the elements. Their frequency oracles, and , have server running time $\tilde O(n)$ and memory usage $\tilde O( \sqrt{n} )$. Unfortunately, due to invoking the Poisson approximation technique [Mitzenmacher and Upfal, 2017], these algorithms have inferior estimation error of $O( (1 / \eps) \cdot \sqrt{ n \log ( {n} / {\beta} ) } )$.

For the succinct histogram problem, [Bassily and Smith, 2015] [Bassily and Smith, 2015] proposed the first polynomial-time algorithm that has worst-case error $O( (\log^{1.5} ( {1} / {\beta} ) ) \cdot (1 / \eps ) \cdot  \sqrt{ n \log d})$.
However, it has server running time $\tilde O( n^{2.5} )$ and user time $\tilde O(n^{1.5} )$, which is not practical.
In [Bassily et al., 2017], [Bassily et al., 2017] [Bassily et al., 2017] proposed two improved algorithms,  and , which
involve different techniques.  searches for the heavy hitters via a prefix tree;
hashes elements into a smaller domain and identifies a noisy version of the heavy hitters.
The recovery of the true heavy hitters relies on error-correcting codes.
The former algorithm has error $O ( (1 / \eps ) \cdot  \sqrt{ n \cdot ( \log d ) \cdot \log (n / \beta)  } )$, while the latter has error $O ( (1 / \eps ) \cdot  \sqrt{ n \cdot ( \log (d / \beta) ) \cdot \log (1 / \beta)  } )$; each achieves almost-optimal error, but  is inferior to  by a factor of $\sqrt{ \log n }$. Importantly, each algorithm has server time $\tilde O(n)$ and user time $\tilde O(1)$. In [Bun et al., 2019], [Bun et al., 2019] [Bun et al., 2019] further refined  based on a list-recoverable code. Their new algorithm,  [Bun et al., 2019], achieved an optimal error of $O( (1 / \eps ) \cdot  \sqrt{ n \cdot \log (d / \beta) } )$.

§ PRELIMINARIES

A sequence of random variables $Y_0, \ldots, Y_n$ is a martingale with respect to the sequence $X_0, \ldots, X_n$ if, for all $i \ge 0$, the following conditions hold: i) $Y_i$ is a function of $X_0, \ldots, X_i$; ii) $\E[ |Y_i| ] < \infty$; and iii) $\E[ Y_{i + 1} \mid X_0, \ldots, X_i] = Y_i.$

The Hadamard matrix is defined recursively for a parameter, $m$, that is a power of two: $\small \mrmH_1 = [1]$ and
\mrmH_m =
\begin{bmatrix}
\mrmH_{ m / 2}     &   \mrmH_{ m / 2} \\
\mrmH_{ m / 2}     &   -\mrmH_{ m / 2}
\end{bmatrix}
Appendix <ref> includes some examples.

Observe that a Hadamard matrix is symmetric. We list here some other important properties of Hadamard matrix; for completeness, we include proofs in Appendix <ref>.

The columns of the Hadamard matrix are mutually orthogonal.

For $0 \le i, j < m$, the $(i + 1,j + 1)$-th entry $\mrmH_m[i + 1, j + 1]$ of the Hadamard matrix can be computed in $O( \log m )$ time (both the rows and columns of $\mrmH_m$ are indexed from $1$ to $m$). In particular, let the vectors $(i)_{\log m}, (j)_{\log m} \in \{0, 1\}^{\log m}$ be the $\log m$-bit binary representation of $i$ and $j$, respectively. Then
\mrmH_m[i + 1, j + 1] = (-1)^{ \left< (i)_{\log m}, (j)_{\log m} \right> },
where $\left< (i)_{\log m}, (j)_{\log m} \right>$ is the dot product between $(i)_{\log m}$ and $(j)_{\log m}$.

[Fast Hadamard Transform]
For all $\pmbx{} \in \R^m$, there is a standard divide-and-conquer algorithm that computes the multiplication $\mrmH_m \,\pmbx{}$ (equivalently, $\mrmH_m^T \pmbx{}$, as $\mrmH_m$ is symmetric) in $O(m \log m)$ time and $O(m)$ memory.

§ FREQUENCY ORACLE

In this section, we discuss the problem of frequency estimation for a set $\mcalU{}$ of users, each of which holds an element from some finite domain $\mcalD{}$.

Our main vehicle for solving this problem is the Hadamard matrix, and our main result is as follows:

Let $\mcalU{}$ be a set of users, each holding an element from some finite domain $\mcalD{}$. Let $\eps \in (0, 1)$ be the privacy parameter and $\beta' \in (0, 1)$ be the specified failure probability. There exists an $\eps$-locally differentially private frequency oracle that, for each query element $v \in \mcalD{}$, with probability at least $1 - \beta'$, returns an frequency estimate $\hat f_\mcalU{} [ v ]$ satisfying

\left|  \hat f_\mcalU{} [ v ] - f_\mcalU{} [ v ] \right| \in O \left( \frac{1}{\eps} \cdot \sqrt{ | \mcalU{} | \cdot \ln \frac{1}{\beta'} } \right).

Each user in $\mcalU{}$ requires $\tilde O(1)$ memory, takes $\tilde O(1)$ running time and reports only $1$ bit to the server. The server uses processing memory of size $\tilde O(\sqrt{ | \mcalU{} | } )$, has $\tilde O( | \mcalU{} | )$ processing time, and answers each query in $\tilde O(1)$ time. The $\tilde O$ notation hides logarithmic factors in $| \mcalU{} |$, $| \mcalD{} |$ and $1 / \beta'$.

§.§ Hadamard Randomized Response

Before introducing our algorithm, in this section we review an

algorithm based on the Hadamard matrix, called the Hadamard Randomized Response () [Nguyên et al., 2016, Cormode et al., 2019].

The algorithm achieves every property of Algorithm as specified in Theorem <ref>, except that

the server has processing time $\tilde O( |\mcalU{} | + |\mcalD{}| )$ and memory usage $O(|\mcalD{}|)$.

For completeness, we include a proof in Appendix <ref>.

The algorithm relies on a Hadamard matrix $\mrmH_m$ with $m = 2^{ \lceil \log | \mcalD{} | \rceil }$ (hence $| \mcalD{} | \le m < 2 | \mcalD{} |$ ), and assigns each element $v \in \mcalD{}$ the $v^{\text{th}}$ column of $\mrmH_m$. For a user $u \in \mcalU{}$, it is said to be assigned to the $v^{\text{th}}$ column, if its element $v^{(u)} = v$. The problem of estimating the frequency of a element $v \in \mcalD{}$ reduces to estimating the number of users in $\mcalU{}$ assigned to the $v^{\text{th}}$ column. When the value of $m$ is clear from context, we omit subscript $m$ and write Hadamard matrix $\mrmH_m$ as $\mrmH$.

The client-side algorithm is described in Algorithm <ref>. Each user receives (from the server) a row index $r$ of the Hadamard matrix, and privacy parameter $\eps$. Its own element $v$ is the column index.
It returns the value of $\mrmH{}[r,v]$, but flipped with probability $1 / (e^\eps + 1)$.
Multiplying $\mrmH{}[r,v]$ by a Rademacher random variable $b$ that equals $1$ with probability $e^\eps / (e^\eps + 1)$ and $-1$ with probability $1 / (e^\eps + 1)$ achieves the flip.
It returns the one-bit result to the server.

-Client $\algoHrrClient$

[1]
Row index $r \in [m]$; privacy parameter $\eps$.
Let $v \in \mcalD{}$ be the user's element.

Sample $b \in \{-1, 1 \}$, which is $+1$ with probability $e^\eps / (e^\eps + 1)$.
$\omega \leftarrow b \cdot \mrmH[r,v]$.

The server-side algorithm is described in Algorithm <ref>. Its input comprises the set of users, $\mcalU{}$, their elements' domain, $\mcalD{}$, and privacy parameter $\eps$. The server maintains a vector $\pmbomega{} \in \R^m$, which is initialized with all zeros. For each user $u \in \mcalU{}$, the server samples an integer $r^{ (u) } \in [m]$ independently and uniformly at random. Then it invokes $\algoHrrClient(r^{ (u) }, \eps)$ by sending $r^{(u)}$ and $\eps$ to user $u$.
On receiving user $u$'s response, $\omega^{ (u)}$, the server increases the $( r^{ (u) } )^{\text{th}}$ entry of $\pmbomega$ by $(e^\eps + 1) / (e^\eps - 1) \cdot \omega^{ (u) }$.
Finally, it returns a vector $\hat f_\mcalU{} = \mrmH^T \,\pmbomega{} \in \R^m$. Note that the dimension of $\hat f_\mcalU{}$ is $m$, which could be larger than $|\mcalD{}|$: we use only the first $|\mcalD{}|$ entries of $\hat f_\mcalU{}$.

Via the fast Hadamard transform (Fact <ref>), the server computes $\hat f_\mcalU{} \leftarrow \mrmH^T \,\pmbomega$ (Algorithm <ref>, line 6) in $\tilde O( |\mcalD{} | )$ time. Then for each $v \in \mcalD{}$, if its frequency is queried, the server can return $\hat f_\mcalU{} [v]$ in $O(1)$ time. There is another version of that omits line 6. It has server running time $\tilde O( |\mcalU{}| )$. However, when it answers a frequency query for some $v \in \mcalD{}$, it needs to compute $\hat f_\mcalU{} [v] = (\mrmH^T \,\pmbomega ) [v]$ on the fly, which requires $\tilde O( \min \{ m, | \mcalU{} | \} )$ time.

-Server $\algoHrrServer{}$

[1]
A set of users $\mcalU{}$; element domain $\mcalD{}$; privacy parameter $\eps$.
Set $m \leftarrow 2^{ \lceil \log | \mcalD{} | \rceil }$,  $\pmbomega \leftarrow \{0 \}^m$.
$u \in \mcalU{}$
$r^{ (u)} \leftarrow$ uniform random integer from $[m]$.
$\omega^{ (u)} \leftarrow \algoHrrClient (r^{ (u)}, \eps)$.
$\pmbomega [ r^{ (u) } ] \leftarrow \pmbomega [ r^{ (u) } ] + (e^\eps + 1) / (e^\eps - 1) \cdot \omega^{ (u) }$.
$\hat f_\mcalU{} \leftarrow \mrmH^T \,\pmbomega$.

§.§ [Bassily et al., 2017]'s Approach [Bassily et al., 2017]

In this section, we overview the  [Bassily et al., 2017] algorithm by [Bassily et al., 2017], to explain the core ideas that reduce the server processing time to $\tilde O( | \mcalU{} |)$

and memory usage to $\tilde O ( \sqrt{ | \mcalU{} | } )$, and to explain why their approach leads to sub-optimal estimation error. [Bassily et al., 2017]'s other algorithm  [Bassily et al., 2017] suffers from a similar issue, so we discuss only here.
In the next section, we show how to improve upon and propose the algorithm.

The [Bassily et al., 2017] achieves every property of Algorithm as specified in Theorem <ref>, except that
the estimation error is bounded by $O( (1 / \eps) \cdot \sqrt{ | \mcalU{} | \cdot \ln ( {| \mcalU{} |} / {\beta'} ) } )$.

The  discussed in this section is based on the version of presented in Section <ref>.
The original  of [Bassily et al., 2017] [Bassily et al., 2017] invokes another version of , mentioned in Remark <ref>. It answers a frequency query in $\tilde O(\min \{ m, | \mcalU{} | \} )$ time:
even after applying  domain compression, detailed below, this is still $\tilde O( \sqrt{ | \mcalU{} | } )$ time.
One of our main contributions is the benefit from the fast Hadamard transform for , which leads to $\tilde O(1)$ query time.

Domain Compression. In the algorithm , each $v \in \mcalD{}$ is uniquely assigned the $v^{\text{th}}$ column in $\mrmH{}_m$, which requires setting $m = 2^{ \lceil \log |\mcalD{} | \rceil }$ and leads to server running time $\tilde O(| \mcalD{} | + | \mcalU{} |)$ and memory usage $O(| \mcalD{} |)$.
To reduce the server running time and memory usage, we need a smaller $m$ (we discuss how to set a smaller $m$ later), and to compress the elements' domain from $\mcalD{}$ to $[m]$.
The compression is performed via a pairwise independent hash function $h: \mcalD{} \rightarrow [m]$, mapping
elements in $\mcalD{}$ to $[m]$.
For each $v \in \mcalD{}$, the hash function $h$ maps it to $h(v)$ and assigns it the $h(v)$-th column of $\mrmH_m$. Observe that multiple elements can share the same column.

Each user $u$ in $\mcalD{}$ now holds a new element $h( v^{(u)} )$ in the domain $[m]$.
According to Fact <ref>, the frequencies of the new elements can be estimated by the algorithm, which has server running time $\tilde O(m + | \mcalU{} |)$ and memory usage $O(m)$.
Let $f_{\mcalU{}, h} \in \R^m$ be the frequency vector of the new elements,
and $\hat f_{\mcalU{}, h}$ the estimate of $f_{\mcalU{}, h}$ returned by .

For $v \in \mcalD{}$, $\hat f_{\mcalU{}, h} [ h(v) ]$ is an estimate of $f_\mcalU{} [ v ]$.
By the triangle inequality, the estimation error is bounded by $| \hat f_{\mcalU{}, h} [ h(v) ] - f_{\mcalU{}, h} [ h(v) ]| + | f_{\mcalU{}, h} [ h(v) ] - f_\mcalU{} [ v ]|$.
The first term inherits from the randomness of the algorithm;
the second term is due to hash collisions of $h$.
According to Fact <ref>, the first term is, with probability $1 - \beta'$, bounded by $O( (1 / \eps) \cdot \sqrt{ | \mcalU{} | \cdot \ln ( {1} / {\beta'} ) } )$.
There are two possible ways to bound the second term.

First, we could set $m \in \tilde O( \sqrt{| \mcalU{} |}  / \beta')$.
Via Markov's inequality, with probability $1 - \beta'$, the second term is $\tilde O( \sqrt{| \mcalU{} |})$ .
However, when $\beta'$ is, e.g., $1 / |\mcalU{} |^c$, for some constant $c$, this would be unacceptable.

Second, as [Bassily et al., 2017] [Bassily et al., 2017] do, we set $m \in \tilde O( \sqrt{| \mcalU{} |} )$, bounding with constant probability the second term by $\tilde O( \sqrt{| \mcalU{} |})$.
Repetition and returning the median estimate amplifies the success probability.

Ideally, only $O(\ln ( {1} / {\beta'} ) )$ repetitions are required, to boost success probability to $1 - \beta'$. Unfortunately, $O(\ln ( {| \mcalU{} |} / {\beta'} ) )$ repetitions are required in [Bassily et al., 2017]'s analysis [Bassily et al., 2017], introducing a term $\sqrt{ \ln ( {| \mcalU{} |} / {\beta'} ) }$ in the error bound.
This is due to the Poisson approximation [Bassily et al., 2017].
The remainder of this subsection outlines the compromise of invoking the Poisson approximation.

Repetition for amplification.
Let $k$ be the number of repetitions. Instead of using the entire set $\mcalU{}$ in each repetition, such that each user reports $k$ times to the server (which would degrade privacy according to the Composition Theorem; see Theorem 3.14 in [Dwork and Roth, 2014] for more details), partition the $\mcalU{}$ into $k$ sets, denoted as $\mcalU{}_1, \ldots, \mcalU{}_k$, use $k$ pairwise independent hash functions $h_1, \ldots, h_k : \mcalD{} \rightarrow [m]$ and run the algorithm on each of $\mcalU{}_1, \ldots, \mcalU{}_k$ independently.
The partition puts each user into one of the $k$ sets uniformly at random, so that it reports to the server only once.
For all $j \in [k]$ and $i \in [m]$, let $f_{ \mcalU{}_j , h_j} [ i ] \doteq | \{ u \in \mcalU{}_j : h_j( v^{ (u) } ) = i \} |$ be the number of users in $\mcalU{}_j$ whose elements are hashed to $i$ and let $\hat f_{\mcalU{}_j, h_j} [ i ]$ be its estimate by .
For all $j \in [k]$ and $v \in \mcalD{}$, let $f_{\mcalU{}_j} [ v ] \doteq | \{ u \in \mcalU{}_j : v^{ (u) } = v \} |$ be the number of users in $\mcalU{}_j$ whose elements equal $v$. For each $v \in \mcalD{}$, $\hat f_{\mcalU{}_j, h_j} [ h(v) ]$ is an estimate of $f_{\mcalU{}_j} [ v ]$.
In expectation, $f_{\mcalU{}_j} [ v ]$ equals $f_{\mcalU{} } [ v ] / k$, so views $k \cdot \hat f_{\mcalU{}_j, h_j} [ h(v) ]$ as an estimate of $f_{\mcalU{} } [ v ]$.

focuses on three kinds of error: i) $\lambda_1 (j, v) \doteq | k f_\mcalU{}_j [ v ] -  f_\mcalU{} [ v ] |$;
ii) $\lambda_2 (j, v) \doteq | k f_{\mcalU{}_j, h_j} [ h(v) ] - k f_\mcalU{}_j [ v ] |$; and iii) $\lambda_3 (j, v) \doteq | k \hat f_{\mcalU{}_j, h_j} [ h(v) ] - k f_{\mcalU{}_j, h_j} [ h(v) ] |$.
By the triangle inequality,

\begin{equation} \label{equa: error decomposition}
| k \hat f_{\mcalU{}_j, h_j} [ h(v) ] - f_{\mcalU{} } [ v ] |
\le
\lambda_1(j, v) + \lambda_2(j, v) + \lambda_3(j, v)\,.
\end{equation}

Ideally, one would like to bound $\med{}_{j \in [k] } | k \hat f_{\mcalU{}_j, h_j} [ h(v) ] - f_{\mcalU{} } [ v ] |$ by $O ( ( {1} / { \epsilon } ) \cdot \sqrt{ | \mcalU{} | \cdot \ln ( {1} / {\beta'} ) } )$ with probability $1 - \beta'$.
Following previous strategy [Bassily et al., 2017], as we include in Theorem <ref> below, one key step would be proving that with probability at least $1 - \beta'$, the number of $j \in [k]$ such that $\lambda_1 (j, v) \in O ( ( {1} / { \epsilon } ) \cdot \sqrt{ | \mcalU{} | \cdot \ln ( {1} / {\beta'} ) } )$ is greater than $(1 - \alpha_1 )\cdot k$, for some constant[In the original paper [Bassily et al., 2020], $\alpha_1$ is set to be $1 / 10$. See Claim 5.4 in [Bassily et al., 2020].],
$\alpha_1 < 0.5$.

Ball in Bins.

However, Analyzing the random variables $\{ f_\mcalU{}_j [ v ] : j \in [k] \}$ is not trivial due to interdependence, and this reduces to the study of the balls and bins problem.
There are $f_\mcalU{} [ v ]$ balls, which are thrown into $k$ bins independently and uniformly at random. For each $j \in [k]$, let $X_j = f_\mcalU{}_j [v]$ be the number of balls in the $j^{\text{th}}$ bin, which is a sum of $f_\mcalU{} [ v ]$ independent Bernoulli random variables each with mean $1 /k$. It holds that $\E[X_j ] = f_\mcalU{} [ v ] / k$.
By Bernstein's inequality (Fact <ref>), with probability at least $1 - \alpha_1 / 2$, $k | X_j - f_\mcalU{} [ v ] / k  | \in O ( k \sqrt{ \Var{} [ X_j  ] \ln (1 / \alpha_1) } + k \ln (1 / \alpha_1) )$. As $\alpha_1$ is a constant and $\Var{} [ X_j ] \in \Theta ( f_\mcalU{} [ v ] / k)$, it simplifies to $O ( \sqrt{ k \cdot f_\mcalU{} [ v] } + k )$.

If the $\{X_j\}$ were independent, it could be proven via Chernoff bound that with probability at most $e^{ - \Theta(k) }$, the number of $j \in [k]$ for which the error bound does not hold exceeds $\alpha_1 \cdot k$.
It suffices to set $k \in \Theta (\ln (1 / \beta') )$.
As $f_\mcalU{} [v] \in O( | \mcalU{} | )$, the error would be at most $O ( \sqrt{ | \mcalU{} | \cdot \ln ( {1} / {\beta'} ) } )$, which is desirable[We assume that $|\mcalU{} | \ge \ln (1 / \beta')$. Otherwise, $\sqrt{ |\mcalU{} | \ln (1 / \beta')} \ge |\mcalU{}|$ and the bound is not meaningful.].

The problem is that the $X_j$ are not independent, as $\sum_{j \in [k] } X_j = f_\mcalU{} [ v ]$.
To decouple the dependence of the $X_j$ terms, one possible way is to approximate $X_1, \ldots, X_k$ by a set of independent Poisson random variables $Y_1, \ldots, Y_k$ each with mean $f_\mcalU{} [ v ] / k$.
We know from Fact <ref>, and prior art [Bassily et al., 2017], that for each $j \in [k]$, with probability at least $1 - \alpha_1 / 2$, $| k Y_j - f_\mcalU{} [ v ]  | \in O ( \sqrt{ k \cdot f_\mcalU{} [ v ] } + k )$. As the $Y_j$ random variables are independent, via the Chernoff bound, the probability that the number of $j \in [k]$ for which this bound does not hold exceeds $\alpha_1 \cdot k$ is at most $e^{ - \Theta(k) }$.
The relation between the $X_j$ and the $Y_j$ is established as follows.
[Poisson Approximation [Mitzenmacher and Upfal, 2017]]
Let $g(z_1, z_2, \ldots, z_k): \R^k \rightarrow \R$ be a non-negative function. Then

\E[ g(X_1, \ldots, X_k ) ] \le e \sqrt{ f_\mcalU{} [ v ] } \E [ g(Y_1, \ldots, Y_k ) ]

For $\vec z = (z_1, \ldots, z_k) \in \R^k$, define

g (\vec z) = \dsone{}[ | \{ j \in [k] : | k z_j - f_\mcalU{}[v] | \notin O ( \sqrt{ k \cdot f_\mcalU{}[v] } + k ) \} | \ge \alpha_1 \cdot k ],

which is the indicator function of whether the size of the set $| \{ j \in [k] : | k z_j - f_\mcalU{}[v] | \notin O ( \sqrt{ k \cdot f_\mcalU{}[v] } + k ) \} |$ is at least $\alpha_1 k$. With this definition, it holds that,

\begin{align*}
\E[g (X_1, \ldots, X_k) ]
&= \Pr[ | \{ j \in [k] : | k X_j - f_\mcalU{}[v] | \notin O ( \sqrt{ k \cdot f_\mcalU{}[v] } + k ) \} | \ge \alpha_1 \cdot k ]
\\
\E [ g(Y_1, \ldots, Y_k) ]
&= \Pr[ | \{ j \in [k] : | k Y_j - f_\mcalU{}[v] | \notin O ( \sqrt{ k \cdot f_\mcalU{}[v] } + k ) \} | \ge \alpha_1 \cdot k ] = e^{ - \Theta(k) }
\end{align*}

By Fact <ref>, if we set $k \in \Theta ( \ln ( |\mcalU{} |  /  \beta' ) )$, we can prove that

\Pr[ | \{ j \in [k] : | k X_j - f_\mcalU{}[v] | \notin O ( \sqrt{ k \cdot f_\mcalU{}[v] } + k ) \} | \ge  \alpha_1 \cdot k ] \le e \sqrt{ f_\mcalU{} [ v ] } e^{ - \Theta(k) } \le \beta'.

By this fact, an event that happens with probability $e^{ - \Theta(k) }$ in the Poisson case, happens with probability $e^{ - \Theta(k) } \cdot e \sqrt{ f_\mcalU{} [ v ] }$ in the exact case (to see this, set $g$ to be the indicator function of that event).

By setting $k \in \Theta ( \ln ( |\mcalU{} |  /  \beta' ) )$, we can prove that, with  probability at most $\beta'$, the number of $j \in [k]$ for which $| k X_j - f_\mcalU{} [ v ]  | \not\in O ( \sqrt{ k \cdot |\mcalU{} | }  )$ exceeds $\alpha_1 \cdot k$.

§.§ The

In this section, we discuss our , which improves on  [Bassily et al., 2017] and achieves properties specified in Theorem <ref>. In particular, achieves optimal estimation error of $O( (1 / \eps) \cdot \sqrt{ | \mcalU{} | \cdot \ln ( {1} / {\beta'} ) } )$. By involving martingales in the analysis, to cope with dependencies, we avoid Poisson approximation. Hence partitions $\mcalU{}$ into fewer sets than .

At a high level, follows the same framework as . First, partitions $\mcalU{}$ into $k$ (to be determined) subsets $\mcalU{}_1, \ldots, \mcalU{}_k$.
Then, picks $k$ pairwise independent hash functions $h_1, \ldots, h_k : \mcalD{} \rightarrow [m]$ (with $m$ to be determined). For each $j \in [k]$,  $h_j$ maps $\{ v^{ (u) } : u \in \mcalU{}_j \} \subseteq \mcalD{}^{ |\mcalU{}_j | }$, the set of elements held by users in $\mcalU{}_j$, to a new set $\{ h_j ( v^{ (u) } ) : u \in \mcalU{}_j \} \subseteq [m]^{ |\mcalU{}_j | }$.
The frequency of elements

in the new set can be estimated by applying the algorithm.
For each $v \in \mcalD{}, j \in [k]$, we view $\hat f_{\mcalU{}_j, h_j} [ h(v) ]$ as an estimate of $f_{\mcalU{}_j} [ v ]$, and we regard $\med{}_{j \in [k] } k \cdot \hat f_{\mcalU{}_j, h_j} [ h(v) ]$ as an estimate of $f_{\mcalU{} } [ v ]$.
Detailed pseudocode for is included in Appendix <ref>.

There are two significant differences between the algorithms. First, can partition $\mcalU{}$ differently from . Second, the analysis of involves more helpful parameters than those of . Specifically, in , the number of repetitions $k = C_K \cdot \ln ( 1 / \beta')$, and the Hadamard matrix dimension $m = C_M \cdot \eps \cdot \sqrt{| \mcalU{} | }$, for constants
[The values are determined in the proofs. See Appendix <ref>.]  $C_M$ and $C_K$.

Two Partition Schemes. In , each user is put into one of the subsets uniformly and independently at random. We investigate this independent partitioning  further, and propose the following alternative partitioning scheme.
First, randomly permute $\mcalU{}$; then, pick the first $|\mcalU{}| / k$ users as $\mcalU{}_1$, the next $|\mcalU{}| / k$ users as $\mcalU{}_2$, and so on.

Compared to independent partitioning, this permutation partitioning, as we call it, creates subsets of equal size. Analyzing it is more challenging due to the dependence between the $\mcalU{}_1, \ldots, \mcalU{}_k$.

Outline of Our Analysis. We study two kinds of deviations introduced by the partitioning of $\mcalU{}$ that affect the estimation error of the frequency oracle: i) $\Delta_0 \doteq \sum_{j \in [k] } \sqrt{ ( | \mcalU{}_j | - | \mcalU{} | / k )^2 }$, which measures the deviations of the $| \mcalU{}_j |$ terms from their expectation $| \mcalU{} | / k$;
one advantage of permutation partitioning is that $\Delta_0 = 0$; and  ii) $\Delta_1 \doteq \sum_{j \in [k] } \Vert  f_\mcalU{}_j - f_\mcalU{} / k \Vert_2$, where $\left\Vert f_\mcalU{}_j - { f_\mcalU{} } / k \right\Vert_2 \doteq \sqrt{ \sum_{ v \in \mcalD{} } ( f_\mcalU{}_j [ v ] -   f_\mcalU{} [ v ] / k )^2 }$ are, for every $j \in [k]$, the $\ell_2$ distances between the vectors $f_\mcalU{}_j$ and $f_\mcalU{} / k$.
These definitions focus on the deviations as a whole, instead of individually, for a a single $v \in \mcalD{}$ or $j \in [k]$.
For independent partitioning, we bound $\Delta_0$ and $\Delta_1$ directly by McDiarmid’s Inequality (Fact <ref>, which is proven by martingale method [McDiarmid, 1998, Mitzenmacher and Upfal, 2017]).
For permutation partitioning, we construct a martingale based on $\Delta_1$.
Then we bound it by Azuma's Inequality (Fact <ref>).
Our technique leads to a strong result, the proof of which is included in Appendix <ref>.

For $i = 0, 1$; $k \in \N^+$, $\exists$ $C_i > 0$, s.t., with probability $1 - \beta'$: $\Delta_i \le C_i \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }$ .

As a special case, this lemma holds for $k = C_K \cdot \ln ( 1 / \beta')$. Next, we study the estimation error of $|\med{}_{j \in [k] } k \cdot \hat f_{\mcalU{}_j, h_j} [ h(v) ] - f_\mcalU{} [v] |$ for a given $v \in \mcalD{}$. Inequality (<ref>) bounds this via three kinds of error $\lambda_1(j, v)$, $\lambda_2(j, v)$, and $\lambda_3(j, v)$. We focus on the following good sets

\begin{align}
\goodset{}_0 &\doteq \{ j \in [k] : k |\mcalU{}_j | \in \Theta( |\mcalU{} |  ) \}\,, \\
\goodsetA{}
& \doteq \{ j \in [k] : \Vert k f_\mcalU{}_j -  f_\mcalU{} \Vert_2 \in O ( \sqrt{ |\mcalU{} | \ln ( 1 / \beta') } ) \}\,, \\
\goodset{}_i
& \doteq \big\{ j \in [k] : \lambda_i (j, v) \in O \big( (1 / \eps) \cdot \sqrt{ k \cdot |\mcalU{}_j | \ln ( 1 / \beta') } \big) \big\}\,, \quad i = 2, 3
\end{align}

For each $j \in \cap_{ 0 \le i \le 3}\, \goodset{}_i$, it holds that $|k \cdot \hat f_{\mcalU{}_j, h_j} [ h(v) ] - f_\mcalU{} [v] | \in O \big( (1 / \eps) \cdot \sqrt{ |\mcalU{} | \ln ( 1 / \beta') } \big)$. To prove that the median of the estimates follows the same bound, we prove that $|j \in \cap_{ 0 \le i \le 3} \goodset{}_i| > k/2$, as follows.

For $0 \le i \le 3$, with probability at least $1 - \beta'$, it holds that $|\goodset{}_i| > (1 - 1 / 8) k$.

For $i = 0, 1$, Theorem <ref> is a corollary of Lemma <ref>. For $i = 2$, the Theorem follows from the analysis of the elements' collisions under hash functions $h_j$. For $i = 3$, the Theorem results from Fact <ref>, the properties of the algorithm. Appendix <ref> details the proof.

§ SUCCINCT HISTOGRAM

We show how to construct a succinct histogram efficiently, based on the discussed in previous section. In Section <ref>, reduce succinct histogram directly to frequency oracle. In Section <ref>, we improve the tree-based protocol proposed by [Bassily et al., 2017] [Bassily et al., 2017]. Our main result is this.

Let $\mcalU{}$ be a set of $n$ users each holding an element from some finite domain $\mcalD{}$ of size $d$, $\eps \in (0, 1)$ be the privacy parameter and $\beta \in (0, 1)$ be the specified failure probability. There exists an $\eps$-locally differentially private tree-based protocol that returns a set of (element, estimate) pairs of size $\tilde O( \sqrt{n} )$, such that, with probability at least $1 - \beta$,

* For each $(v, \hat f_\mcalU{} [ v] )$ in the set, it holds that $|\hat f_\mcalU{}[v] - f_\mcalU{} [ v] | \in O ( (1 / \eps{} ) \cdot \sqrt{ n \cdot \ln ( {n} / {\beta} ) } )$ .

* $\forall v \in \mcalD{}$, if $f_\mcalU{} [ v ] \ge O ( (1 / \eps{} ) \cdot \sqrt{ n \cdot (\ln d ) \cdot ( \ln ( {n} / {\beta} ) ) / \ln n } )$, then $v$ is included in the set.

Each user in $\mcalU{}$ uses processing memory of size $\tilde O(1)$, has $\tilde O(1)$ running time and reports only $1$ bit to the server. The server uses processing memory of size $\tilde O(\sqrt{ | \mcalU{} | } )$, has $\tilde O( | \mcalU{} | )$ processing time, and answers each query in $\tilde O(1)$ time. The $\tilde O$ notations hide logarithmic factors in $| \mcalU{} |$, $| \mcalD{} |$ and $1 / \beta'$.

§.§ Accurate, Computation Intensive Protocol

To discover heavy hitters, we could construct a directly on all users, $\mcalU{}$. By Theorem <ref>, for each element $v \in \mcalD{}$, with probability at least $1 - \beta / d$, it returns an estimate $\hat f_\mcalU{} [ v ]$ satisfying:

|  \hat f_\mcalU{} [ v ] - f_\mcalU{} [ v ] | \in  O ( (1 / \eps{} ) \cdot \sqrt{ n \cdot \ln ( {d} / {\beta} ) } )\,.

Each user has memory in $\tilde O(1)$, running time in $\tilde O(1)$, and reports only $1$ bit to the server. The server requires $\tilde O(\sqrt{ n } )$ memory, has $\tilde O( n )$ processing time, and answers each query in $\tilde O(1)$ time.

To construct a succinct histogram, we query the frequency oracle for every element $v \in \mcalD{}$. By  aunion bound, the algorithm fails with probability $\beta$. However, this leads to a running time of $O(d)$, which is infeasible when the domain $\mcalD{}$ is large.

To lower the computation cost, we develop a tree-based protocol, called , that satisfies properties in Theorem <ref>.

Base-$\sqrt{n}$ representation. Let $\Lambda \doteq \{0, 1, \ldots, \sqrt{n} - 1 \}$ be an alphabet of size $\sqrt{n}$ (for simplicity, we assume that $\sqrt{n}$ is an integer), and $L \doteq 2 \cdot (\log d) / \log n$.

Each element in the finite $\mcalD{}$ can be encoded as a unique string in $\Lambda^L = \{0, 1, \ldots, \sqrt{n} - 1 \}^L$.

Prefix Tree. $\forall v \in \mcalD{}, \tau \in [L]$, let $v[1 : \tau]$ be the first $\tau$ symbols in $v$'s base-$\sqrt{n}$ representation, which is called a prefix of $v$. Let $\Lambda^0 \doteq \{ \bot \}$ be the set consisting of the empty string.
$\forall \tau \in [L]$, $\Lambda^\tau$ the set of all possible prefixes of length $\tau$.
Denote $\mathcal{T}$ the complete tree with fanout $\sqrt{n}$ and depth $L$, such that each non-leaf node of $\mathcal{T}$ has $\sqrt{n}$ children.
The root of $\mcalT{}$ is associated with the empty string $\bot$.
Each leaf of $\mcalT{}$ is associated with a unique element in $\mcalD{}$.
Each edge on a root-to-leaf path corresponds to a symbol in the leaf's base-$\sqrt{n}$ representation.
We call $\mcalT{}$ a prefix tree (or trie) of $\mcalD{}$.

$\forall \tau \in [L], \pmbs{} \in \Lambda^\tau$, let $f_\mcalU{} [ \pmbs{} ] \doteq | \{ u \in \mcalU{} : v^{ (u) }[1 : \tau] = \pmbs{} \} |$ be the frequency of $\pmbs{}$. Then, $f_\mcalU{} [ v[1:\tau] ] \ge f_\mcalU{} [v]$.

Overview of . The algorithm aims to identify a set of elements in $\mcalD{}$, called heavy hitters, whose frequencies are no less than some threshold, $3 \lambda$, where $\lambda \doteq ( C_{\lambda} / \eps) \sqrt{ n \cdot (\log d) \cdot (\ln (n / \beta) ) / \ln n }$, for some constant $C_{\lambda} > 0$ (to be determined).
If $v \in \mcalD{}$ is a heavy hitter, then $f_\mcalU{} [ v[1:\tau] ] \ge f_\mcalU{} [v] \ge 3\lambda$ for all $\tau \in [L]$.
To find heavy hitters in $\mcalD{}$, we can search for the set of prefixes in $\Lambda^\tau$ whose frequencies are at least $3 \lambda$, for $\tau = 1, 2, \ldots, L$.
From the perspective of the prefix tree $\mathcal{T}$, if some leaf node $v$ has frequency at least $3\lambda$, then all nodes in its root-to-leaf path have frequency at least $3\lambda$.
Hence, to find the leaves that are heavy hitters, we  search the prefix tree top down.

For each $\tau \in [L]$, we need to construct a frequency oracle () to estimate the frequencies of the prefixes in $\Lambda^\tau$ .
We want to avoid each user participating in every frequency oracle: a user reporting $L$ times to the server would degenerate the privacy guarantee of the algorithm.
Therefore, we partition the set of users $\mcalU{}$ into $L$ subsets $\U_1, \U_2, \ldots, \U_L$.
As before, this is performed by either independent partitioning or permutation partitioning.
As $L \in O(\log d)$, by Theorem <ref>, the server uses in total $\tilde O( n )$ processing time and $\tilde O(\sqrt{ n } )$ processing memory to construct these oracles.
For each $\tau \in [L], \pmbs{} \in \Lambda^\tau$, let $\hat f_{\U_\tau} [ \pmbs{} ]$ be the estimation of $f_{\U_\tau} [ \pmbs{} ]$ returned by the frequency oracle. As $\E [ L \cdot f_{\U_\tau} [\pmbs{}] ] = f_\mcalU{} [ \pmbs{} ]$, we use $\hat f_\mcalU{} [ \pmbs{} ] \doteq L \cdot \hat f_{\U_\tau} [ \pmbs{} ]$ as an estimate of $f_\mcalU{} [ \pmbs{} ]$, whose estimation error is established by the following theorem, proven in Appendix <ref>.

$\forall \tau \in [L], \pmbs{} \in \Lambda^\tau$, it holds that, with probability $1 - \beta'$,

| \hat f_\mcalU{} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] | \in O( ( 1 / \eps) \sqrt{ n \cdot (\log d) \cdot (\ln (1 / \beta') ) / \ln n } )\,.

There are two sources of error. First, for each $\tau \in [L]$, the frequency distribution in $\U_\tau$ deviates from its expectation. We bound the $\ell_2$ distance between the distribution in $\U_\tau$ and its expectation by martingale methods. The second kind of error inherits from .
We are particularly interested in the estimation errors of the prefixes in a fixed set.

Define $\Gamma_0 \doteq \{ \bot \}$  to be the set of the empty string, and for $\tau \in [L]$, $\Gamma_\tau \doteq \{ \pmbs{} \in \Lambda^\tau : f_\mcalU{} [ \pmbs{} ] \ge \lambda \}$, the set of prefixes of length $\tau$ whose frequency is at least $\lambda$.
For $\tau < L$, the child set of $\Gamma_\tau$ is defined as $ \Gamma{}_\tau \times \Lambda  \doteq \{ \pmbs{} = \pmbs{}_1 \circ \pmbs{}_2 : \pmbs{}_1 \in \Gamma{}_\tau, \pmbs{}_2 \in \Lambda \}$, where $\pmbs{}_1 \circ \pmbs{}_2$ is the concatenation of $\pmbs{}_1$ and $\pmbs{}_2$.
The candidate set is defined as $\Gamma \doteq \cup_{0 \le \tau < L } \left( \Gamma{}_\tau \times \Lambda \right)$.

Note that for each $\tau \in [L]$, we have $|\Gamma_\tau | \le n / \lambda \le \sqrt{n}$.
Hence, $|\Gamma| \le n L \in \tilde O (n)$.
By applying Theorem <ref> with $\beta' = \beta / (nL)$, and by the union bound over all $\pmbs{} \in \Gamma$, we get the following corollary.

There exists some constant $C_\lambda$, such that with probability at least $1 - \beta$, it holds simultaneously for all $\pmbs{} \in \Gamma$:
| \hat f_\mcalU{} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] |
\le \lambda
\in
O( ( 1 / \eps) \sqrt{ n \cdot (\log d) \cdot (\ln (n / \beta) ) / \ln n } )\

Search Phrase.
loops over $\tau \in [L]$, and queries the frequency oracles to construct the following sets. The detailed pseudo codes of the algorithm is included in Appendix <ref>.
Define $\mcalP{}_0 \doteq \{ \bot \}$. For $\tau \in [L]$, the $\tau^{\text{th}}$ search set is defined inductively as $\mcalP{}_\tau \doteq \{ \pmbs{} \in \mcalP{}_{\tau - 1} \times \Lambda : \hat f_\mcalU{} [ \pmbs{} ] \ge 2 \lambda \}$, where
\mcalP{}_{\tau - 1} \times \Lambda \doteq \{ \pmbs{} = \pmbs{}_1 \circ \pmbs{}_2 : \pmbs{}_1 \in \mcalP{}_{\tau - 1}, \pmbs{}_2 \in \Lambda \}.

The following theorem, proved in Appendix <ref>, shows is correct.

Assuming that $\forall \pmbs{} \in \Gamma$, it holds that $| \hat f_\mcalU{} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] | \le \lambda$. It is guaranteed that $\forall \tau \in [L], \forall \pmb{s} \in \Lambda^\tau$:  i) if $f_\mcalU{} [ \pmb{s} ] \ge 3 \cdot \lambda$, then $\pmbs{} \in \mcalP{}_\tau$;  ii) if $f_\mcalU{} [ \pmb{s} ] < \lambda$, then $\pmbs{} \notin \mcalP{}_\tau$, consequently, $\mcalP{}_\tau \subseteq \Gamma_\tau$.

By this theorem, the set $\mcalP{}_L$ contains all heavy hitters in $\mcalD{}$. Moreover, for each $\tau \in [L]$, to construct $\mcalP{}_\tau$, only needs to query the frequencies of elements in $\mcalP{}_{\tau - 1} \times \Lambda \subseteq \Gamma_{\tau - 1} \times \Lambda \subseteq \Gamma$. In other words, all elements queried by belongs to $\Gamma$. By Theorem <ref>, each query requires $\tilde O(1)$ time, hence the total query time  is bounded by $|\Gamma | \in \tilde O(n)$.

Refinement Phrase. After the set $\mcalP{}_L$ is identified, invokes the frequency oracle constructed on the whole user set $\mcalU{}$, to refine the frequency estimations of elements in $\mcalP{}_L$. This oracle is more accurate compared to those in the search phrase, because there is no partitioning of $\mcalU{}$. Including the refinement phrase, each user reports just twice to the server.

Comparison with  [Bassily et al., 2017]. There are two major differences between our algorithm and . First, the algorithm  considers base-$2$ representation of elements in $\mcalD{}$, instead of base-$\sqrt{n}$ representation. The prefix tree of  has fanout 2 and depth $\log d$. This requires the algorithm to partition $\mcalU{}$ into $\log d$ subsets, which results in smaller subset sizes and larger estimation error. Second, the frequency oracle used by  does not exploit the fast Hadamard transform. It answers each query in $\tilde O( \sqrt{n} )$ time. As  queries only $\tilde O( \sqrt{n} )$ elements, the server running time is still $\tilde O( n )$. On the other hand, with $\sqrt{n}$-representation, explores and queries $\tilde O( n )$ elements. It is thus crucial that each query is answered in $\tilde O(1)$ time.

[Bassily et al., 2017]
R. Bassily, K. Nissim, U. Stemmer, and A. G. Thakurta, “Practical locally
private heavy hitters,” in Advances in Neural Information Processing
Systems 30: Annual Conference on Neural Information Processing Systems 2017,
December 4-9, 2017, Long Beach, CA, USA, I. Guyon, U. von Luxburg,
S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett,
Eds., 2017, pp. 2288–2296.

[Erlingsson et al., 2014]
Ú. Erlingsson, V. Pihur, and A. Korolova, “RAPPOR: randomized
aggregatable privacy-preserving ordinal response,” in Proceedings of
the 2014 ACM SIGSAC Conference on Computer and Communications Security,
Scottsdale, AZ, USA, November 3-7, 2014, G. Ahn, M. Yung, and N. Li,
Eds.1em plus 0.5em minus 0.4emACM, 2014, pp. 1054–1067.

[Fanti et al., 2016]
G. C. Fanti, V. Pihur, and Ú. Erlingsson, “Building a RAPPOR with the
unknown: Privacy-preserving learning of associations and data dictionaries,”
Proc. Priv. Enhancing Technol., vol. 2016, no. 3, pp. 41–61, 2016.

[Team, 2017]
D. P. Team, “Learning with privacy at scale,” Apple Machine Learning
Journal, vol. 2017, no. 1, pp. 1–25, 2017.

[Tang et al., 2017]
J. Tang, A. Korolova, X. Bai, X. Wang, and X. Wang, “Privacy loss in apple's
implementation of differential privacy on macos 10.12,” CoRR, vol.
abs/1709.02753, 2017.

[Ding et al., 2017]
B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,”
in Advances in Neural Information Processing Systems 30: Annual
Conference on Neural Information Processing Systems 2017, December 4-9, 2017,
Long Beach, CA, USA, I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach,
R. Fergus, S. V. N. Vishwanathan, and R. Garnett, Eds., 2017, pp. 3571–3580.

[Dwork and Roth, 2014]
C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,”
Found. Trends Theor. Comput. Sci., vol. 9, no. 3-4, pp. 211–407,

[Bassily and Smith, 2015]
R. Bassily and A. D. Smith, “Local, private, efficient protocols for succinct
histograms,” in Proceedings of the Forty-Seventh Annual ACM on
Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17,
2015, R. A. Servedio and R. Rubinfeld, Eds.1em plus 0.5em minus
0.4emACM, 2015, pp. 127–135.

[Bun et al., 2019]
M. Bun, J. Nelson, and U. Stemmer, “Heavy hitters and the structure of local
privacy,” ACM Trans. Algorithms, vol. 15, no. 4, pp. 51:1–51:40,

[Bassily et al., 2020]
R. Bassily, K. Nissim, U. Stemmer, and A. Thakurta, “Practical locally private
heavy hitters,” J. Mach. Learn. Res., vol. 21, pp. 16:1–16:42, 2020.

[Nguyên et al., 2016]
T. T. Nguyên, X. Xiao, Y. Yang, S. C. Hui, H. Shin, and J. Shin,
“Collecting and analyzing data from smart device users with local
differential privacy,” CoRR, vol. abs/1606.05053, 2016.

[Cormode et al., 2019]
G. Cormode, T. Kulkarni, and D. Srivastava, “Answering range queries under
local differential privacy,” Proc. VLDB Endow., vol. 12, no. 10,
pp. 1126–1138, 2019.

[Motwani and Raghavan, 1995]
R. Motwani and P. Raghavan, Randomized Algorithms.1em plus 0.5em
minus 0.4emCambridge University Press, 1995.

[Mitzenmacher and Upfal, 2017]
M. Mitzenmacher and E. Upfal, Probability and computing: Randomization
and probabilistic techniques in algorithms and data analysis.1em plus
0.5em minus 0.4emCambridge university press, 2017.

[Charikar et al., 2002]
M. Charikar, K. C. Chen, and M. Farach-Colton, “Finding frequent items in
data streams,” in Automata, Languages and Programming, 29th
International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002,
Proceedings, ser. Lecture Notes in Computer Science, P. Widmayer, F. T.
Ruiz, R. M. Bueno, M. Hennessy, S. J. Eidenbenz, and R. Conejo, Eds., vol.
2380.1em plus 0.5em minus 0.4emSpringer, 2002, pp. 693–703.

[McDiarmid, 1998]
C. McDiarmid, Concentration.1em plus 0.5em minus 0.4emBerlin, Heidelberg: Springer Berlin Heidelberg, 1998, pp. 195–248.

[Audibert et al., 2009]
J. Audibert, R. Munos, and C. Szepesvári, “Exploration-exploitation
tradeoff using variance estimates in multi-armed bandits,” Theor.
Comput. Sci., vol. 410, no. 19, pp. 1876–1902, 2009.

[Chung and Lu, 2006]
F. Chung and L. Lu, “Concentration inequalities and martingale inequalities: a
survey,” Internet Math., vol. 3, no. 1, pp. 79–127, 2006.

[Devroye and Lugosi, 2001]
L. Devroye and G. Lugosi, Combinatorial methods in density estimation,
ser. Springer series in statistics.1em plus 0.5em minus 0.4emSpringer, 2001.

[Tolstikhin, 2017]
I. O. Tolstikhin, “Concentration inequalities for samples without
replacement,” Theory of Probability & Its Applications, vol. 61,
no. 3, pp. 462–481, 2017.

[Pollard, 2015]
D. Pollard, “Miniempirical,” Manuscript.
http://www.stat.yale.edu/˜pollard/Books/Mini/, 2015.

§ CONCENTRATION INEQUALITIES

[Chernoff bound [Mitzenmacher and Upfal, 2017]]  Let $X_1, \ldots, X_n$ be independent 0-1 random variables. Let $X = \sum_{i \in [n]} X_i$ and $\mu = \E[X]$. Then for every $\delta > 0$,

\Pr[ X \ge (1 + \delta) \mu ] \le  \left( \frac{ e^\delta}{ (1 + \delta)^{1 + \delta} } \right)^\mu\,.

Similarly, for every $\delta \in (0, 1)$

\Pr[ X \le (1 - \delta) \mu ] \le  \left( \frac{ e^{-\delta} }{ (1 - \delta)^{1 - \delta} } \right)^\mu\,.

[Bernstein’s Inequality [Audibert et al., 2009]]  Let $X_1, \ldots, X_n$ be independent real-valued random variables such that $|X_i| \le c$ with probability one. Let $S_n = \sum_{i \in [n]} X_i$ and $\Var{} [ S_n ]  = \sum_{ i \in [n] } \Var [X_i^2]$. Then for all $\beta \in (0, 1)$,

\left| S_n - \E[ S_n ] \right| \le \sqrt{ 2 \Var{} [ S_n ] \ln \frac{2}{\beta} } + \frac{2 c \ln \frac{2}{\beta}}{ 3}\,,

with probability at least $1 - \beta$.

[[Chung and Lu, 2006]]
Let the sequence of random variables $Y_0, \ldots, Y_n$ be a martingale with respect to the sequence of random variables $X_0, \ldots, X_n$ such that

* $\Var{}[ Y_i \mid X_0, \ldots, X_{i - 1} ] \le \sigma_i^2, \forall i \in [n]$ ;  and

* $| Y_i - Y_{i - 1} | \le c, \forall i \in [n]$ .

Then, we have

\Pr[ Y_n - Y_0 \ge \eta ] \le \exp \left( - \frac{\eta^2}{ 2 \left( \sum_{i \in [n] } \sigma_i^2 + c \eta / 3 \right) } \right)\,.

[Hoeffding's Inequality [Devroye and Lugosi, 2001]]  Let $X_1, \ldots, X_n$ be independent real-valued random variables such that that $|X_i| \in [a_i, b_i], \forall i \in [n]$ with probability one. Let $S_n = \sum_{i \in [n]} X_i$, then for every $\eta \ge 0$:

\begin{align*}
\Pr[ S_n - \E[ S_n] \ge \eta ] \le \exp \left( - \frac{2 \eta^2 }{ \sum_{i \in [n] } (b_i - a_i)^2 } \right)\,, \text{ and} \\
\Pr[ \E [ S_n ] - S_n \ge \eta ] \le \exp \left( - \frac{2 \eta^2 }{ \sum_{i \in [n] } (b_i - a_i)^2 } \right)\,.
\end{align*}

[Azuma's Inequality [Mitzenmacher and Upfal, 2017]]  Let $Y_0, \ldots, Y_n$ be a martingale such that

A_i \le Y_i - Y_{i - 1}  \le A_i + c_i\,,

for some constants $\{c_i\}$ and for some random variables $\{A_i\}$ that may be functions of $Y_0, Y_1, \ldots Y_{i - 1}$. Then for all $t \ge 0$ and every $\eta > 0$,

\Pr[ |Y_t - Y_0 | \ge \eta ] \le 2 \exp \left( - \frac{ 2 \eta^2 }{   \sum_{i \in [t] } c_i^2 }\right)\,.

A function $\Delta: \R^n \rightarrow \R$ satisfies the Lipschitz condition with bound $c \in \R$ if, for every $i \in [n]$ and for every sequence of values $x_1, \ldots, x_n \in \R$ and $y_i \in \R$,

| \Delta( x_1, x_2, \ldots, x_{i - 1}, x_i, x_{i + 1}, \ldots, x_n ) - \Delta( x_1, x_2, \ldots, x_{i - 1}, y_i, x_{i + 1}, \ldots, x_n ) | \le c.

[McDiarmid’s Inequality [Mitzenmacher and Upfal, 2017, Tolstikhin, 2017]]
Let $\Delta: \R^n \rightarrow \R$ be a function that satisfies the Lipschitz condition with bound $c \in \R$. Let $X_1, \ldots, X_n$ be independent random variables such that $\Delta(X_1, \ldots, X_n)$ is in the domain of $\Delta$. Then for all $\eta \ge 0$,

\Pr \left[ \Delta(X_1, \ldots, X_n) - \E \left[ \Delta(X_1, \ldots, X_n) \right] \ge \eta \right] \le \exp \left( - \frac{ 2 \eta^2 } { n c^2 } \right)\,.

Let $\mbbS{}_n$ be the symmetric group of $[n]$ (i.e., the set of all possible permutations of $[n]$). A function $\Delta : \mbbS{}_n \rightarrow \R$, is called $(n_1, n_2)$-symmetric with respect to permutations if, for each permutation $\pmbx{} \in \mbbS{}_n$, $\Delta( \pmbx{} )$ does not change its value under the change of order of the first $n_1$ and/or last $n_2 = n - n_1$ coordinates of $\pmbx{}$. For brevity, we call these functions $(n_1, n_2)$-symmetric functions.

[McDiarmid’s Inequality with respect to permutations [Tolstikhin, 2017]]
Let $\Delta: \mbbS{}_n \rightarrow \R$ be an $(n_1, n_2)$-symmetric function for which there exists a constant $c > 0$ such that $| \Delta( \pmbx{} ) - \Delta( \pmbx{}_{i, j} ) | \le c$ for all $\pmbx{} \in \mbbS{}_n, i \in \{1, \ldots, n_1 \}, j \in \{ n_1 + 1, \ldots, n \}$, where the permutation $\pmbx{}_{i,j}$ is obtained from $\pmbx{}$ by transposition of its $i^{\text{th}}$ and $j^{\text{th}}$ coordinates. Let $\mbfX{}$ be a vector of random permutation chosen uniformly from a symmetric permutation group of the set $[n]$. Then for every $\eta > 0$,

\Pr[ \Delta( \mbfX{} ) - \E [ \Delta( \mbfX{} ) ] \ge \eta ] \le \exp \left( - \frac{2 \eta^2 }{ n_1 c^2} \left( \frac{n - 1 / 2 }{n - n_1} \right) \left( 1 - \frac{1}{2 \max \{n_1, n_2 \} } \right) \right)\,.

[Poisson Tail Bound [Pollard, 2015, Mitzenmacher and Upfal, 2017]]  Let $X$ has Poisson distribution with mean $\mu$. For $\eta \in [0, \mu]$,

\begin{align*}
\Pr[ X \le \mu - \eta ] &\le \exp\left( - \frac{\eta^2 }{ 2 \mu } \right)\,,
\end{align*}

and for all $\eta \ge 0$,

\begin{align*}
\Pr[ X \ge \mu + \eta ] &\le \exp\left( - \frac{\eta^2 }{ 2 \mu + 2 / 3 \eta } \right) \,.
\end{align*}

§ PSEUDOCODE

Client-Side Algorithm

Each user receives (from the server) a row index $r$ of the Hadamard matrix, a pairwise hash function[The hash function $h$ has succinct description of $\tilde{O} (1)$ bits, therefore it can be transmitted from the server to the users.] $h: \mcalD{} \rightarrow [m]$, and a privacy parameter $\eps$. Its own element $v$ is hashed to $h(v)$ as the column index. Then it invokes $\algoRandomizer{}(r, h(v), \eps)$ and returns the one-bit result to the server.

Hadamard Randomizer $\algoRandomizer{}$

[1]
Row index $i \in [m]$; column index $j \in [m]$; privacy parameter $\eps$.
Sample $b \in \{-1, 1 \}$, which is $+1$ with probability $e^\eps / (e^\eps + 1)$.
$b \cdot \mrmH[i,j]$.

-Client $\algoHadaOracleClient{}$

[1]
Random index $r \in [m]$; hash function $h: \mcalD{} \rightarrow [m]$; privacy parameter $\eps$.
Let $v \in \mcalD{}$ be the user's element.
$\omega \leftarrow \algoRandomizer{}(r, h(v), \eps)$.

Server-Side Algorithm

The server side algorithm for the frequency oracle consists of two components, namely, oracle construction and frequency query.
The oracle construction algorithm is described in Algorithm <ref>.
Its input comprises a set of users, $\mcalU{}$, their element domain, $\mcalD{}$, and a privacy parameter, $\eps$.
It sets $k = C_K \cdot \ln ( 1 / \beta')$ and $m = C_M \cdot \eps \cdot \sqrt{| \mcalU{} | }$.
It generates $k$ pairwise hash functions $h_1, \ldots h_k$ and partitions $\mcalU{}$ into $k$ sets $\mcalU{}_1, \ldots, \mcalU{}_k$, by independent partitioning or permutation partitioning.
It keeps a matrix $\mrmM{} \in \R^{k \times m}$ initialized with all zeros.
It iterates over the subsets $\mcalU{}_1, \ldots, \mcalU{}_k$.
For each user $u$ in $\mcalU{}_j$ (Line 5), it samples an integer $r^{ (u) } \in [m]$ independently and uniformly at random.
Then it invokes $\algoHadaOracleClient{}(r^{ (u) }, h_j, \eps)$ by sending $r^{(u)}$, $h_j$ and $\eps$ to user $u$.
On receiving user $u$'s response, $\omega^{ (u)}$, the server increases the $(j,  r^{ (u) } )$-th entry of $\mrmM{}$ by $(e^\eps + 1) / (e^\eps - 1) \cdot \omega^{ (u) }$.
Finally, it performs fast Hadamard transforms for all rows of $\mrmM{}$, which has time complexity $O ( k \cdot m \cdot \log m) \subseteq \tilde O ( \sqrt{| \mcalU{} | } )$.

-Construction $\algoHadaOracleConstruction{}$

[1]
A set of users $\mcalU{}$; element domain $\mcalD{}$; privacy parameter $\eps$.
Set $k \leftarrow C_K \cdot \ln ( 1 / \beta')$;  $m \leftarrow C_M \cdot \eps \cdot \sqrt{| \mcalU{} | }$.

Let $h_1, \ldots, h_k : \mcalD{} \rightarrow [m]$ be $k$ pairwise independent hash functions.

Partition $\mcalU{}$ into $k$ sets $\mcalU_1, \ldots, \mcalU_k$, by independent partitioning or permutation partitioning.
Initialize $\mrmM  \in \{ 0 \}^{ k \times m}$.
$j \in [k]$
$u \in \mcalU_j$
$r^{ (u)} \leftarrow$ uniform-at-random integer from $[m]$.
$\omega^{ (u)}  \leftarrow \algoHadaOracleClient{}(r^{ (u)}, h_j, \eps )$.

$\mrmM{}[ j , r^{ (u)}  ] \leftarrow \mrmM [ j, r^{ (u)} ] + (e^\eps + 1) / (e^\eps - 1) \cdot \omega^{ (u)} $.
Set $\mrmM \leftarrow \mrmM \ \mrmH^T$.

The pseudocode for frequency query is in Algorithm <ref>. Its input comprises the estimation matrix $\mrmM{}$ and an element $v \in \mcalD{}$.
For each $j \in [k]$, $\mrmM{} [j, h_j ( v ) ]$ is an estimate of $\hat f_{\mcalU{}_j, h_j} [ v ]$.
Finally, it returns the median of the estimates (times $k$).

-Query $\algoHadaOracleQuery{}$

[1]
Matrix $\mrmM \in \R^{ k \times m}$; an element $v \in \mcalD{}$.
index $j \in [k]$
$\hat f_{\mcalU{}_j, h_j} [ v ] \leftarrow \mrmM [j, h_j( v ) ]$.
$\hat f_\mcalU{}[ v ] \leftarrow \textbf{Median} \left( k \cdot \hat f_{\mcalU{}_j, h_j} [ v ] : j \in [k]  \right)$.
$\hat f_\mcalU{}[ v ]$.

Compared to , we need to slightly change the client side algorithm, described in Algorithm <ref>.
Its input comprises an additional parameter $\tau \in [L]$, the prefix length.
Observe that for each $\tau \in [L]$, elements in $\Lambda^\tau = \{0, 1, \ldots, \sqrt{n} - 1 \}^\tau$ can be viewed integers with size at most $|\mcalD{}|$ in base-$\sqrt{n}$ representation.
Hence, the hash function $h: \mcalD{} \rightarrow [m]$ applies to elements $\Lambda^\tau$.
The user extracts the first $\tau$ symbols, $v[1: \tau]$, of its own element $v$'s the base-$\sqrt{n}$ representation, invokes $\algoRandomizer{}$ with row index $r$, column index $h( v[1: \tau] )$ and privacy parameter $\eps$.

-Client $\algoHadaHeavyClient{}$

[1]
Index $\tau \in [L]$; random index $r \in [m]$; hash function $h: \mcalD{} \rightarrow [m]$; privacy parameter $\eps$.
Let $v \in \mcalD{}$ be the user's element.
$\omega \leftarrow \algoRandomizer{}(r, h(v [ 1 : \tau] ), \eps)$.

Algorithm <ref> shows the changes for the oracle construction.
First, its input comprises the prefix length, $\tau$.
Second, the pairwise independent hash functions $h_1, \ldots, h_k: \mcalD{} \rightarrow [m]$ are also part of the inputs, because they are reused in the different subsets $\U_1, \ldots, \U_L$ by .
Third, the frequency oracle needs to inform the users the prefix length $\tau$, when it invokes $\algoHadaHeavyClient{}$.

-Oracle-Construction $\algoHadaHeavyOracleConstruction{}$

[1]
User set $\U{}$; index $\tau \in [L]$;  hash functions $h_1, \ldots, h_k : \mcalD{} \rightarrow [m]$; privacy parameter $\eps$.
Same as Algorithm <ref>, except that

* Skip Line <ref> and <ref>.

* Replace Line <ref> with $\omega^{ (u)}  \leftarrow \algoHadaHeavyClient{}(\tau, r^{ (u)}, h_j, \eps )$.

is described in Algorithm <ref>.
It partitions the set $\mcalU{}$ into $L$ subsets $\U_1, \ldots, \U_L$, by independent partitioning or permutation partitioning.
It generates $k$ pairwise independent hash functions, $h_1, \ldots, h_k$.
Initially $\mcalP{}_0 = \{ \bot \}$.
Then it constructs $\mcalP{}_1, \ldots, \mcalP{}_L$ for increasing values of $\tau$.
For each $\tau \in [L]$, it invokes frequency oracle construction $\algoHadaHeavyOracleConstruction{}$ on the set $\U_\tau$, with additional parameter the prefix length $\tau$, the hash functions $h_1, \ldots, h_k$, and privacy budget only $\epsilon / 2$.
It queries the frequencies of each elements in $\mcalP{}_{\tau - 1} \times \Lambda$, and adds the ones with frequency estimates at least $2 \lambda$ to $\mcalP{}_\tau$.
When the construction finishes, $\mcalP{}_L \subseteq \mcalD{}$ contains heavy hitters in $\mcalD{}$.
Finally, it invokes the frequency oracle constructed on the whole use set $\mcalU{}$  with privacy budget $\epsilon / 2$, to refines the frequency estimations of elements in $\mcalP{}_L$.

is $\eps{}$ locally differentially private as each user reports only twice, and each report is $\eps{} / 2$ differentially private.

[1]
A set of users $\mcalU{}$; element domain $\mcalD{}$; privacy parameter $\eps$.
Set $\Lambda \leftarrow \{0, 1, \ldots, \sqrt{n} - 1 \}$; $L \leftarrow 2 \cdot (\log d) / \log n$; $\mcalP_0 \leftarrow \{ \bot \}$;  $k \leftarrow C_K \cdot \ln ( nL / \beta)$.
Partition $\mcalU{}$ into $L$ sets $\U_1, \ldots, \U_L$ by independent partitioning or permutation partitioning
Let $h_1, \ldots, h_k : \mcalD{} \rightarrow [m]$ be $k$ pairwise independent hash functions.
$\tau \leftarrow 1$ to $L$
$\mrmM{}_\tau \leftarrow \algoHadaHeavyOracleConstruction{} \left( \U_\tau, \tau, \{ h_j : j \in [k] \}, \eps{} / 2 \right)$.
Initialize candidate prefixes $\mcalP_\tau \leftarrow \emptyset$.
$\pmb{s} \in \mcalP_{\tau - 1} \times \Lambda $
$\hat f_\mcalU{} [ \pmbs{} ] \leftarrow L \cdot \algoHadaOracleQuery{} ( \mrmM{}_\tau, \pmbs{} )$.
$\hat f_\mcalU{}[ \pmb{s} ] \ge 2 \cdot \lambda$
$\mcalP_\tau \leftarrow \mcalP_\tau \cup \{ \pmb{s} \}$.
$\mrmM{} \leftarrow \algoHadaHeavyOracleConstruction{} \left(\mcalU{}, L, \{ h_j : j \in [k] \}, \eps{} / 2 \right)$.
$\pmbs{} \in  \mcalP{}_{ L }$
$\hat f_\mcalU{} [ \pmbs{} ] \leftarrow \algoHadaOracleQuery{} ( \mrmM{}, \pmbs{} )$.
$\{ ( \pmbs{}, \hat f_\mcalU{} [ \pmbs{} ] ) : \pmbs{} \in \mcalP{}_{ L} \}$.

§ PROOFS

§.§ Proofs For Section <ref>.

\mrmH_2 =
\begin{bmatrix}
1 &1 \\
1 &-1
\end{bmatrix},
\text{ and }
\mrmH_4 =
\begin{bmatrix}
1 &1  &1     &1 \\
1 &-1 &1     &-1 \\
1 &1  &-1    &-1 \\
1 &-1 &-1    &1
\end{bmatrix}.

Fact <ref>.
The columns of the Hadamard matrix are mutually orthogonal.

We prove this by induction on the size of $m$. For $\mrmH_1$, this is trivially true. Suppose this holds for $\mrmH_{ m / 2 }$. For every $i \in [m / 2]$, let $\pmbx{}_i \in \R^{m  / 2}$ be the $i^\text{th}$ column of $\mrmH_{m / 2}$. By the induction hypothesis, for all $i, j \in [m / 2]$, if $i \neq j$, then
\left< \pmbx{}_{i }, \pmbx{}_{j } \right> = 0.

Consider $\mrmH_m$. For each $i \in [m]$, define $\pmby{}_i \in \R^m$ to be the $i^{\text{th}}$ column of $\mrmH_m$. Further, define

c(i) \doteq \left((i - 1) \mod (m / 2) \right) + 1 =  \begin{cases}
i,  & \text{ if } i \le m / 2\,, \\
i - m / 2 & \text{ if } i > m / 2\,.
\end{cases}

s(i) \doteq (-1)^{ \dsone{}[ i > (m / 2) ] } = \begin{cases}
1,  & \text{ if } i \le (m / 2)\,, \\
-1  & \text{ if } i > (m / 2)\,.
\end{cases}

By the definition of $\mrmH_m$, it holds that for all $i, j \in [m]$,

\pmby{}_i = \begin{bmatrix}
\pmbx{}_{c(i)} \\
s( i ) \cdot \pmbx{}_{c(i)}
\end{bmatrix}
\quad \text{ and }
\pmby{}_j = \begin{bmatrix}
\pmbx{}_{c(j)} \\
s( j ) \cdot \pmbx{}_{c(j)}\,.
\end{bmatrix}

\left< \pmby{}_i, \pmby{}_j \right>  =
\left< \pmbx{}_{c(i)}, \pmbx{}_{c(j)} \right>  + s( i ) s( j ) \left< \pmbx{}_{c(i)}, \pmbx{}_{c(j)} \right>.

If $i \neq j$, then there are two possible cases: 1) $i \neq j + m / 2$ and $j \neq i + m / 2$, then by the induction hypothesis, $\left< \pmbx{}_{c(i)}, \pmbx{}_{c(j)} \right> = 0$; and 2) $i = j + m / 2$ or $j = i + m / 2$, then $s( i ) s( j ) = -1$. In both cases, $\left< \pmby{}_i, \pmby{}_j \right> = 0$ holds.

Fact <ref>.
For $0 \le i, j < m$, the $(i + 1,j + 1)$-th entry $\mrmH_m[i + 1, j + 1]$ of the Hadamard matrix can be computed in $O( \log m )$ time (both the rows and columns of $\mrmH_m$ are indexed from $1$ to $m$). In particular, let the vectors $(i)_{\log m}, (j)_{\log m} \in \{0, 1\}^{\log m}$ be the $\log m$-bit binary representation of $i$ and $j$, respectively. Then
\mrmH_m[i + 1, j + 1] = (-1)^{ \left< (i)_{\log m}, (j)_{\log m} \right> },
where $\left< (i)_{\log m}, (j)_{\log m} \right>$ is the dot product between $(i)_{\log m}$ and $(j)_{\log m}$.

We prove the Theorem by induction. The claim can be verified manually for $\mrmH_1$ and $\mrmH_2$. Suppose this holds for $\mrmH_{m / 2}$; to prove it true for $\mrmH_m$, recall that the recursive definition
\mrmH_m =
\begin{bmatrix}
\mrmH_{ m / 2}     &   \mrmH_{ m / 2} \\
\mrmH_{ m / 2}     &   -\mrmH_{ m / 2}
\end{bmatrix}
divides $\mrmH_m$ into four sub-matrices. For $0 \le i, j < m$, let the vectors $(i)_{\log m}, (j)_{\log m} \in \{0, 1\}^{\log m}$ be the $\log m$-bit binary representations of $i$ and $j$, respectively. Let $b_i = (i)_{\log m}[1]$ be the highest bit and $\pmbs{}_i = (i)_{\log m}[2: \log m]$ be the last $(\log m) - 1$ bits of $(i)_{\log m}$, respectively. Similarly, we can define $b_j = (j)_{\log m}[1]$ and $\pmbs{}_j = (j)_{\log m}[2: \log m]$. Now,

(i)_{\log m} = \begin{bmatrix}
b_i \\
\pmbs{}_i
\end{bmatrix}
\\ \qquad
(j)_{\log m} = \begin{bmatrix}
b_j \\
\pmbs{}_j
\end{bmatrix}.

Consider the $(i + 1, j + 1)$-th entry of $\mrmH_m$. Our goal is prove that

\mrmH_m [i + 1, j + 1] = (-1)^{ \left< (i)_{\log m}, (j)_{\log m}\right> } = (-1)^{ b_i b_j + \left< \pmbs{}_i , \pmbs{}_j \right> }.

Observe that $b_i b_j = 1$ if the $(i + 1, j + 1)$-th entry belongs to the lower right sub-matrix and $b_i b_j = 0$ otherwise. By definition of $\mrmH_m$, the sub-matrix this entry belongs to can be written as $(-1)^{b_i b_j } \mrmH_{m / 2}$. If we also view $\pmbs{}_i, \pmbs{}_j \in \{0, 1\}^{ ( \log m ) - 1 }$ as integers in $[0, m / 2)$, then $(\pmbs{}_i + 1, \pmbs{}_j + 1)$ is the pair of indexes of the entry inside the sub-matrix. By the induction hypothesis, the value of the $(\pmbs{}_i + 1, \pmbs{}_j + 1)$ entry of the matrix $(-1)^{b_i b_j } \mrmH_{m / 2}$ is given by
$(-1)^{ b_i b_j + \left< \pmbs{}_i , \pmbs{}_j \right> }$, which finishes the proof.

Fact <ref>.
For all $\pmbx{} \in \R^m$, there is a standard divide-and-conquer algorithm that computes the multiplication $\mrmH_m \,\pmbx{}$ (equivalently, $\mrmH_m^T \pmbx{}$, as $\mrmH_m$ is symmetric) in $O(m \log m)$ time and $O(m)$ memory.

Let $\pmbx{}_1\in \R^{m / 2}$ be the first $m / 2$ entries, and $\pmbx{}_2 \in \R^{m / 2}$ be the second $m / 2$ entries of $\pmbx{}$ respectively. Define $\pmby{}_1 = \mrmH_{ m / 2} \ \pmbx{}_1$ and $\pmby{}_2 = \mrmH_{ m / 2 } \ \pmbx{}_2$. Then

\mrmH_m  \ \pmbx{} =
\begin{bmatrix}
\mrmH_{ m / 2}     &   \mrmH_{ m / 2} \\
\mrmH_{ m / 2}     &   -\mrmH_{ m / 2} \\
\end{bmatrix}
\begin{bmatrix}
\pmbx{}_1 \\
\pmbx{}_2
\end{bmatrix}
\begin{bmatrix}
\mrmH_{ m / 2} \ \pmbx{}_1 + \mrmH_{ m / 2} \ \pmbx{}_2 \\
\mrmH_{ m / 2} \ \pmbx{}_1 - \mrmH_{ m / 2} \ \pmbx{}_2
\end{bmatrix}
\begin{bmatrix}
\pmby{}_1 + \pmby{}_2 \\
\pmby{}_1 - \pmby{}_2
\end{bmatrix}.

Let $T(m)$ be the time to compute $\mrmH_m \ \pmbx{}$. Computing $\pmby{}_1$ and $\pmby{}_2$ takes time $2 \cdot T(m / 2)$. Computing $\pmby{}_1 + \pmby{}_2$ and $\pmby{}_1 - \pmby{}_2$ takes time $O(m)$. Therefore,
T(m) = 2 \cdot T( m / 2) + O(m).
Solving the recursion gives $T(m) = O(m \log m)$.

§.§ Proofs For Section <ref>.

§.§.§ Proof of Fact <ref>

Fact <ref>
The algorithm achieves every property of Algorithm as specified in Theorem <ref>, except that
the server has processing time $\tilde O( |\mcalU{} | + |\mcalD{}| )$ and memory usage $O(|\mcalD{}|)$.

The proof of Fact <ref> consists of Facts <ref>, <ref>, <ref>, and <ref>.

Running Time and Memory Usage.

The client-side running time is stated as follows.

Algorithm <ref> ($\algoHrrClient{}$) has running time $O(\log m) \subseteq O(\log | \mcalD{} |)$.

According to Fact <ref>, the entry $\mrmH[r, v]$ can be computed in $O(\log m) \subseteq O(\log | \mcalD{} |)$ time.

We discuss the server side running time and memory usage.

The server needs memory of size $O(m) \subseteq O(| \mcalD{} |)$ to store the vector $\pmbomega$. Processing responses from the users in $\mcalU{}$ takes time $O(| \mcalU{} |)$. By Fact <ref>, $\mrmH{}^T \pmbomega{}$ can be computed in $O(m \log m) \subseteq \tilde O( | \mcalD{} |)$ time, with memory usage $O(m) \subseteq O(| \mcalD{} |)$. Hence the overall running time is $\tilde O(| \mcalD{} | + | \mcalU{} |)$ and memory usage is $O(| \mcalD{} |)$.

Privacy Guarantee.

Algorithm <ref> ($\algoHrrClient$) is $\eps$-locally differentially private.

We need to prove that the output distribution of $\algoHrrClient{}$ deviates little with the value $v \in \mcalD{}$, the user's element.
To explicitly state the dependence of $\algoHrrClient$ on $v$, we write its output as $\algoHrrClient{}(r, \eps; v)$.
It suffices to prove that $\forall v, v' \in \mcalD{}$, the output distributions of $\algoHrrClient{}(r, \eps; v)$ and $\algoHrrClient{}(r, \eps; v')$ are similar.
There are only two possible outputs, namely, $\{ - 1, 1\}$. Let $b$ and $b'$ be the Rademacher random variables generated by $\algoHrrClient{}(r, \eps; v)$ and $\algoHrrClient{}(r, \eps; v')$ respectively.

\begin{align*}
&\Pr[ \algoHrrClient{}(r, \eps; v) = 1 ] = \Pr[ b \cdot \mrmH[ r, v ] = 1] \le e^\eps / (e^\eps + 1)\,, \\
&\Pr[ \algoHrrClient{}(r, \eps; v') = 1 ] = \Pr[ b' \cdot \mrmH[ r, v' ] = 1] \ge 1 / (e^\eps + 1)\,.
\end{align*}

\frac{\Pr[ \algoHrrClient{}(r, \eps; v) = 1 ] }{ \Pr[ \algoHrrClient{}(r, \eps; v') = 1 ]} \le e^\eps.
Similarly, we can prove that
\frac{\Pr[ \algoHrrClient{}(r, \eps; v) = -1 ] }{ \Pr[ \algoHrrClient{}(r, \eps; v') = -1 ]} \le e^\eps.
By Definition <ref>, the algorithm $\algoHrrClient{}$ is $\eps$-differentially private.

Utility Guarantee.

Let $\hat f_\mcalU{}$ be the estimate vector returned by Algorithm <ref>. Then for all $v \in \mcalD{}$, $\hat f_\mcalU{} [v ]$ is an unbiased estimator of $f_\mcalU{} [v ]$.

For each $i \in [m]$, let $\pmbe{}_i$ be the $i^{\text{th}}$ standard basis vector.
For each user $u \in \mcalU{}$, let $\pmbc^{ (u)} \doteq \mrmH \ \pmbe{}_{ v^{ (u) } }$ be the column assigned to $u$, i.e., the $(v^{(u)})^\text{th}$ column of the Hadamard matrix $\mrmH$, and let $b^{(u)}$ be the Rademacher random variable generated when algorithm $\algoHrrClient{}$ is invoked for user $u$. Let $\ceps{} \doteq (e^\eps + 1) / (e^\eps - 1)$.
By algorithm $\algoHrrClient$, the response from user $u$ can be expressed as $\omega^{ (u) } = b^{ (u) } \cdot \pmbc^{ (u) } [ r^{ (u) } ]$. When the server receives the response $\omega^{(u)}$, the update of $\pmbomega$ can be rewritten as

\pmbomega{} \leftarrow \pmbomega{} +  \ceps{} \cdot  \omega^{ (u) } \cdot \pmbe{}_{ r^{ (u) } }\,.

Hence $\pmbomega{} = \sum_{u \in \mcalU{} } \ceps{} \cdot  \omega^{ (u) } \cdot \pmbe{}_{ r^{ (u) } } = \sum_{u \in \mcalU{} } \ceps{} \cdot b^{ (u) } \cdot \pmbc^{ (u) } [ r^{ (u) } ] \cdot \pmbe{}_{ r^{ (u) } }$, where $\pmbe{}_{ r^{ (u) } }$ is the $(r^{(u)})^\text{th}$ standard basis vector.
Let $\pmbc_{ v } \doteq \mrmH \ \pmbe{}_{ v }$ be the $v^{\text{th}}$ column of $\mrmH$.
Since $\hat f_\mcalU{} = \mrmH^T \ \pmbomega{}$, we have

\hat f_\mcalU{} [ v ] = \left< \pmbc{}_{v },  \pmbomega{} \right>
= \sum_{u \in \mcalU{} } \ceps{} \cdot b^{ (u) } \cdot \pmbc^{ (u) } [ r^{ (u) } ] \cdot \left< \pmbc{}_{v }, \pmbe{}_{ r^{ (u) } } \right>
= \sum_{u \in \mcalU{} } \ceps{} \cdot b^{ (u) } \cdot \pmbc^{ (u) } [ r^{ (u) } ] \cdot \pmbc{}_{v } [ r^{ (u) } ]\,.

By the independence of $b^{ (u) }$ and $r^{ (u) }$, and by linearity of expectation, we have

\E \left[ \hat f_\mcalU{} [ v ] \right]
= \sum_{u \in \mcalU{} } \ceps{} \cdot \E[ b^{ (u) } ] \cdot \E \left[ \pmbc^{ (u) } [ r^{ (u) } ] \cdot \pmbc{}_{v } [ r^{ (u) } ] \right]
= \sum_{u \in \mcalU{} }  \E \left[ \pmbc^{ (u) } [ r^{ (u) } ] \cdot \pmbc{}_{v } [ r^{ (u) } ] \right]\,

The second equality follows from

$$\E[ b^{ (u) } ] = 1 \cdot \frac{ e^\eps }{ e^\eps + 1} + (-1) \cdot \frac{1}{e^\eps + 1} = 1 / \ceps{}\,.$$

As $r^{ (u) }$ is sampled uniformly from $[m]$, it holds that

\sum_{u \in \mcalU{} }  \E \left[ \pmbc^{ (u) } [ r^{ (u) } ] \cdot \pmbc{}_{v } [ r^{ (u) } ] \right]
= \sum_{u \in \mcalU{} } \frac{1}{m } \cdot  \sum_{j = 1}^m \left( \pmbc{}^{ (u) } [j] \cdot \pmbc{}_{v } [j] \right)
= \sum_{u \in \mcalU{} } \frac{1}{m }  \cdot  \left< \pmbc{}^{ (u) }, \pmbc{}_{v } \right>
= \sum_{u \in \mcalU{} } \dsone{} [ v = v^{ (u) } ]\,.

The final equality follows from the orthogonality of columns of $\mrmH$, and that $\left< \pmbc{}_{v }, \pmbc{}_{v } \right> = m$. We conclude that $\E \left[ \hat f_\mcalU{} [ v ] \right] = \sum_{u \in \mcalU{} } \dsone{} [ v = v^{ (u) } ] = f_\mcalU{} [ v ]$.

For a fixed $v \in \mcalD{}$ and for all $\beta' \in (0, 1)$, with probability at least $1 - \beta'$, it holds that

\begin{align*}
| \hat f_\mcalU{} [v ] - f_\mcalU{} [v ] | \in O\left( (1 / \eps) \cdot \sqrt{ | \mcalU{} | \cdot \ln ( {1} / {\beta'} ) } \right)\,.
\end{align*}

For each $u \in \mcalU{}$, define $Z^{ (u) } \doteq \ceps{} \cdot b^{ (u) } \cdot \pmbc^{ (u) } [ r^{ (u) } ] \cdot \pmbc{}_{v } [ r^{ (u) } ]$. The $\{Z^{ (u) }\}$ are independent random variables in the range of $[-\ceps{}, \ceps{}]$. As $\hat f_\mcalU{} [v ] = \sum_{ u \in \mcalU{} } Z^{ (u) }$ and $\E \left[ \hat f_\mcalU{} [ v ] \right] = f_\mcalU{} [ v ]$, by Hoeffding's inequality (Fact <ref>), for all $\eta > 0$,

\Pr \left[ \left| \hat f_\mcalU{} [ v ] -  f_\mcalU{} [ v ]\right| \ge  \eta \right] \le 2 \exp \left( - \frac{ 2 \eta^2 }{ \sum_{u \in \mcalU{} } (\ceps{} - (-\ceps{}) )^2 } \right)\,.

If we upper bound the failure probability with $\beta'$, we obtain that $\eta \le \ceps{} \cdot \sqrt{ 2 | \mcalU{} | \ln \frac{2}{\beta'}} = \frac{e^\eps + 1}{e^\eps - 1} \sqrt{ 2 | \mcalU{} | \ln \frac{2}{\beta'}}$, which finishes the proof.

§.§ Proof For

Lemma <ref>.
For $i = 0, 1$; $k \in \N^+$, $\exists$ $C_i > 0$, s.t., with probability $1 - \beta'$: $\Delta_i \le C_i \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }$ .

We need to prove Lemma <ref> for both independent partitioning and permutation partitioning.

§.§.§ Proof of Lemma <ref> for Independent Partitioning.

Without loss of generality, assume that $\mcalU{} = \{ 1, 2, .., | \mcalU{} | \}$.
For each $u \in \mcalU{} $, let $X_u \in [k]$ be the index of the subset that user $u$ belongs to. Let $\mbfX{} \doteq (X_1,  \ldots, X_{ | \mcalU{} | })$: by definition, for each $j \in [k]$, $\Pr[ X_u = j ] = 1 / k$. The set $\mcalU{}_j$ can be represented as

\mcalU{}_j \doteq \{ u \in \mcalU{}  : X_u = j \}\,.

Now, $\Delta_0$ can be rewritten as

\Delta_0 = \sum_{j \in [k] } \sqrt{ \left( \sum_{ u \in \mcalU } \dsone{} \left[ X_u = j \right] - |\mcalU{}| / k \right)^2 }\,,

where $\dsone{} \left[ X_u = j \right]$ is the indicator random variable for the event $X_u = j$.
Similarly, we have for each $v \in \mcalD{}$,
f_\mcalU{}_j [ v ] = \sum_{ u \in \mcalU{}_j } \dsone{} \left[ v^{ ( u ) } = v \right],
where $\dsone{} \left[ v^{ ( u ) } = v \right]$ is the indicator random variable for the event $v^{ ( u ) } = v$. Then,

\left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2
= \sqrt{ \sum_{ v \in \mcalD{} } \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 }
= \sqrt{ \sum_{ v \in \mcalD{} } \left( \sum_{ u \in \mcalU{}_j } \dsone{} \left[ v^{ ( u ) } = v \right] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 }.

Recall that $\Delta_1 = \sum_{j \in [k] } \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$.
Hence, each of $\Delta_0$ and $\Delta_1$ is a random variables that depends on $\mbfX{}$.
For $i = 0, 1$, we write $\Delta_i$ explicitly as $\Delta_i(X_1, \ldots, X_{ | \mcalU{} | })$ or $\Delta_i(\mbfX{})$ when necessary.
For a sequence of values $\pmbx{} = \{ x_1, \ldots, x_{ | \mcalU{} | } \} \in [k]^{ | \mcalU{} | }$, we use $\Delta_i (x_1, \ldots, x_{ | \mcalU{} | })$ or $\Delta_i (\pmbx{})$ to denote the value of $\Delta_i$, when $\mbfX{} = \pmbx{}$.
Observe that

\Delta_i = \Delta_i - \E[ \Delta_i ] + \E[ \Delta_i ].

In order to upper bound $\Delta_i$, we can upper bound both $\Delta_i - \E[ \Delta_i]$ and $\E[ \Delta_i]$.

The proof consists of two steps. We will bound $\Delta_0 - \E[ \Delta_0 ]$ by $\sqrt{ 2 | \mcalU{} | \ln \frac{1}{\beta'} }$ and $\E[ \Delta_0 ]$ by $\sqrt{ k  | \mcalU{} | }$.

Step 1: Bounding $\Delta_0 - \E[ \Delta_0]$.
We upper bound it by McDiarmid’s Inequality (Fact <ref>).

We will prove that $\Delta_0$ satisfies Lipschitz condition (Definition <ref>) with bound $2$, i.e., for all $u \in \mcalU{} $, and every sequence of values $\pmbx{} = \{ x_1, \ldots,x_u, \ldots, x_{ | \mcalU{} | } \} \in [k]^{| \mcalU{} |}$ and $x_u' \in [k]$,

\begin{equation} \label{ineq: delta0-lipschitz}
| \Delta_0(x_1, \ldots, x_u, \ldots, x_{ | \mcalU{} | }) - \Delta_0(x_1, \ldots, x_u', \ldots, x_{ | \mcalU{} | }) | \le 2\,.
\end{equation}

Then by McDiarmid’s Inequality,

\Pr\left[ \Delta_0 - \E[ \Delta_0] \ge \sqrt{ 2 | \mcalU{} | \ln \frac{1}{\beta'} } \right] \le \exp \left( - \frac{  2 \left( \sqrt{ 2 | \mcalU{} | \ln \frac{1}{\beta'} } \right)^2  }{ | \mcalU{} | ( 2 )^2 } \right) \le \beta'\,.

Proof of Lipschitz condition.
Define a random vector in $\R^k$ that depends on $\mbfX{}$ as

\pmbomega (\mbfX{} ) \doteq \left( \sum_{ u \in \mcalU } \dsone{} \left[ X_u = 1 \right] - \frac{|\mcalU{}|} {k}, \ \ldots, \ \sum_{ u \in \mcalU } \dsone{} \left[ X_u = k \right] - \frac{|\mcalU{}|} { k} \right).

For a sequence of values $\pmbx{} = \{ x_1, \ldots,x_u, \ldots, x_{ | \mcalU{} | } \} \in [k]^{| \mcalU{} |}$ , let $\pmbomega (\pmbx{} )$ be the vector $\pmbomega (\mbfX{} )$ when $\mbfX{} = \pmbx{}$.
By the definition of $\Delta_0$, we have $\Delta_0 (\pmbx{} ) = \Vert \pmbomega ( \pmbx{} ) \Vert_1$.
Consider a fixed $u \in \mcalU{} $.
Let $\pmbx{}' = \{ x_1, \ldots, x_u', \ldots, x_{ | \mcalU{} | } \}$ be the sequence obtained by replacing $x_u$ with $x_u'$.
The inequality (<ref>) clearly holds when $x_u = x_u'$.
Considering the case $x_u \neq x_u'$,
suppose that $x_u = j$ and $x_u' = j'$ for different $j, j' \in [k]$.
The $\pmbomega( \pmbx{} )$ and $\pmbomega( \pmbx{}' )$ differ in only two coordinates, each by 1.
By the triangle inequality,

\left| \left\Vert \pmbomega( \pmbx{} ) \right\Vert_1 - \left\Vert \pmbomega( \pmbx{}' ) \right\Vert_1 \right| \le {1  + 1 } = 2.

Step 2: Bounding $\E[ \Delta_0 ]$.

By Jensen's inequality, it holds  that

\begin{align*}
\E\left[ \Delta_0 \right]
=  \sum_{j \in [k] } \E \left[ \sqrt{ \left( \sum_{ u \in \mcalU } \dsone{} \left[ X_u = j \right] - |\mcalU{}| / k \right)^2 } \right]
\le \sum_{j \in [k] } \sqrt{ \E\left[ \left( \sum_{ u \in \mcalU } \dsone{} \left[ X_u = j \right] - |\mcalU{}| / k \right)^2  \right] }\,.
\end{align*}

Fix a $j \in [k]$. For all $u \in \mcalU{}$, define the indicator random variable $Z^{ (u) } \doteq \dsone{} [ X_u = j ]$ for the event $u \in \mcalU{}_j$.
Then $\Pr[ Z^{ (u) } = 1 ] = 1 / k$ and $\Pr[ Z^{ (u) } = 0 ] = 1 - 1 / k$.
| \mcalU{}_j | = \sum_{ u \in \mcalU{} [ v ] } Z^{ (u) },
is a sum of $|\mcalU{}|$ independent random variables and has expectation $|\mcalU{}| / k$.

\begin{align*}
\E\left[  \left( \sum_{ u \in \mcalU{} } Z^{ (u) } - |\mcalU{}| / k \right)^2 \right]
= \Var{} \left[  | \mcalU{}_j | \right]
=  \sum_{ u \in \mcalU{} } \Var{} \left[ Z^{ (u) } \right]
\le \frac{ | \mcalU{} | }{ k }\,.
\end{align*}

\E\left[ \Delta_0 \right]
\le \sum_{j \in [k] } \sqrt{  \E\left[ \left( \sum_{ u \in \mcalU } \dsone{} \left[ X_u = j \right] - |\mcalU{}| / k \right)^2  \right] }
\le \sum_{j \in [k] } \sqrt{ \frac{ | \mcalU{} | }{ k } }
= \sqrt{ k | \mcalU{} |  }\,.

The proof consists of two steps. We first bound $\Delta_1 - \E[ \Delta_1 ]$ by $\sqrt{ 2 | \mcalU{} | \ln \frac{1}{\beta'} }$ and then bound $\E[ \Delta_1 ]$ by $\sqrt{ k | \mcalU{} | }$.

Step 1: Bounding $\Delta_1  - \E[ \Delta_1 ]$.
We upper bound it by McDiarmid’s Inequality (Fact <ref>).

We  prove that $\Delta_1 $ satisfies the Lipschitz condition (Definition <ref>) with bound $2$, i.e., for all $u \in \mcalU{} $, and every sequence of values $\pmbx{} = \{ x_1, \ldots,x_u, \ldots, x_{ | \mcalU{} | } \} \in [k]^{ |\mcalU{} | }$ and $x_u' \in [k]$,

\begin{equation} \label{ineq:delta-lipschitz}
| \Delta_1 (x_1, \ldots, x_u, \ldots, x_{ | \mcalU{} | }) - \Delta_1 (x_1, \ldots, x_u', \ldots, x_{ | \mcalU{} | }) | \le 2\,.
\end{equation}

Then by McDiarmid’s Inequality,

\Pr\left[ \Delta_1  - \E[ \Delta_1 ] \ge \sqrt{2 | \mcalU{} | \ln \frac{1}{\beta'} } \right] \le \exp \left( - \frac{  2 \left( \sqrt{2 | \mcalU{} | \ln \frac{1}{\beta'} } \right)^2  }{ | \mcalU{} | 2^2 } \right) \le \beta'.

Proof of Lipschitz condition.
Consider a fixed $u \in \mcalU{} $. Let $\pmbx{}' = \{ x_1, \ldots, x_u', \ldots, x_{ | \mcalU{} | } \}$ be the sequence obtained by replacing $x_u$ with $x_u'$.
The inequality (<ref>) clearly holds when $x_u = x_u'$.
It is left to consider the case when $x_u \neq x_u'$.
Recall that $\Delta_1  = \sum_{j \in [k] } \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$.
Suppose that $x_u = j$ and $x_u' = j'$ for different $j, j' \in [k]$.
The $\Delta_1 ( \pmbx{} )$ and $\Delta_1 ( \pmbx{}' )$ differ only in two terms, namely, $\left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$ and $\left\Vert f_\mcalU{}_{j'} - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$.
Let $f_{\mcalU{}_j, \pmbx{} }$ and $f_{\mcalU{}_j, \pmbx{}' }$ be the frequency vectors when $\mbfX{} = \pmbx{}$ and $\mbfX{} = \pmbx{}'$, respectively.

If we view $f_{\mcalU{}_j, \pmbx{} } - \frac{ f_\mcalU{} }{ k }$ and $f_{\mcalU{}_j, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k }$ as $|\mcalD{}|$-dimensional vectors, they differ only by $1$ in the $( v^{ (u) } )^\text{th}$ coordinate, i.e.,

\left( f_{\mcalU{}_j, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right) - \left( f_{\mcalU{}_j, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k } \right) =  \pmbe{}_{ v^{ (u) } }\,,

where $\pmbe{}_{ v^{ (u) } }$ is the $v^{ (u) }$-th standard basis vector in $\R^{ |\mcalD{} | }$. By the triangle inequality,

\left\Vert  f_{\mcalU{}_j, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 - \left\Vert f_{\mcalU{}_j, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 \le \Vert \pmbe{}_{ v^{ (u) } } \Vert_2 = 1\,.

Similarly, let $f_{\mcalU{}_{j'}, \pmbx{} }$ and $f_{\mcalU{}_{j'}, \pmbx{}' }$ be the frequency vectors when $\mbfX{} = \pmbx{}$ and $\mbfX{} = \pmbx{}'$ respectively. It holds that

\left\Vert  f_{\mcalU{}_{j'}, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 - \left\Vert f_{\mcalU{}_{j'}, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 \le \Vert \pmbe{}_{ v^{ (u) } } \Vert_2 = 1\,.

Therefore, $| \Delta_1 ( \pmbx{} ) - \Delta_1 ( \pmbx{}' ) | \le 2$.

Step 2: Bounding $\E[ \Delta_1 ]$. By linearity of expectation,

\E[ \Delta_1  ] = \sum_{j \in [k] }
\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right].

For a fixed $j \in [k]$, by Jensen's inequality, it holds  that

\begin{align*}
\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right]
=  \E\left[ \sqrt{ \sum_{ v \in \mcalD{} } \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 } \right]
\le \sqrt{ \sum_{ v \in \mcalD{} } \E\left[  \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 \right] }\,.
\end{align*}

For a fixed $v \in \mcalD{}$, define $\mcalU{}[v ] \doteq \{ u \in \mcalU{} : v^{ (u) } = v \}$ as the set of users holding element $v$.
It holds that $| \mcalU{}[v ] | = f_\mcalU{} [ v ]$.
For each $u \in \mcalU{} [v]$, define the indicator random variable $Z^{ (u) } \doteq \dsone{} [ X_u = j ]$ for the event $u \in \mcalU{}_j$.
Then $\Pr[ Z^{ (u) } = 1 ] = 1 / k$ and $\Pr[ Z^{ (u) } = 0 ] = 1 - 1 / k$.
f_\mcalU{}_j [ v ] = \sum_{ u \in \mcalU{} [ v ] } Z^{ (u) },
is a sum of $f_\mcalU{} [ v ]$ independent random variables with expectation $f_\mcalU{} [ v ] / k$. Hence,

\begin{align*}
\E\left[  \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 \right]
% &= \E\left[  \big( f_\mcalU{}_j [ v ] -  \E \big[ f_\mcalU{}_j [ v ] \big] \big)^2 \right]
= \Var{} \left[  f_\mcalU{}_j [ v ] \right]
&=  \sum_{ u \in \mcalU{} [ v ] } \Var{} \left[ Z^{ (u) } \right]
\le \frac{ f_\mcalU{} [ v ] }{ k }\,.
\end{align*}

\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right] \le \sqrt{ \sum_{ v \in \mcalD{} } \E\left[  \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 \right] } \le \sqrt{ \sum_{ v \in \mcalD{} } \frac{ f_\mcalU{} [ v ] }{ k } } = \sqrt{ \frac{| \mcalU{} |}{k} }\,,

\E[ \Delta_1  ] = \sum_{j \in [k] }
\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right] \le \sqrt{ | \mcalU{} | k }\,.

§.§.§ Proof of Lemma <ref> for Permutation Partitioning.

In this case, we have $\Delta_0 = 0$. We need only bound $\Delta_1$; we bound $\Delta_1 - \E[ \Delta_1 ]$ by $2 \sqrt{  | \mcalU{} | \ln \frac{2}{\beta'} }$ and $\E[ \Delta_1 ]$ by $\sqrt{ k | \mcalU{} | }$.

WLOG, assume that $\mcalU{} = \{ 1, \ldots, | \mcalU{} | \}$.
Let $\mbfX{} = (X_1, X_2, \ldots, X_{ | \mcalU{} | })$ be a random permutation of $\mcalU{}$, i.e., one chosen uniformly at random from the set of all possible permutation of $\mcalU{}$. Note that $X_1, \ldots, X_{ | \mcalU{} | }$ are dependent random variables.

By the way we generate $\mcalU{}_j$, it has size $| \mcalU{} | / k$ and $\mcalU{}_j = \left\{ X_i :  (j - 1) \cdot | \mcalU{} | / k + 1 \le i \le j \cdot | \mcalU{} | / k \right\}$. For every $v \in \mcalD{}$, we can write

f_\mcalU{}_j [ v ] = \sum_{ X_i \in \mcalU{}_j } \dsone{} \left[ v^{ ( X_i ) } = v \right]\,,

where $\dsone{} \left[ v^{ ( X_i ) } = v \right]$ is the indicator random variable for the event $v^{ ( X_i ) } = v$.

\left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2
= \sqrt{ \sum_{ v \in \mcalD{} } \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 }
= \sqrt{ \sum_{ v \in \mcalD{} } \left( \sum_{ X_i \in \mcalU{}_j } \dsone{} \left[ v^{ ( X_i ) } = v \right] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 }\,.

Now, $\Delta_1 = \sum_{j \in [k] } \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$ is a function that depends on $\mbfX{}$;
we write $\Delta_1$ explicitly as $\Delta_1(\mbfX{})$ or $\Delta_1(X_1, \ldots, X_{ | \mcalU{} | })$ when necessary.
For a sequence of values $\pmbx{} = \{ x_1, \ldots, x_{ | \mcalU{} | } \}$, we use $\Delta_1 (x_1, \ldots, x_{ | \mcalU{} | })$ or $\Delta_1 (\pmbx{})$ to denote the value of $\Delta_1$, when $\mbfX{} = \pmbx{}$.

Martingale Construction. To construct a martingale that satisfies Definition <ref>, we introduce a dummy random variable $X_0 \equiv 0$.
To ease the notation, let $\mbfS{}_0 = ( X_0 )$ and for $1 \le i \le |\mcalU{} |$, let $\mbfS{}_i$ be shorthand for $(X_1, \ldots, X_i)$, and

Y_i \doteq \E[ \Delta_1 \mid \mbfS{}_i ]\,.

The $Y_i$ is a function of $X_0, \ldots, X_i$ and $\E[ |Y_i| ] \le \infty$.

\E[ Y_{i + 1} \mid \mbfS{}_i ] = \E \big[ \E[ \Delta_1 \mid \mbfS{}_i, X_{i + 1} ] \mid  \mbfS{}_i \big] = \E[ \Delta_1 \mid \mbfS{}_i ] = Y_i\,.

The sequence $Y_0, \ldots, Y_{ | \mcalU{} | } $ satisfies all conditions specified in Definition <ref> and is a martingale.
By definition, $Y_{ | \mcalU{} | }  = \E [ \Delta_1 \mid \mbfS{}_{ | \mcalU{} |  } ] = \Delta_1$, as once the values of $X_1, \ldots, X_{ | \mcalU{} | }$ are determined, so is $\Delta_1$.

Observe that

\Delta_1 = \Delta_1 - \E[ \Delta_1] + \E[ \Delta_1] = Y_{ | \mcalU{} | }  - Y_0 + Y_0\,,

In order to upper bound $\Delta_1$, we can upper bound both $Y_{ | \mcalU{} | }  - Y_0$ and $Y_0$.

Step 1: Bounding $Y_{ | \mcalU{} | }  - Y_0$.
We upper bound it via Azuma's Inequality (Fact <ref>).
We prove that,

\begin{equation} \label{ineq: martingale diff 1}
A_i \le Y_i - Y_{i - 1}  \le A_i + 2 \sqrt{2}\,,
\end{equation}

for some random variables $\{A_i\}$ that are functions of $X_0, \ldots, X_{i - 1}$.
By Azuma's inequality,

\Pr\left[ |Y_{ | \mcalU{} | }  - Y_0| \ge \left( 2 \sqrt{| \mcalU{} | \ln \frac{2}{\beta'} } \right) \right] \le 2 \exp \left( - \frac{  2 \left( 2 \sqrt{| \mcalU{} | \ln \frac{2}{\beta'} } \right)^2  }{ \sum_{i \in \mcalU{} } (2 \sqrt{2} )^2 } \right) \le \beta'\,.

Proof of Inequality (<ref>). We prove that the gap between the upper and lower bounds on $Y_i - Y_{i - 1}$ is at most $2 \sqrt{2}$. By the definitions of $Y_i$ and $Y_{i - 1}$,

Y_i - Y_{i - 1}  = \E[ \Delta_1 \mid \mbfS{}_i ] - \E[ \Delta_1 \mid \mbfS{}_{i - 1} ]\,.

Let $\mcalU{} \setminus \mbfS{}_{i - 1}$ be the set of integers in $\mcalU{}$ that are distinct from $X_1, \ldots, X_{i - 1}$.

\begin{align*}
A_i = \inf_{ x \in \mcalU{} \setminus \mbfS{}_{i - 1} } \E[ \Delta_1 \mid \mbfS{}_{i - 1}, X_i = x ] - \E[ \Delta_1 \mid \mbfS{}_{i - 1} ]\,, \text{ and}
\\
B_i = \sup_{ x' \in \mcalU{} \setminus \mbfS{}_{i - 1} } \E[ \Delta_1 \mid \mbfS{}_{i - 1}, X_i = x' ] - \E[ \Delta_1 \mid \mbfS{}_{i - 1} ]\,.
\end{align*}

Clearly $A_i \le Y_i - Y_{i - 1} \le B_i$.
We  prove that $B_i - A_i \le 2 \sqrt{2}$.
Let $\pmbx{}_0 = ( 0 )$ and for each $i \ge 2$, $\pmbx{}_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mcalU{}^{i - 1}$ be the first $i - 1$ entries of a possible permutation of $\mcalU{}$.
Let $\mcalU{} \setminus \pmbx{}_{i - 1}$ be the set of integers in $\mcalU{}$ that are distinct from $x_1, \ldots, x_{i - 1}$.
Conditioned on $\mbfS{}_{i - 1} = \pmbx{}_{i - 1}$,

\begin{align*}
B_i - A_i
&= \sup_{ x' \in \mcalU{} \setminus \pmbx{}_{i - 1} } \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x' ] - \inf_{ x \in \mcalU{} \setminus \pmbx{}_{i - 1} }\E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x ] \\
&= \sup_{ x', x \in \mcalU{} \setminus \pmbx{}_{i - 1} } \left( \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x' ] - \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1},  X_i = x ] \right)\,.
\end{align*}

It suffices to bound this for every possible sequence of $\pmbx{}_{i - 1}$.

Consider a fixed $i \in \mcalU{}$ and $\pmbx{}_{i - 1}$. Define

\gamma_{x', x} \doteq \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x' ] - \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x ] \,.

Our goal is to prove for all $x', x \in \mcalU{} \setminus \pmbx{}_{i - 1}$, $\gamma_{x', x'} \le 2 \sqrt{2}$.
It follows that $\sup_{ x', x \in \mcalU{} \setminus \pmbx{}_{i - 1} } \gamma_{x', x'} \le 2 \sqrt{2}$.
If $x' = x$, then $\gamma_{x', x'} = 0$.
Suppose $x' \neq x$.
As $\mbfX{}$ is a random permutation of $\mcalU{}$, conditioned on $\mbfS{}_{i - 1} = \pmbx{}_{i - 1}$ and $X_i = x'$, with equal probability, one of the elements $X_{i + 1}, \ldots, X_{ | \mcalU{} | }$ equals $x$.

\E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x' ]
= \frac{1}{ | \mcalU{} | - i} \sum_{ \ell = i + 1 }^{ | \mcalU{} | } \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x', X_\ell  = x ]\,.

Similarly, it holds that

\E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x ]
= \frac{1}{ | \mcalU{} | - i} \sum_{ \ell = i + 1 }^{ | \mcalU{} | } \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x, X_\ell  = x' ]\,.

By triangle inequality,

\gamma_{x', x}
= \frac{1}{ | \mcalU{} | - i} \sum_{ \ell = i + 1 }^{ | \mcalU{} | }
\left[
\E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x', X_\ell  = x ]
- \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x, X_\ell  = x' ]
\right]

For all permutation sequences $\pmbx{} = (x_1, \ldots, x_{ | \mcalU{} | })$ and for all $i \neq \ell \in \mcalU{}$, define $\pmbx{}_{i, \ell}$ to be the sequence with the values of $x_i$ and $x_\ell$ being swapped. We claim it holds that

\begin{equation} \label{ineq:swap-diff}
| \Delta_1( \pmbx{} ) - \Delta_1( \pmbx{}_{i, \ell} ) | \le 2 \sqrt{2},
\end{equation}

This proves that

\E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x', X_\ell  = x ]
- \E[ \Delta_1 \mid \mbfS{}_{i - 1} = \pmbx{}_{i - 1}, X_i = x, X_\ell  = x' ]  \le 2 \sqrt{2}

and that $ \gamma_{x', x} \le 2 \sqrt{2}$.

To prove Inequality (<ref>), recall that $\Delta_1 = \sum_{j \in [k] } \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$.

If $v^{ (x_i) } = v^{ ( x_\ell )}$ or there exists some $j \in [k]$, s.t. both $x_i, x_\ell \in \mcalU{}_j$, then the swap does not change $\Delta_1$, and $| \Delta_1( \pmbx{} ) - \Delta_1( \pmbx{}_{i, \ell} ) | = 0$.

Otherwise, $v^{ (x_i) } \neq v^{ (x_\ell )}$ and $x_i \in \mcalU{}_j$, $x_\ell \in \mcalU{}_{j'}$ for different $j, j' \in [k]$. The swap affects only $\left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$ and $\left\Vert f_\mcalU{}_{j'} - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$.
Let $f_{\mcalU{}_j, \pmbx{} }$ and $f_{\mcalU{}_j, \pmbx{}_{i, \ell} }$ be the frequency vectors when $\mbfX{} = \pmbx{}$ and $\mbfX{} = \pmbx{}_{i, \ell}$, respectively.
They differ in both the $( v^{ (x_i ) } )^\text{th}$ and $( v^{ (x_\ell ) } )^\text{th}$ coordinates, each by 1.

If we view $f_{\mcalU{}_j, \pmbx{} } - \frac{ f_\mcalU{} }{ k }$ and $f_{\mcalU{}_j, \pmbx{}_{i, \ell} } - \frac{ f_\mcalU{} }{ k }$ as $|\mcalD{}|$-dimensional vectors, it holds that

\left( f_{\mcalU{}_j, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right) - \left( f_{\mcalU{}_j, \pmbx{}_{i, \ell} } - \frac{ f_\mcalU{} }{ k } \right) = - \pmbe{}_{ v^{ (x_{i} ) } } + \pmbe{}_{ v^{ (x_\ell ) } },

where $\pmbe{}_{ v^{ (x_{i} ) } }$ and $\pmbe{}_{ v^{ (x_\ell ) } }$ are the $v^{ (x_{i} ) }$-th and the $v^{ (x_\ell ) }$-th standard basis vectors in $\R^{ |\mcalD{} | }$ respectively. By the triangle inequality,

\left\Vert  f_{\mcalU{}_j, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 - \left\Vert f_{\mcalU{}_j, \pmbx{}_{i, \ell} } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 \le \Vert - \pmbe{}_{ v^{ (x_{i} ) } } + \pmbe{}_{ v^{ (x_\ell ) } } \Vert_2 = \sqrt{2}.

Similarly, we can prove that the change of $\left\Vert f_\mcalU{}_{j'} - \frac{ f_\mcalU{} }{ k }  \right\Vert_2$ is bounded by $\sqrt{2}$. Therefore, $| \Delta_1( \pmbx{} ) - \Delta_1( \pmbx{}_{i, \ell} ) | \le 2 \sqrt{2}$.

Step 2: Bounding $Y_0$. By linearity of expectation,

Y_0 = \E[ \Delta_1 ] = \sum_{j \in [k] }
\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right].

For a fixed $j \in [k]$, by Jensen's inequality, it holds that

\begin{align*}
\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right]
=  \E\left[ \sqrt{ \sum_{ v \in \mcalD{} } \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 } \right]
\le \sqrt{ \sum_{ v \in \mcalD{} } \E\left[  \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 \right] }\,.
\end{align*}

Consider a fixed $v \in \mcalD{}$, define $\mcalU{} [ v ] \doteq \{ u \in \mcalU{} : v^{ (u) } = v \}$ as the set of users holding element $v$. It holds that $| \mcalU{}[ v ] | = f_\mcalU [ v ]$.
For each $u \in \mcalU{} [v]$, define the indicator random variable $Z^{ (u) }$ for the event $u \in { \mcalU{}_j }$.
Then $\Pr[ Z^{ (u) } = 1 ] = 1 / k$ and $\Pr[ Z^{ (u) } = 0 ] = 1 - 1 / k$.

f_{ \mcalU{}_j } [ v ] = \sum_{ u \in \mcalU{} [ v ] } Z^{ (u) },

is a sum of $f_\mcalU[ v ]$ dependent random variables with expectation $f_\mcalU[ v ] / k$. For a pair of users $u, u' \in \mcalU{}{} [ v ], u \neq u'$, due the permutation, if $u$ belongs to $\mcalU{}_j$, it is less likely that $u'$ belongs to $\mcalU{}_j$. In particular,

\begin{align*}
\Cov{} \left[ Z^{ (u) }, Z^{ (u') } \right]
&= \E\left[ Z^{ (u) } \cdot Z^{ (u') } \right] - \E\left[ Z^{ (u) } \right] \E \left[ Z^{ (u') } \right] \\
&= \binom{ | \mcalU{} | - 2}{ | \mcalU{} | / k - 2} / \binom{ | \mcalU{} | }{ | \mcalU{} | / k} - \left( \frac{1}{k} \right)^2 \\
&= \frac{ | \mcalU{} | / k \cdot ( | \mcalU{} | / k - 1)}{ | \mcalU{} | ( | \mcalU{} | - 1)} - \left( \frac{1}{k} \right)^2 \\
&\le 0\,.
\end{align*}

\begin{align*}
\E\left[  \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 \right]
&= \Var{} \left[ f_\mcalU{}_j [ v ] \right]
=  \sum_{ u \in \mcalU{}{} [ v ] } \Var{} \left[ Z^{ (u) } \right] +
\sum_{ u \neq u' \in \mcalU{} [ v ] } \Cov{} \left[ Z^{ (u) }, Z^{ (u') } \right]
\\
&\le \sum_{ u \in \mcalU{}{} [ v ] } \Var{} \left[ Z^{ (u) } \right]
= f_\mcalU [ v ] \cdot \frac{1}{k} \cdot \left( 1 - \frac{1}{k} \right) \le \frac{ f_\mcalU [ v ] }{ k }\,.
\end{align*}

\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right] \le \sqrt{ \sum_{ v \in \mcalD{} } \E\left[  \left( f_\mcalU{}_j [ v ] -  \frac{ f_\mcalU{} [ v ] }{ k} \right)^2 \right] } \le \sqrt{ \sum_{ v \in \mcalD{} } \frac{ f_\mcalU{} [ v ] }{ k } } = \sqrt{ \frac{ | \mcalU{} |}{k} }\,,

Y_0 = \E[ \Delta_1 ] = \sum_{j \in [k] }
\E\left[ \left\Vert f_\mcalU{}_j - \frac{ f_\mcalU{} }{ k }  \right\Vert_2 \right] \le \sqrt{  | \mcalU{} | k }\,.

§.§.§ Proof of Theorem <ref>

Theorem <ref>.
For $0 \le i \le 3$, with probability at least $1 - \beta'$, it holds that $|\goodset{}_i| > (1 - 1 / 8) k$.

We need to prove the Theorem for $\goodset{}_0, \goodset{}_1, \goodset{}_2, \goodset{}_3$, separately.

By Lemma <ref>, with probability at least $1 - \beta'$, it holds that $\Delta_0 \le C_0 \sqrt{ | \mcalU{} | \ln ( 1 / \beta' ) }$ for some constant $C_0$.
Recall that $\Delta_0 \doteq \sum_{j \in [k] } \sqrt{   ( | \mcalU{}_j | - | \mcalU{} | / k )^2 }$.

\sum_{j \in [k] } \left| | \mcalU{}_j | - | \mcalU{} | / k \right| \le C_0 \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }\,,

\sum_{j \in [k] } \big\vert k \cdot | \mcalU{}_j | - | \mcalU{} | \big\vert \le k C_0 \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }\,.

By a counting argument, the number of $j \in [k]$, such that $\big\vert k \cdot | \mcalU{}_j | - | \mcalU{} | \big\vert \ge 8 C_0 \sqrt{ | \mcalU{} | \ln ( 1 / \beta' ) }$ is bounded by $(1 / 8)k$. This implies that for at least $(1 - 1 / 8)k$  of the $j \in [k]$, we have

\big\vert k \cdot | \mcalU{}_j | - | \mcalU{} | \big\vert \le 8 C_0 \sqrt{ | \mcalU{} | \ln ( 1 / \beta' ) }\,.

By the assumption that $|\mcalU{}| \ge \ln ( 1 / \beta' )$, we get $\big\vert k \cdot | \mcalU{}_j | - | \mcalU{} | \big\vert \in \Theta (|\mcalU{}|)$, which finishes the proof.

By Lemma <ref>, with probability at least $1 - \beta'$, it holds that $\Delta_1 \le C_1 \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }$ for some constant $C_1$.
Recall that $\Delta_1 \doteq \sum_{j \in [k] } \Vert f_\mcalU{}_j - f_\mcalU{} / k \Vert_2$.
By a counting argument, the number of $j \in [k]$, such that $\Vert f_\mcalU{}_j - f_\mcalU{} / k \Vert_2 \ge \frac{8C_1}{k} \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }$ is bounded by $(1 / 8)k$. This implies that for at least $(1 - 1 / 8)k$ number of $j \in [k]$, we have

\Vert f_\mcalU{}_j - f_\mcalU{} / k \Vert_2 \le \frac{8C_1}{k} \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }\,.

\Vert k f_\mcalU{}_j - f_\mcalU{} \Vert_2 \le 8 C_1 \sqrt{ | \mcalU{} | \ln \frac{1}{\beta'} }\,,

which finishes the proof.

Consider a fixed $v \in \mcalD{}$. Recall that $\lambda_2 (j, v) \doteq | k f_{\mcalU{}_j, h_j} [ h(v) ] - k f_\mcalU{}_j [ v ] |$.
By definition of $\goodset{}_2$, it can be rewritten as

\goodset{}_2
= \left \{ j \in [k] : | k f_{\mcalU{}_j, h_j} [ h(v) ] - k f_\mcalU{}_j [ v ] | \in O \left( \frac{1}{\eps} \cdot \sqrt{ k \cdot |\mcalU{}_j | \ln \frac{1}{\beta'} } \right) \right\}\,.

The errors $| k f_{\mcalU{}_j, h_j} [ h(v) ] - k f_\mcalU{}_j [ v ] |$ are the result of hash collisions.
Next, we fix an index $j \in [k]$.
For each user $u \in \mcalU{}_j$, define the indicator random variable $X_u = \dsone{}[ h_j ( v^{ (u) } ) = h_j ( v ) ]$ for the event $h_j ( v^{ (u) } ) = h_j ( v) $.
Note that if $v^{ (u) } = v$, it always holds that $X_u = 1$.
Otherwise, as $h_j$ is a pairwise-independent hash function, $\Pr[ X_u = 1 ] = 1 / m$.

By definition, $f_{ \mcalU{}_j, h_j} [ h_j(v) ] = \sum_{u \in \mcalU{}_j } X_u$. Therefore,

\E \left[ \left| f_{ \mcalU{}_j, h_j} [ h_j (v) ] -  f_\mcalU{}_j [ v ] \right| \right]
= \E \left[ \left| \sum_{u \in \mcalU{}_j } X_u - f_\mcalU{}_j [ v ] \right| \right]
= \E \left[ \left| \sum_{u \in \mcalU{}_j, v^{ (u) } \neq v } X_u  \right| \right] \,.

By linearity of expectation, we have

\E \left[ \left| f_{ \mcalU{}_j, h_j} [ h_j (v) ] -  f_\mcalU{}_j [ v ] \right| \right] = \frac{ | u \in \mcalU{}_j, v^{ (u) } \neq v | }{ m } \le \frac{| \mcalU{}_j | }{ m }\,.

By Markov's inequality,

\begin{equation*}
\Pr \left[ \left| f_{ \mcalU{}_j, h_j} [ h_j (v) ] -  f_\mcalU{}_j [ v ] \right| \ge \frac{1}{\eps} \sqrt{ (1 / k) \cdot |\mcalU{}_j | \ln ( 1 / \beta') } \right] \le \frac{ | \mcalU{}_j | / m }{  \frac{1}{\eps}  \sqrt{ (1 / k) \cdot |\mcalU{}_j | \ln ( 1 / \beta') } } .
\end{equation*}

Using that fact that $k = C_K \cdot \ln ( 1 / \beta')$, $m = C_M \cdot \eps \cdot \sqrt{| \mcalU{} |}$ and $|\mcalU{}| \ge |\mcalU{}_j|$, the upper bound on the probability simplifies to $\frac{  \sqrt{C_k} }{ C_M}$.
If we set $C_M \doteq 8e^2 \sqrt{C_K}$ (we determine $C_K$ later), this upper bound further simplifies to $1 / (8e^2)$.
Hence, for each $j \in [k]$, with probability at most $1 / (8e^2)$,

| k f_{\mcalU{}_j, h_j} [ h(v) ] - k f_\mcalU{}_j [ v ] | \ge \frac{1}{\eps} \cdot \sqrt{ k \cdot |\mcalU{}_j | \ln ( 1 / \beta') }\,.

As the $h_1, .., h_k$ are chosen independently, this event happens independently for different $j \in [k]$.
The probability that there are more than $k / 8$ choices of $j \in [k]$ for which this event happens is at most

\begin{align*}
\binom{k }{k / 8} \left( \frac{1}{ 8e^2 } \right)^{ k / 8 }
\le \left( \frac{ e k }{ k / 8  } \right)^{k / 8} \left(  \frac{1}{ 8e^2 } \right)^{ k / 8 }
= \left( \frac{1}{e} \right)^{ k / 8 },
\end{align*}

where the first inequality follows from that $\binom{k}{k / 8} \le \frac{ k^{k / 8} }{ (k / 8)! }$ and that $\frac{ (k / 8)^{k / 8} }{ (k / 8)! } \le e^{k / 8}$.

Recall that $k = C_K \cdot {\ln \frac{1}{\beta'}}$. If we set $C_K \ge 8$, then we get
\left( \frac{1}{e} \right)^{ k / 8 } \le \beta',
which finishes the proof.

We apply algorithm to each $\mcalU{}_j$.
By Theorem <ref>, for every $j \in [k]$, it holds that with probability at least $1 - \frac{1}{8e^2}$,

\begin{equation} \label{ineq: subgroup_response_deviation}
| \hat f_{\mcalU{}_j, h_j} [ h(v) ] - f_{\mcalU{}_j, h_j} [ h(v) ] | \in O \left( \frac{1}{\eps} \cdot \sqrt{ | \mcalU{}_j |  \cdot \ln (8e^2) } \right) \subseteq O \left( \frac{1}{\eps} \cdot \sqrt{ | \mcalU{}_j | } \right)\,.
\end{equation}

In the case that $k = C_K \cdot \ln \frac{1}{\beta'}$, it holds that
O \left( \frac{1}{\eps} \cdot \sqrt{  k^2 | \mcalU{}_j | } \right) \subseteq O \left( \frac{1}{\eps} \cdot \sqrt{ k  | \mcalU{}_j | \cdot \ln \frac{1}{\beta'} } \right).
Hence, for each $j \in [k]$, it happens independently, with probability $1 / 8e^2$, that

| k \hat f_{\mcalU{}_j, h_j} [ h(v) ] - k f_{\mcalU{}_j, h_j} [ h(v) ] | \notin O \left( \frac{1}{\eps} \cdot \sqrt{  k | \mcalU{}_j | \cdot \ln \frac{1}{\beta'} } \right).

Therefore, the probability that there are more than $k / 8$ choices of $j \in [k]$ for which this event happens is at most
\binom{k }{k / 8} \left( \frac{1}{  8e^2 } \right)^{ \frac{k}{8 } } \le \beta'.

§.§ Proofs for

§.§.§ Proof for Theorem <ref>

Theorem <ref>.
$\forall \tau \in [L], \pmbs{} \in \Lambda^\tau$, it holds, with probability $1 - \beta'$,

| \hat f_\mcalU{} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] | \in O( ( 1 / \eps) \sqrt{ n \cdot (\log d) \cdot (\ln (1 / \beta') ) / \ln n } )\,.

First, $\forall \tau \in [L]$, define the $\ell_2$ distance between the frequency distribution $f_{\U_\tau }$ and its expectation $f_\mcalU{} / L$ as

\left\Vert f_{\U_\tau } - { f_\mcalU{} } / { L }  \right\Vert_2 \doteq \sqrt{ \sum_{ \pmbs{} \in \Lambda^\tau } \left( f_{\U_\tau } [ \pmbs{} ] -  { f_\mcalU{} [ \pmbs{} ] } / { L } \right)^2 }\,.

To prove Theorem <ref>, we need the following lemmas.

For each $\tau \in [L]$, with probability $1 - \beta'$, it holds that $| \U_\tau | \in O \left( n / L \right)$.

For each $\tau \in [L]$, with probability $1 - \beta'$, it holds that

\left\Vert f_{\U_\tau } - { f_\mcalU{} } / { L }  \right\Vert_2 \in O \left( \sqrt{ \frac{ n }{L} \ln \frac{1}{\beta'} } \right)\,.

Before proving the lemmas, we apply them to complete the proof of Theorem <ref>. For  each $\tau \in [L]$, each $\pmbs{} \in \Lambda^\tau$, we regard $\hat f_\mcalU{} [ \pmbs{} ] = L \cdot \hat f_{\U_\tau} [ \pmbs{} ]$ as an estimate of $f_\mcalU{} [ \pmbs{} ]$. By triangle inequality,

\left| L \cdot \hat f_{\U_\tau} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] \right|
\le \left| L \cdot \hat f_{\U_\tau} [ \pmbs{} ] - L \cdot f_{\U_\tau} [ \pmbs{} ] \right|
+ \left| L \cdot f_{\U_\tau} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] \right|,

where $\hat f_{\U_\tau} [ \pmbs{} ]$ is the estimate of $f_{\U_\tau} [ \pmbs{} ]$ returned by . By Theorem <ref> and Lemma <ref>, it holds with probability at least $1 - \beta'$,

\left| \hat f_{\U_\tau} [ \pmbs{} ] - f_{\U_\tau } [ \pmbs{} ] \right| \in O \left( \frac{1}{\eps} \sqrt{ | \U_\tau| \ln \frac{ 1 }{\beta'} } \right) \subseteq O \left( \frac{1}{\eps} \sqrt{ \frac{ | \mcalU{} | }{ L } \ln \frac{ 1 }{\beta'} } \right).

By Lemma <ref>, with probability at least $1 - \beta'$,

\left| f_{\U_\tau} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] / L \right| \le \left\Vert f_{\U_\tau } - f_\mcalU{} / L \right\Vert_2
\in O \left( \sqrt{ \frac{ | \mcalU{} | }{ L } \cdot \ln \frac{L}{\beta'} } \right)\,.

By a union bound, with probability at least $1 - 2 \beta'$, it holds that

\left| L \cdot \hat f_{\U_\tau} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] \right| \in O \left( \frac{1}{\eps} \sqrt{ | \mcalU{} | \cdot L \cdot \ln \frac{ 1 }{\beta'} } \right)\,.

We finish the proof by substituting $|\mcalU{}| = n$ and $L = 2 \cdot (\log d) / \log n$.

The claim is trivial, if we partition $\mcalU{}$ by permutation partitioning, as $|\U_\tau| = |\mcalU{}| / L$ for all $\tau \in [L]$.

It is left to prove the claim just for independent partitioning. Let us fix a $\tau \in [L]$, for each $u \in [n]$, define the indicator random variable $X_u$ that equals $1$ if $u \in \U_\tau$ and $0$ otherwise. Then $| \U_\tau | = \sum_{u \in [n] } X_u$, $\E[ | \U_\tau | ] = n / L$. By Chernoff bound <ref>, it holds that

\Pr[ | \U_\tau | > e n / L ] \le \left( \frac{ e^{e - 1} }{ e^e } \right)^{n / L} = \frac{1}{ e^{n / L} }\,.

Recall that $L = 2 \cdot (\log d) / \log n$. Further, in order that the bound $O \left( \frac{1}{\eps} \sqrt{ n \cdot \frac{\log d}{\log n} \cdot \ln \frac{1}{\beta'}} \right)$ in Theorem <ref> to be meaningful, we need the assumption that $n \ge \frac{1}{\eps^2} \cdot L \cdot \ln \frac{1}{\beta'}$. Therefore,

\frac{1}{ e^{n / L} } \le e^{ - \ln (1 / \beta') } = \beta'\,.

It concludes that  $|\U_\tau| \in O( n / L)$.

The proof of Lemma <ref> consists of two versions, one for permutation partitioning and one for independent partitioning.

Consider a fixed $\tau \in [L]$.
We have

\left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 \right] + \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 \right].

We will bound each term separately.

Bounding $\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 \right]$.
By Jensen's inequality,

\begin{align*}
\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L }  \right\Vert_2 \right] \le \sqrt{ \sum_{ \pmbs{} \in \Lambda^\tau } \E \left[ \left( f_{\U_\tau } [ \pmbs{} ] - \frac{ 1 }{ L } f_\mcalU [ \pmbs{} ]  \right)_2^2 \right] } = \sqrt{ \sum_{ \pmbs{} \in \Lambda^\tau } \Var \left[  f_{\U_\tau } [ \pmbs{} ] \right] }\,.
\end{align*}

For each user $u \in \mcalU{}$, define $\pmbs{}^{ (u) } \doteq v^{ (u) } [ 1 : \tau ]$, the prefix of $v^{ (u) }$ with length $\tau$.
Consider a fixed $\pmbs{} \in \Lambda^\tau$, define $\U[\pmbs{} ] \doteq \{ u \in \mcalU{} : \pmbs{}^{ (u) } = \pmbs{} \}$ as the set of users holding element $\pmbs{}$. It holds that $| \U{}[\pmbs{} ] | = f_\mcalU [ \pmbs{} ]$.
For all $u \in \U [\pmbs{}]$, define the indicator random variable $Z^{ (u) }$ to represent the event $u \in  \U_\tau $.
Then $\Pr[ Z^{ (u) } = 1 ] = 1 / L$ and $\Pr[ Z^{ (u) } = 0 ] = 1 - 1 / L$.

f_{ \U_\tau } [ \pmbs{} ] = \sum_{ u \in \U [ \pmbs{} ] } Z^{ (u) }\,,

is a sum of $f_\mcalU[ \pmbs{} ]$ dependent random variables with expectation $f_\mcalU[ \pmbs{} ] / L$. For a pair of users $u, u' \in \U{} [ \pmbs{} ], u \neq u'$, due to the permutation, if $u$ belongs to $\U_\tau$, it is less likely that $u'$ belongs to $\U_\tau$. In particular,

\begin{align*}
\Cov{} \left[ Z^{ (u) }, Z^{ (u') } \right]
&= \E\left[ Z^{ (u) } \cdot Z^{ (u') } \right] - \E\left[ Z^{ (u) } \right] \E \left[ Z^{ (u') } \right] \\
&= \binom{n - 2}{n / L - 2} / \binom{n}{n / L} - \left( \frac{1}{L} \right)^2 \\
&= \frac{ n / L \cdot (n / L - 1)}{n (n - 1)} - \left( \frac{1}{L} \right)^2 \\
&\le 0\,.
\end{align*}

\begin{align*}
\Var{} \left[  f_{ \U_\tau } [ \pmbs{} ] \right]
&=  \sum_{ u \in \U{} [ \pmbs{} ] } \Var{} \left[ Z^{ (u) } \right] +
\sum_{ u \neq u' \in \U{} [ \pmbs{} ] } \Cov{} \left[ Z^{ (u) }, Z^{ (u') } \right] \\
&\le \sum_{ u \in \U{} [ \pmbs{} ] } \Var{} \left[ Z^{ (u) } \right]
= f_\mcalU [ \pmbs{} ] \cdot \frac{1}{L} \cdot \left( 1 - \frac{1}{L} \right) \le \frac{ f_\mcalU [ \pmbs{} ] }{ L }\,.
\end{align*}

\E\left[ \left\Vert f_{ \U_\tau } - \frac{ f_\mcalU }{ L }  \right\Vert_2 \right] = \sqrt{ \sum_{ \pmbs{} \in \Lambda^\tau } \Var \left[  f_{\U_\tau } [ \pmbs{} ] \right] } \le \sqrt{ \sum_{ \pmbs{} \in \Lambda^\tau  } \frac{ f_\mcalU [ \pmbs{} ] }{ L } } = \sqrt{ \frac{n}{L} }\,.

Bounding $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 \right]$.
By symmetry, we prove just the case when $\tau = 1$.
Let $\mbfX{} = \{ X_1, \ldots, X_n \}$ be a random permutation of $[n]$.
As $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2$ is a function that depends on $\mbfX{}$, we write it explicitly as $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2(X_1, \ldots, X_n)$ or $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2(\mbfX{})$ when necessary.
For a possible permutation $\pmbx{} = \{ x_1, \ldots, x_n \}$ of $[n]$, we use $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2(x_1, \ldots, x_n)$ or $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2(\pmbx{})$ to denote the value of $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2$ when $\mbfX{} = \pmbx{}$.
Let $\gsize = n / L$. For each possible permutation $\pmbx{}$, $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2 ( \pmbx{} )$ does not change its value under the change of order of the first $\gsize$ and/or last $n - \gsize$ coordinates $\pmbx{}$. Hence, $\left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2$ is $(\gsize, n - \gsize)$-symmetric (Definition <ref>).

We prove that for each possible permutation $\pmbx{}$, for all $i \in \{1, \ldots, \gsize \}, j \in \{ \gsize + 1, \ldots, n \}$, it holds that

\begin{equation} \label{ineq: f tau 1 permutaion swap change}
\left| \left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2 ( \pmbx{} ) - \left\Vert f_{\U_1 } - \frac{ f_\mcalU }{ L }  \right\Vert_2 ( \pmbx{}_{i, j} ) \right| \le \sqrt{2}\,,
\end{equation}

where the permutation $\pmbx{}_{i,j}$ is obtained from $\pmbx{}$ by transposition of its $i^{\text{th}}$ and $j^{\text{th}}$ coordinates.
Then by the McDiarmid Inequality with respect to permutation (Fact <ref>), we have that for all $\eta > 0$,

\Pr \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 \right] \ge \eta \right] \le \exp \left( - \frac{2 \eta^2 }{ \frac{n}{L} 2 } \left( \frac{n - \frac{1}{2} }{n - \frac{n}{L}} \right) \left( 1 - \frac{1}{2 \max \{ \frac{n}{L} , n - \frac{n}{L} \} } \right) \right)\,.

As $L = 2 (\log d ) / \log n \ge 2$, it holds that $n / L \le n - n / L$. It follows that

\begin{align*}
\left( \frac{n - \frac{1}{2} }{n - \frac{n}{L}} \right) \left( 1 - \frac{1}{2 \max \{ \frac{n}{L} , n - \frac{n}{L} \} } \right)
\ge \left( 1 - \frac{ \frac{1}{2} }{ ( n - \frac{n}{L} ) } \right)
\ge \frac{1}{2}\,.
\end{align*}

Substituting $\eta$ with $\sqrt{ 2 \frac{n}{L} \ln \frac{1}{\beta'}}$, we get

\Pr \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU }{ L } \right\Vert_2 \right] \ge \eta \right]
\le \exp \left( - \frac{2 \eta^2 }{ \frac{n}{L} 2 } \cdot \frac{1}{2} \right)
= \beta'\,.

Proof of Inequality (<ref>).
Let $f_{\U{}_1, \pmbx{} }$ and $f_{\U{}_1, \pmbx{}_{i, j} }$ the frequency vectors when $\mbfX{} = \pmbx{}$ and $\mbfX{} = \pmbx{}_{i, j}$, respectively.
It holds that

\begin{align*}
f_{\U{}_1, \pmbx{}_{i, j} } [ \pmbs{} ]
= \begin{cases}
f_{\U{}_1, \pmbx{} } [ \pmbs{} ], &
\forall \pmbs{} \in  \Lambda^\tau \setminus \{ \pmbs{}^{ (x_i) },  \pmbs{}^{ (x_\ell ) } \}\,, \\
f_{\U{}_1, \pmbx{} } [ \pmbs{} ] - 1, & \pmbs{} =  \pmbs{}^{ (x_{i} ) }\,,   \\
f_{\U{}_1, \pmbx{} } [ \pmbs{} ] + 1, &
\pmbs{} = \pmbs{}^{ (x_\ell ) }\,.
\end{cases}
\end{align*}

If we view $f_{\U_j, \pmbx{} } - \frac{ f_\mcalU}{ L }$ and $f_{\U_j, \pmbx{}_{i, j} } - \frac{ f_\mcalU }{ L }$ as $|\Lambda^\tau|$-dimensional vectors, it holds that

\left( f_{\U_j, \pmbx{} } - \frac{ f_\mcalU }{ L } \right) - \left( f_{\U_j, \pmbx{}_{i, j} } - \frac{ f_\mcalU }{ L } \right) = - \pmbe{}_{ \pmbs{}^{ (x_{i} ) } } + \pmbe{}_{ \pmbs{}^{ (x_\ell ) } }\,,

where $\pmbe{}_{ \pmbs{}^{ (x_{i} ) } }$ and $\pmbe{}_{ \pmbs{}^{ (x_\ell ) } }$ are the $\pmbs{}^{ (x_{i} ) }$-th and the $\pmbs{}^{ (x_\ell ) }$-th standard basis vectors in $\R^{ |\Lambda^\tau | }$ respectively. By the triangle inequality,

\left\Vert  f_{\U_j, \pmbx{} } - \frac{ f_\mcalU }{ k } \right\Vert_2 - \left\Vert f_{\U_j, \pmbx{}_{i, j} } - \frac{ f_\mcalU }{ k } \right\Vert_2 \le \Vert - \pmbe{}_{ \pmbs{}^{ (x_{i} ) } } + \pmbe{}_{ \pmbs{}^{ (x_\ell ) } } \Vert_2 = \sqrt{2}\,.

Bounding $\left\Vert f_{\U_\tau } - \frac{ f }{ L }  \right\Vert_2$. We prove that for each $\tau \in [L]$, with probability at least $1 - \beta'$, it holds that

\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \in O \left( \sqrt{ \frac{n}{L} \ln \frac{1}{\beta'} } \right)\,.

Consider a fixed $\tau \in [L]$.
For each user $u \in \mcalU{}$, define $\pmbs{}^{ (u) } \doteq v^{ (u) } [ 1 : \tau ]$, the prefix of $v^{ (u) }$ with length $\tau$.
For each $u \in \mcalU{}$, define the indicator random variable $X_u$ for the corresponding event $u \in \U_\tau$.
Let $\mbfX{}$ be shorthand for $\{ X_1, \ldots, X_n \}$.
As $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2$ is a function that depends on $\mbfX{}$, we write it explicitly as $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2(X_1, \ldots, X_n)$ or $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2(\mbfX{})$ when necessary.
For a sequence of values $\pmbx{} = \{ x_1, \ldots, x_n \} \in \{0, 1\}^n$, we use $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2(x_1, \ldots, x_n)$ or $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2(\pmbx{})$ to denote the value of $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 ( \mbfX{} )$, when $\mbfX{} = \pmbx{}$. Since

\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2
= \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2
- \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right]
+ \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right]\,,

we can bound $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right]$ and $\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right]$ separately.

Bounding $\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right]$.
First, similar to the proof for Lemma <ref>, we have that

\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2^2 \right]
= \sum_{ \pmbs{} \in \Lambda^\tau } \E \left[ \left( f_{\U_\tau } [ \pmbs{} ] - \frac{ 1 }{ L } f_\mcalU{} [ \pmbs{} ]  \right)^2 \right]
= \sum_{ \pmbs{} \in \Lambda^\tau } \Var \left[  f_{\U_\tau } [ \pmbs{} ] \right] \le \sum_{ \pmbs{} \in \Lambda^\tau } \frac{1}{L} f_\mcalU{} [ \pmbs{} ] = \frac{n}{L}\,.

Hence, by Jensen's inequality, $\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right] \le \sqrt{ \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2^2 \right]  } \in O \left( \sqrt{ \frac{n}{L} } \right)$ .

Bounding $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right]$.
Bounding this is more nuanced than the equivalent term in the proof of Lemma <ref>.
We could show that $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2$ satisfies the Lipschitz condition with bound $1$ and then apply McDiarmid’s Inequality (Fact <ref>).
But this will give us an inferior bound of $O \left( \sqrt{ n \ln \frac{1}{\beta'}} \right)$.
The Lipschitz condition states that for each $u \in \mcalU{}$, if the value of $X_u$ changes, it affects $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2$ by at most $1$.
This completely ignores the variance of $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2$.

We apply a martingale concentration inequality that incorporates variances (Fact <ref>).
First, we introduce a dummy variable $X_0 \equiv 0$. For each $0 \le i \le n$, let $\mbfS{}_i$ be shorthand for $(X_0, \ldots, X_i)$. Define

Y_i \doteq \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_i \right].

Clearly $Y_i$ is a function of $X_0, \ldots, X_i$ and $\E[ |Y_i| ] \le \infty$. Moreover,

\begin{aligned}
\E[ Y_{i + 1} \mid \mbfS{}_i ]
&= \E \left[ \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_i, X_{i + 1} \right] \,\middle\vert\, \mbfS{}_i \right]
&= \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_i \right]
&= Y_i.
\end{aligned}

The sequence $Y_0, \ldots, Y_n$ satisfies all conditions specified in Definition <ref> and is a martingale. By definition, $Y_n = \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_n \right] = \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2$ as, once the values of $X_1, \ldots, X_n$ are determined, so is $\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2$. And we have $Y_0 = \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, X_0 \right] = \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \right]$, as $X_0 \equiv 0$.

Next, we show that for all $i \in [n]$,

* $| Y_i - Y_{i - 1} | \le 1$; and

* $\Var{}[ Y_i \mid X_0, \ldots, X_{i - 1} ] \le \frac{1}{L}$.

Then by Fact <ref>, it holds that for all $\eta > 0$,

\Pr[ Y_n - Y_0 \ge \eta ] \le \exp \left( - \frac{\eta^2}{ 2 \left( n / L + \eta / 3 \right) } \right)\,.

We want to find an $\eta$, s.t., $\exp \left( - \frac{\eta^2}{ 2 \left( n / L + \eta / 3 \right) } \right) = \beta'$.
This leads to an equation

\eta^2 - \frac{2 \cdot \ln \frac{1}{\beta'} }{ 3 } \eta - \frac{2 \cdot n \cdot \ln \frac{1}{\beta'} }{L} = 0\,,

whose solution gives

\eta = \frac{ \ln \frac{1}{\beta'} }{ 3 } + \frac{1}{2} \sqrt{ \frac{ 2^2 \cdot \ln^2 \frac{1}{\beta'} }{ 3^2 } + \frac{8 \cdot n \cdot \ln \frac{1}{\beta'} }{L}} \le \sqrt{ \frac{2 \cdot n \cdot \ln \frac{1}{\beta'} }{L} } + \frac{ 2 \cdot \ln \frac{1}{\beta'} }{ 3 }\,.

We conclude that, with probability at least $1 - \beta'$, it holds that

\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L }  \right\Vert_2 \right] \le \sqrt{ 2 \cdot \frac{n}{L} \cdot \ln \frac{1}{\beta'}  } + \frac{ 2 \cdot \ln \frac{1}{\beta'} }{ 3 } \le \left( \sqrt{2} + \frac{2}{3} \right) \cdot \sqrt{ \frac{n}{L} \cdot \ln \frac{1}{\beta'}  }\,.

Proving that for all $i \in [n], | Y_i - Y_{i - 1} | \le 1$.  For all sequences $\pmbx{}_{i - 1} = (0, x_1, \ldots, x_{i - 1} ) \in \{0, 1\}^i$ and for all $x_i \in \{0, 1\}$, we prove that

\begin{equation*}
\left| \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_{i - 1} = \pmbx{}_{i - 1} , X_i = x_i \right] - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_{i - 1} = \pmbx{}_{i - 1} \right] \right| \le 1\,.
\end{equation*}

But since

\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_{i - 1} = \pmbx{}_{i - 1} \right] = \underset{ x \in \{0, 1\} }{\E } \left[ \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_{i - 1} = \pmbx{}_{i - 1} , X_i = x \right] \right],

\begin{equation*}
\gamma \doteq \left| \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_{i - 1} = \pmbx{}_{i - 1} , X_i = 0 \right] - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfS{}_{i - 1} = \pmbx{}_{i - 1} , X_i = 1  \right] \right|\,.
\end{equation*}

It suffices to prove that $\gamma \le 1$.
Let $\pmbx{}_i^+ = (x_{i + 1}, \ldots, x_n )$ denote a possible sequence in $\{0, 1 \}^{ n - i}$.
For $x_i \in \{0, 1 \}$, we write

\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 ( \pmbx{}_{i - 1} , x_i, \pmbx{}_i^+ )

\left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 ( x_0, \ldots, x_{i - 1} , 0, x_{i + 1}, \ldots, x_n ).

Let $\mbfS{}_i^+$ be shorthand for $\{ X_{i + 1}, \ldots, X_n\}$.
Since $\mbfS{}_i^+$ is independent of $\mbfS{}_i$, we have

\begin{align*}
\gamma
&= \left| \sum_{ \pmbx{}_i^+ \in \{0, 1\}^{n - i} } \Pr[ \mbfS{}_i^+ = \pmbx{}_i^+ ] \cdot \left( \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 ( \pmbx{}_{i - 1} , 0, \pmbx{}_i^+ ) - \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 ( \pmbx{}_{i - 1} , 1, \pmbx{}_i^+ ) \right) \right|.
\end{align*}

Consider a fixed $\pmbx{}_i^+ \in \{0, 1\}^{n - i}$.
Let $\pmbx{} = (\pmbx{}_{i - 1}, 0, \pmbx{}_i^+ )$ and $\pmbx{}' = (\pmbx{}_{i - 1}, 1, \pmbx{}_i^+ )$. Let $f_{\U_\tau, \pmbx{} }$ and $f_{\U_\tau, \pmbx{}' }$ be the frequency vectors when $\mbfX{} = \pmbx{}$ and $\mbfX{} = \pmbx{}'$, respectively.
Recall that $\pmbs{}^{ (i) } = v^{ (i) } [ 1 : \tau]$ is the prefix with length $\tau$ of the $i^{\text{th}}$ user.
For $\pmbs{} \in \Lambda^\tau \setminus \{ \pmbs{}^{ (i) } \}$, it holds that $f_{\U_\tau, \pmbx{} } [ \pmbs{} ] = f_{\U_\tau, \pmbx{}' } [ \pmbs{} ]$. Further, $f_{\U_\tau, \pmbx{} } [ \pmbs{}^{ (i) } ] + 1 = f_{\U_\tau, \pmbx{} '} [ \pmbs{}^{ (i) } ]$.

If we view $f_{\U_\tau, \pmbx{} } - \frac{ f_\mcalU{} }{ k }$ and $f_{\U_\tau, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k }$ as $|\Lambda^\tau|$-dimensional vectors, it holds that

\left( f_{\U_\tau, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right) - \left( f_{\U_\tau, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k } \right) = - \pmbe{}_{ \pmbs{}^{ (i) } }\,,

where $\pmbe{}_{ \pmbs{}^{ (i) } }$ is the $\pmbs{}^{ (i) }$-th standard basis vector. By the triangle inequality,

\left\Vert  f_{\U_\tau, \pmbx{} } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 - \left\Vert f_{\U_\tau, \pmbx{} ' } - \frac{ f_\mcalU{} }{ k } \right\Vert_2 \le \Vert \pmbe{}_{ \pmbs{}^{ (i) } } \Vert_2 = 1\,.

Proving $\forall i \in [n], \Var{}[ Y_i \mid X_0, \ldots, X_{i - 1} ] \le \frac{1}{L}$. For each sequence $\pmbx{}_{i - 1}$,

\begin{align*}
\E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfX{}_{i - 1} = \pmbx{}_{i - 1} \right]
&= \frac{1}{L} \cdot \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfX{}_{i - 1} = \pmbx{}_{i - 1} , X_i = 1 \right] \\
&+ \left( 1 - \frac{1}{L} \right) \cdot \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfX{}_{i - 1} = \pmbx{}_{i - 1} , X_i = 0 \right]\,.
\end{align*}

We have also proven that

\left| \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfX{}_{i - 1} = \pmbx{}_{i - 1} , X_i = 0 \right] - \E \left[ \left\Vert f_{\U_\tau } - \frac{ f_\mcalU{} }{ L } \right\Vert_2 \,\middle\vert\, \mbfX{}_{i - 1} = \pmbx{}_{i - 1} , X_i = 1  \right] \right| \le 1.

It follows that $\Var{} \left[ Y_i \mid \mbfX{}_{i - 1} = \pmbx{}_{i - 1} \right] \le 1 / L \cdot (1 - 1 / L) \le 1 / L$.

§.§.§ Proof for Theorem <ref>