# Block Design-Based Local Differential Privacy Mechanisms

Hyun-Young Park, Seung-Hyun Nam, and Si-Hyeon Lee H.-Y. Park, S.-H. Nam, and
S.-H. Lee are with the School of Electrical Engineering, Korea Advanced
Institute of Science and Technology (KAIST), Daejeon 34141, South Korea
(e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>sihyeon@kaist.ac.kr).
(Corresponding Author: Si-Hyeon Lee)A short version of this manuscript will be
presented at 2023 IEEE International Symposium on Information Theory [1].

###### Abstract

In this paper, we propose a new class of local differential privacy (LDP)
schemes based on combinatorial block designs for a discrete distribution
estimation. This class not only recovers many known LDP schemes in a unified
framework of combinatorial block design, but also suggests a novel way of
finding new schemes achieving the optimal (or near-optimal) privacy-utility
trade-off with lower communication costs. Indeed, we find many new LDP schemes
that achieve both the optimal privacy-utility trade-off and the minimum
communication cost among all the unbiased schemes for a certain set of input
data size and LDP constraint. Furthermore, to partially solve the sparse
existence issue of block design schemes, we consider a broader class of LDP
schemes based on regular and pairwise-balanced designs, called RPBD schemes,
which relax one of the symmetry requirements on block designs. By considering
this broader class of RPBD schemes, we can find LDP schemes achieving near-
optimal privacy-utility trade-off with reasonably low communication costs for
a much larger set of input data size and LDP constraint.

###### Index Terms:

Block design, local differential privacy, statistical inference, communication
efficiency, discrete distribution estimation.

##  I Introduction

Statistical inference often involves the collection of private data about
individuals, e.g., health conditions, preference on merchandises, search
histories, etc. It has been continuously reported that a single data in a
large dataset can be inferred from the anonymized dataset, statistics about
the dataset, and even machine learning models trained with the dataset [2, 3,
4, 5, 6, 7, 8], which necessitates the application of appropriate privacy
protection techniques. An effective and powerful privacy protection technique
is to perturb each data to satisfy a certain privacy constraint before sent to
the data collector. Among many privacy constraints [9, 10, 11, 12], local
differential privacy (LDP) is widely adopted and applied both in academia and
industry due to its powerful privacy guarantee, operational meaning, and
useful properties such as composability and robustness to post-processing [10,
13]. An LDP mechanism is applied at each client side, requiring that each
possible true data (input of the mechanism) should induce a similar
distribution on the data sent to the collector (output of the mechanism). The
LDP constraint was shown to upper-bound the probability of correctly inferring
any information from the protected data [10]. As such, LDP guarantees a
fundamental privacy protection against the data collector and any other
attackers. Furthermore, LDP is well-suited for statistical inference systems
because it does not require the underlying distribution of data, while some
other privacy constraints based on mutual information and $\alpha$-leakage [9]
require the prior distribution.

Many LDP mechanisms and corresponding estimators have been proposed for
various statistical inference tasks, such as discrete distribution
estimation[14, 15, 16, 17, 18, 19, 20], mean estimation[11, 21, 22, 23, 19],
etc. Let us call a pair of an LDP mechanism at the clients and the estimator
at the data collector as an (LDP) scheme. Note that a stronger privacy
constraint requires more perturbation of the data, which in turn causes more
performance degradation in statistical inference, i.e., more loss of utility.
Such a fundamental trade-off between privacy and utility has been actively
studied [24, 25, 16, 26, 23, 27]. In particular, the subset selection (SS)
scheme proposed in [16] was shown to achieve the optimal privacy-utility
trade-off, i.e., the minimax risk, in sample asymptotics for the discrete
distribution estimation [26]. For the mean estimation on spherical data,
PrivUnit2 introduced in [23] was proved to be optimal in a non-asymptotic
sense among all the unbiased schemes [27].

In addition to privacy and utility, another factor of practical importance is
the communication cost for sending data from each client to the data collector
[28, 29, 30]. The optimal LDP schemes with respect to privacy-utility trade-
off, however, are known to require very large communication costs, i.e., the
SS [16] requires the communication cost of order greater than the exponential
of the input data size and PrivUnit2 [23] produces continuous outputs.
Recently, many communication-efficient LDP schemes have been proposed for
private statistical inference [18, 19, 20, 31, 32], especially, [19]
characterized the optimal privacy-utility-communication trade-off in the
order-optimal sense. In practice, however, characterizing the exact trade-off,
instead of order analysis, is important as the effect of constants becomes
non-negligible in finite regime. There have been few works [20] proposing
communication-efficient schemes whose exact privacy-utility trade-off is close
to the optimal, but only for a partial form of input data size and LDP
constraint. Finding communication-efficient schemes with (near-) optimal
privacy-utility trade-off for more general input data size and LDP constraint
has been quite open.

In this paper, we propose a new class of LDP schemes based on combinatorial
block designs [33] for discrete distribution estimation, which we call block
design schemes. This class not only recovers many known LDP schemes in a
unified framework of combinatorial block design, including randomized response
(RR)[14], SS[16], Hadamard response (HR)[18], projective geometry response
(PGR) [20], to name a few, but also suggests a novel way of finding new
schemes achieving the optimal (or near-optimal) privacy-utility trade-off,
i.e., the minimax risk, with lower communication costs. The proposed block
design scheme has six parameters, i.e., sizes of the input and the output of
the mechanism, LDP constraint, and three parameters related to some symmetry
properties. Since the input data size (the input of the mechanism) and the LDP
constraint are predetermined, we have four design parameters to choose. We
show that the risk is determined by only a single parameter among the four,
i.e., one of the symmetry-related parameters, called uniformity parameter.
This fact opens up possibilities of finding schemes achieving optimal (or
near-optimal) privacy-utility trade-off with lower communication costs by
considering block designs with the same (or similar) uniformity parameter with
the optimal SS [16]. Indeed, we find many new LDP schemes in this class that
achieve both the minimax risk and the minimum communication cost for a larger
set of input data size and LDP constraint than [20].

In general, however, due to the necessary conditions that the parameters of a
block design should satisfy, block designs exist for a sparse set of
parameters. Thus, a block design scheme achieving a risk close to the minimax
risk with reasonably low communication cost may not exist for some input data
size and LDP constraint. To overcome this issue of sparse existence of block
designs, we consider regular and pairwise-balanced design (RPBD) schemes,
which relaxes one of the symmetry requirements on block designs. By doing so,
we indeed find new privacy schemes achieving near-optimal privacy-utility
trade-off with reasonably low communication costs for a much larger set of
input data size and LDP constraint. For example, we find schemes which achieve
smaller estimation error while requiring less communication cost compared to
previously known schemes (PGR) in some medium privacy regime by exploring RPBD
schemes.

The rest of this paper is organized as follows. In Section II, we formulate
the problem of private discrete distribution estimation. In Section III, we
first introduce some basics of block design, and then present block design
schemes and RPBD schemes with sufficient conditions for two schemes to achieve
the same risk, which play the key role in finding (near-) optimal risks with
low communication costs. In Section IV, we show the set of input data size and
LDP constraint where both the minimax risks and the minimum communication
costs are achieved by using some block designs, and also show that near-
optimal risks and reasonably low communication costs can be achieved for a
larger set of input data size and LDP constraint by considering RPBD scheme.
Finally, with some discussions in Section V, Section VI concludes the paper.

##  II Problem Formulation

We consider a discrete distribution estimation problem where a server wants to
estimate the underlying data distribution of $n$ clients while preserving each
individual’s privacy. Client $i$ for $i\in[1:n]$ observes $X_{i}$, which is
i.i.d. according to unknown distribution $P\in\Delta_{v}$ on
$\mathcal{X}=[1:v]$, where $v\geq 2$ is finite and

$\displaystyle\Delta_{v}:=\left\\{P=(P_{1},\cdots,P_{v})\in\mathbb{R}^{v}:P_{x}\geq
0,\sum_{x=1}^{v}P_{x}=1\right\\}$ (1)

is the set of all probability mass functions on $\\{1,2,\cdots,v\\}$.

Then, it independently generates a privacy-protected data
$Y_{i}\in\mathcal{Y}$ according to a conditional distribution $Q(\cdot|X_{i})$
and sends $Y_{i}$ to the server, where the set $\mathcal{Y}$ and the
conditional distribution $Q:\mathcal{X}\rightarrow\mathcal{Y}$ are known to
the server. The privacy requirement is formalized by the local differential
privacy (LDP)[24].

###### Definition 1

Let $\epsilon>0$ be given. A conditional distribution
$Q:\mathcal{X}\rightarrow\mathcal{Y}$ is said to satisfy the $\epsilon$-local
differential privacy (in short, $\epsilon$-LDP) if

$\displaystyle Q(A|x)\leq e^{\epsilon}Q(A|x^{\prime}),$ (2)

for all $x,x^{\prime}\in\mathcal{X}$ and a (measurable) set
$A\subset\mathcal{Y}$.

The server collects $Y_{1},Y_{2},\cdots,Y_{n}$ from the clients, and uses them
to construct an estimate $\hat{P}_{n}(Y_{1},\cdots,Y_{n})$ of $P$, where
$\hat{P}_{n}$ is the estimator given as a function
$\hat{P}_{n}=(\hat{P}_{n,1},\cdots,\hat{P}_{n,v}):\mathcal{Y}^{n}\rightarrow\mathbb{R}^{v}$.
We call a conditional distribution $Q$ and a conditional distribution-
estimator pair $(Q,\hat{P}_{n})$ as an (LDP) mechanism and an (LDP) scheme,
respectively. Especially, we say $(Q,\hat{P}_{n})$ is an unbiased scheme if
$\mathbb{E}_{P,Q}[\hat{P}_{n}]=P$ for all $P\in\Delta_{v}$.

Let $\ell:\Delta_{v}\times\mathbb{R}^{v}\rightarrow\mathbb{R}$ be a
(measurable) function called a loss function, which measures the difference
between two arguments. The risk of a scheme $(Q,\hat{P}_{n})$ under a loss
function $\ell$ is defined as

$\displaystyle
R_{v,n}(\ell,P,Q,\hat{P}_{n}):=\mathbb{E}\left[\ell(P,\hat{P}_{n}(Y_{1},\cdots,Y_{n}))\right],$
(3)

where the expectation is over $X_{i}\sim P$ and $Y_{i}\sim Q(\cdot|X_{i})$.
Since $P$ is unknown, we consider the worst case risk, which is defined as

$\displaystyle
R_{v,n}^{*}(\ell,Q,\hat{P}_{n}):=\sup_{P\in\Delta_{v}}R_{v,n}(\ell,P,Q,\hat{P}_{n}).$
(4)

In this paper, we mainly focus on the $\ell_{u}^{u}$-loss for $1\leq u\leq 2$,

$\displaystyle\ell_{u}^{u}(p,\hat{p}):=\sum_{x=1}^{v}|p_{x}-\hat{p}_{x}|^{u},$
(5)

for $p\in\Delta_{v}$ and $\hat{p}\in\mathbb{R}^{v}$.

We consider the fundamental trade-off between privacy and utility in the
following two points of view:

  1. 1.

Asymptotic minimax risk
In this setting, we consider the rate of risk when $n\rightarrow\infty$. The
asymptotic minimax risk under $\epsilon$-LDP constraint for $\ell_{u}^{u}$
loss, $1\leq u\leq 2$ is defined as

$\displaystyle
M_{\infty}(v,u,\epsilon):=\inf_{Q:\epsilon\text{-LDP}}\lim_{n\rightarrow\infty}\inf_{\hat{P}_{n}}n^{u/2}R_{v,n}^{*}(\ell_{u}^{u},Q,\hat{P}_{n}).$
(6)

We note that the rate term $n^{u/2}$ in (6) is because
$\inf_{\hat{P}_{n}}R_{v,n}^{*}(\ell_{u}^{u},Q,\hat{P}_{n})=\Theta(n^{-u/2})$
for any LDP mechanism $Q$ [26].

  2. 2.

(Non-asymptotic) minimax risk under the unbiased constraint
In this setting, we fix $n$, but consider an additional constraint that the
scheme must be unbiased. In this case, we focus on the mean squared loss,
i.e., $\ell_{2}^{2}$. The minimax risk under $\epsilon$-LDP and unbiased
constraints for mean squared loss is defined as

$\displaystyle M(v,n,\epsilon):=\inf_{\begin{subarray}{c}(Q,\hat{P}_{n}):\\\
\epsilon\text{-LDP,
unbiased}\end{subarray}}R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n}).$ (7)

On the other hand, the communication cost of a scheme is measured by the
number of possible outputs $|\mathcal{Y}|$ of the mechanism, which we denote
by $b$. This is the exponential of the number of required bits for uncoded
transmission, which makes sense because the best possible guess for the
distribution of $Y_{i}$ would be the uniform distribution as $P$ is unknown.
We note that it suffices to consider $b<\infty$, since any $\epsilon$-LDP
scheme can be approximated with arbitrary precision (in some sense) by another
$\epsilon$-LDP scheme with finite $b$[16, Lemmas 11 and 19].

We note that the asymptotic minimax risk (6) for ${1\leq u\leq 2}$ was
characterized in [26], in which a lower bound on $M_{\infty}(v,u,\epsilon)$
was derived and the subset selection scheme with appropriately chosen
parameters was shown to achieve it, i.e., for any $(v,\epsilon)$, there is a
subset selection scheme $(Q,\hat{P}_{n})$ such that

$\displaystyle\lim_{n\rightarrow\infty}n^{u/2}R_{v,n}^{*}(\ell_{u}^{u},Q,\hat{P}_{n})=M_{\infty}(v,u,\epsilon),\;\forall
1\leq u\leq 2.$ (8)

However, the subset selection scheme satisfying (8) requires a large
communication cost, larger than the exponential growth in input data size. In
this paper, we are interested in the development of schemes achieving (near-)
optimal risks with lower communication costs.

##  III Main Results

###  III-A Preliminary: Incidence structure and block design

In this subsection, we introduce the basic definitions about the block design
and its properties. The details can be found in [33, 34].

###### Definition 2

An incidence structure is a triplet $(\mathcal{X},\mathcal{Y},\mathcal{I})$,
where

  * •

$\mathcal{X}$, $\mathcal{Y}$ are sets.

  * •

$\mathcal{I}\subset\mathcal{X}\times\mathcal{Y}$ is a subset of pairs $(x,y)$,
$x\in\mathcal{X}$, $y\in\mathcal{Y}$.

If there is no confusion on $\mathcal{X}$ and $\mathcal{Y}$, we simply say
$\mathcal{I}$ is an incidence structure. Furthermore, we define

$\displaystyle\mathcal{I}_{x}$ $\displaystyle:=$
$\displaystyle\\{y\in\mathcal{Y}:(x,y)\in\mathcal{I}\\},$ (9)
$\displaystyle\mathcal{I}^{y}$ $\displaystyle:=$
$\displaystyle\\{x\in\mathcal{X}:(x,y)\in\mathcal{I}\\}.$ (10)

###### Definition 3

Let $(\mathcal{X},\mathcal{Y},\mathcal{I})$ be an incidence structure with
$|\mathcal{X}|,|\mathcal{Y}|<\infty$. We say this incidence structure is

  * •

$r$-regular, if $|\mathcal{I}_{x}|=r$ for all $x\in\mathcal{X}$.

  * •

$k$-uniform, if $|\mathcal{I}^{y}|=k$ for all $y\in\mathcal{Y}$.

  * •

$\lambda$-pairwise balanced, if
$|\mathcal{I}_{x}\cap\mathcal{I}_{x^{\prime}}|=\lambda$ for all
$x,x^{\prime}\in\mathcal{X}$, $x\neq x^{\prime}$.

###### Definition 4

Let $v,b,r,k$, and $\lambda$ be integers such that ${v>k>0}$, $b>r>\lambda\geq
0$. A block design with parameters $(v,b,r,k,\lambda)$, or shortly
$(v,b,r,k,\lambda)$-block design, is an incidence structure such that

  * •

$\mathcal{X},\mathcal{Y}$ are finite sets with $|\mathcal{X}|=v$,
$|\mathcal{Y}|=b$.

  * •

$(\mathcal{X},\mathcal{Y},\mathcal{I})$ is $r$-regular, $k$-uniform, and
$\lambda$-pairwise balanced.

######  Lemma III.1 (Proposition 2.3.7 of [33])

For any block design, the parameters $(v,b,r,k,\lambda)$ should satisfy the
following two equalities:

  * •

$vr=bk$.

  * •

$\lambda(v-1)=r(k-1)$.

###  III-B Block design schemes: Locally differentially private schemes based
on block designs

We propose a general class of schemes based on block designs, which not only
contains randomized response (RR) [14], subset selection (SS) [16], Hadamard
response (HR) [18], and projective geometry response (PGR) [20], but also
contains novel schemes achieving (near-) optimal risks while requiring lower
communication costs. Our scheme is motivated by the observation that the
aforementioned previously known mechanisms can be stated in the following
way111Hadamard response in [18] considers some truncated submatrix of Hadamard
matrix when there is no Hadamard matrix matching to the input data size. For
simplicity, we only refer to HR without such truncation, and we introduce the
concept of truncation in Section III-D. Also, the Hadamard matrix used for the
original version of HR does not satisfy uniformity. But, its slight
modification by removing the first column and the first row satisfies
uniformity and achieves lower worst-case $\ell_{2}^{2}$ risk. In this paper,
we refer to the HR with this modification.:

  1. 1.

An incidence structure $(\mathcal{X},\mathcal{Y},\mathcal{I})$, which is
$r$-regular, $k$-uniform, and $\lambda$-pairwise balanced for some $r$, $k$,
and $\lambda$, is determined in a certain way, which is different for each
mechanism.

  2. 2.

For given $X=x$, the mechanism draws an independent Bernoulli random variable
$B$. The mechanism outputs an element in $\mathcal{I}_{x}$ uniform randomly if
$B=1$, and else, outputs an element in $\mathcal{Y}\setminus\mathcal{I}_{x}$
uniform randomly.

###### Remark 1

The works [18], [20] mentioned that their mechanisms satisfy the regular and
the pairwise balanced properties. We note that, however, they described these
properties not in the context of incidence structure or block design, and did
not capture the uniformity.

Now, let us introduce our proposed class of schemes. We first present the
proposed mechanisms.

###### Definition 5

For given $\mathcal{X}=\\{1,2,\cdots,v\\}$ and $\epsilon>0$, a privacy
mechanism $Q$ is called a block design mechanism with parameters
$(v,b,r,k,\lambda,\epsilon)$ if there exists a $(v,b,r,k,\lambda)$-block
design $(\mathcal{X},\mathcal{Y},\mathcal{I})$ such that

$Q(y|x)=\begin{cases}\alpha e^{\epsilon}&((x,y)\in\mathcal{I})\\\
\alpha&((x,y)\notin\mathcal{I})\end{cases},$ (11)

where $\alpha=\frac{1}{re^{\epsilon}+b-r}$ is a normalization constant.

TABLE I: List of some block designs[33, 35] |  |  |  |  |  |  | Corresponding
---|---|---|---|---|---|---|---
Structure | Parameters | $v$ | $b$ | $r$ | $k$ | $\lambda$ | previous
|  |  |  |  |  |  | mechanism
Trivial symmetric block design |  $v$ : An integer $v\geq 2$ | $v$ | $v$ | $1$ | $1$ | $0$ | RR[14]
Complete block design |  $v$ : An integer $v\geq 2$ $k$ : An integer $1\leq k\leq v-1$ | $v$ | $\binom{v}{k}$ | $\binom{v-1}{k-1}$ | $k$ | $\binom{v-2}{k-2}$ | SS[16]
Projective geometry |  $q$ : prime power $t$ : An integer $t\geq 2$ | $\frac{q^{t}-1}{q-1}$ | $\frac{q^{t}-1}{q-1}$ | $\frac{q^{t-1}-1}{q-1}$ | $\frac{q^{t-1}-1}{q-1}$ | $\frac{q^{t-2}-1}{q-1}$ | PGR[20]
Sylvester’s Hadamard matrix |  $t$ : An integer $t\geq 2$ | $2^{t}-1$ | $v$ | $(v-1)/2$ | $(v-1)/2$ | $(v-3)/4$ | HR[18]
Paley’s Hadamard matrix |  $v$ : A prime power s. t. $v\equiv 3\mod 4$ | $v$ | -
Twin prime power difference set |  $q$ : An odd prime power s.t. $q+2$ is also prime power | $q(q+2)$ | -
Nonzero Quartic residue difference set |  $v$ : A prime power s.t. $v=4t^{2}+1$ for some odd integer $t$ | $v$ | $v$ | $(v-1)/4$ | $(v-1)/4$ | $(v-5)/16$ | -
(Including zero) Quartic residue difference set |  $v$ : A prime power s.t. $v=4t^{2}+9$ for some odd integer $t$ | $v$ | $v$ | $(v+3)/4$ | $(v+3)/4$ | $(v+3)/16$ | -

Some represented block designs based on special mathematical structures[33,
35] are listed in Table I. The detailed descriptions are in Appendix B. We
note that many previously proposed mechanisms are special cases of block
design mechanisms as indicated in Table I.

For matching estimators, we construct a canonical unbiased estimator for each
block design mechanism in a similar way as in [16, 18, 20], which is a simple
linear function of the counts of the events $Y_{i}\in\mathcal{I}_{x}$. For
simplicity, we call a pair of a block design mechanism and the corresponding
canonical estimator as a block design scheme. The risk and the worst case risk
under mean squared loss of a block design scheme are given as follows. The
proof is in Appendix A.

###### Theorem III.2

Given $n$ and a $(v,b,r,k,\lambda,\epsilon)$-block design mechanism $Q$, there
is an unbiased estimator given as

$\displaystyle\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})=\frac{1}{(r-\lambda)(e^{\epsilon}-1)}\left(\frac{N_{x}(Y_{1},\cdots,Y_{n})}{n\alpha}-(\lambda
e^{\epsilon}+(r-\lambda))\right),$ (12)

where

$\displaystyle
N_{x}(Y_{1},\cdots,Y_{n})=\sum_{i=1}^{n}\mathbbm{1}(Y_{i}\in\mathcal{I}_{x}).$
(13)

Moreover, the risk under $\ell_{2}^{2}$ loss of a block design scheme is given
by

$\displaystyle
R_{v,n}(\ell_{2}^{2},P,Q,\hat{P}_{n})=\frac{1}{n}\left(\frac{(v-1)^{2}(ke^{\epsilon}+v-k)^{2}}{k(v-k)(e^{\epsilon}-1)^{2}v}+\frac{1}{v}-\sum_{x\in\mathcal{X}}P_{x}^{2}\right),$
(14)

and the worst-case risk is given by

$\displaystyle
R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})=\frac{(v-1)^{2}(ke^{\epsilon}+v-k)^{2}}{k(v-k)(e^{\epsilon}-1)^{2}nv},$
(15)

which is attained when $P$ is a uniform distribution.

Note that for any given $n$, the risk under $\ell_{2}^{2}$ loss of a block
design scheme only depends on $(v,k,\epsilon)$. In other words, for given
input data size $v$ and LDP constraint $\epsilon$, the risk of a block design
scheme with parameter $(v,b,r,k,\lambda,\epsilon)$ only depends on $k$ under
$\ell_{2}^{2}$ loss. We show that this is true for a broad class of loss
functions including the $\ell_{u}^{u}$ loss, $u\geq 1$, by defining a kind of
equivalence between two schemes as follows.

###### Definition 6

Given $v$ and $n$, two schemes $(Q,\hat{P}_{n})$ and
$(Q^{\prime},\hat{P}_{n}^{\prime})$ are said to be marginally equivalent if
the marginal distributions of the two estimators given the distribution on
$\mathcal{X}$ are the same. Precisely, let $X_{1},\cdots,X_{n}\sim
P\in\Delta_{v}$, and $Y_{i}$ and $Y_{i}^{\prime}$ be the outputs of the
mechanisms $Q$ and $Q^{\prime}$ for an input data $X_{i}$, respectively. We
say the two schemes are marginally equivalent if

$\displaystyle\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})\overset{d}{=}\hat{P}_{n,x}^{\prime}(Y_{1}^{\prime},\cdots,Y_{n}^{\prime}),$
(16)

for all $x\in\mathcal{X}$ and $P\in\Delta_{v}$.

Next, for given $(v,n,\epsilon)$, we show that the marginal equivalence of two
block design schemes is determined solely by $k$ in the following theorem,
whose proof is in Appendix A.

###### Theorem III.3

For given $(v,n,\epsilon)$, let $(Q,\hat{P}_{n})$ and
$(Q^{\prime},\hat{P}_{n}^{\prime})$ be block design schemes with parameters
$(v,b,r,k,\lambda,\epsilon)$ and
$(v,b^{\prime},r^{\prime},k^{\prime},\lambda^{\prime},\epsilon)$,
respectively. Then, the two schemes are marginally equivalent if and only if
$k=k^{\prime}$.

Now, we present a class of widely-used loss functions which give the same risk
for marginally equivalent schemes.

###### Definition 7

A loss function $\ell$ is said to be decomposable if there are functions
$\ell_{x}:[0,1]\times\mathbb{R}\rightarrow\mathbb{R}$, $x=1,2,\cdots,v$, such
that

$\displaystyle\ell(p,\hat{p})=\sum_{x=1}^{v}\ell_{x}(p_{x},\hat{p}_{x}).$ (17)

for all $p\in\Delta_{v}$, $\hat{p}\in\mathbb{R}^{v}$.

For example, for each $u\geq 1$, $\ell_{u}^{u}$ loss is decomposable with
$\ell_{x}(p_{x},\hat{p}_{x})=|p_{x}-\hat{p}_{x}|^{u}$. Another examples are
$f$-divergences $D_{f}:\Delta_{v}\times\Delta_{v}\rightarrow\mathbb{R}$,

$\displaystyle D_{f}(\hat{p}\|p)=\sum_{x=1}^{v}p_{x}f(\hat{p}_{x}/p_{x})$ (18)

for convex functions $f:[0,\infty]\rightarrow\mathbb{R}\cup\\{\infty\\}$ such
that ${f(1)=0}$. It can be easily observed that marginally equivalent schemes
give the same risk for a decomposable loss function.

###### Proposition III.4

If $(Q,\hat{P}_{n})$ and $(Q^{\prime},\hat{P}_{n}^{\prime})$ are marginally
equivalent, then

$R_{v,n}(\ell,P,Q,\hat{P}_{n})=R_{v,n}(\ell,P,Q^{\prime},\hat{P}_{n}^{\prime}),$
(19)

for any $P\in\Delta_{v}$ and a decomposable loss function $\ell$.

###### Proof:

We have

$\displaystyle
R_{v,n}(\ell,P,Q,\hat{P}_{n})=\sum_{x=1}^{v}\mathbb{E}\left[\ell_{x}\left(P_{x},\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})\right)\right].$
(20)

Each of
$\mathbb{E}\left[\ell_{x}\left(P_{x},\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})\right)\right]$
only depends on the marginal distribution of each
$\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})$, not on the joint distribution of
$\hat{P}_{n}(Y_{1},\cdots,Y_{n})$. Thus, marginally equivalent schemes give
the same risk. ∎

Now, together with the asymptotic optimality of SS [26], we prove the
asymptotic optimality of a block design scheme.

###### Theorem III.5

Let $K_{opt}(v,\epsilon)$ be the set of positive integers $k\in[1:v-1]$ which
minimizes

$\displaystyle\frac{(ke^{\epsilon}+v-k)^{2}}{k(v-k)}.$ (21)

For given $(v,\epsilon)$ and for each positive integer $n$, let
$(Q,\hat{P}_{n})$ be a block design scheme satisfying $k\in
K_{opt}(v,\epsilon)$, and $Q^{\prime}$ be any $\epsilon$-LDP mechanism. Then,
we have

$\displaystyle\lim_{n\rightarrow\infty}\frac{\inf_{\hat{P}_{n}^{\prime}}R_{v,n}^{*}(\ell_{u}^{u},Q^{\prime},\hat{P}_{n}^{\prime})}{R_{v,n}^{*}(\ell_{u}^{u},Q,\hat{P}_{n})}\geq
1,$ (22)

for all $1\leq u\leq 2$.

###### Proof:

[26, Theorem 3.1] showed that (22) holds when $(Q,\hat{P}_{n})$ is the SS
scheme with $k\in K_{opt}(v,\epsilon)$. Also, Theorem III.3 and Proposition
III.4 say that any block design schemes with the same $k$ induce the same
risk. Hence, (22) also holds when we replace $(Q,\hat{P}_{n})$ by any block
design scheme with the same $k$. ∎

###### Remark 2

It was shown in [16, Proposition 5] that
$K_{opt}(v,\epsilon)\subset{\left\\{\lfloor\frac{v}{e^{\epsilon}+1}\rfloor,\lceil\frac{v}{e^{\epsilon}+1}\rceil\right\\}}$
by simple calculus. We strengthen this result as the following proposition,
whose proof is in Appendix A.

###### Proposition III.6

For given $(v,k,\epsilon)$, $k\in K_{opt}(v,\epsilon)$ holds if and only if

$\displaystyle E(k,k+1;v)\leq e^{\epsilon}\leq E(k-1,k;v),$ (23)

where

$\displaystyle E(k_{1},k_{2};v)=\sqrt{\frac{(v-k_{1})(v-k_{2})}{k_{1}k_{2}}},$
(24)

and $E(0,1;v):=\infty$. Especially, if $e^{\epsilon}=E(k,k+1;v)$ for some $k$,
then $K_{opt}(v,\epsilon)=\\{k,k+1\\}$. Otherwise, $K_{opt}(v,\epsilon)$ is a
singletone.

Moreover, the following theorem says that the above asymptotic optimality
implies the non-asymptotic optimality under the unbiased constraint for the
mean squared loss ($\ell_{2}^{2}$).

###### Theorem III.7

For given $n$, let $(Q,\hat{P}_{n})$ be a block design scheme satisfying $k\in
K_{opt}(v,\epsilon)$, and $(Q^{\prime},\hat{P}_{n}^{\prime})$ be any unbiased
$\epsilon$-LDP scheme. Then, we have

$\displaystyle R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})\leq
R_{v,n}^{*}(\ell_{2}^{2},Q^{\prime},\hat{P}_{n}^{\prime}).$ (25)

###### Proof:

For each positive integer $m$, let $\hat{P}^{\prime}_{nm}$ be the estimator on
$nm$ clients given by

$\displaystyle\hat{P}^{\prime}_{nm}(Y_{1}^{\prime},Y_{2}^{\prime},\cdots,Y_{nm}^{\prime})=\frac{1}{m}\sum_{j=0}^{m-1}\hat{P}_{n}^{\prime}(Y_{nj+1}^{\prime},Y_{nj+2}^{\prime},\cdots,Y_{nj+n}^{\prime}).$
(26)

Because $Y_{1}^{\prime},Y_{2}^{\prime},\cdots,Y_{nm}^{\prime}$ are i.i.d. and
$(Q^{\prime},\hat{P}_{n}^{\prime})$ is unbiased,
$(Q^{\prime},\hat{P}_{nm}^{\prime})$ is also unbiased. Thus, the risk under
the mean squared loss is same as the variance of the estimator. Therefore,

$\displaystyle
R_{v,nm}(\ell_{2}^{2},P,Q^{\prime},\hat{P}^{\prime}_{nm})=\frac{1}{m}R_{v,n}(\ell_{2}^{2},P,Q^{\prime},\hat{P}_{n}^{\prime}),$
(27)

and consequently,

$\displaystyle
R_{v,nm}^{*}(\ell_{2}^{2},Q^{\prime},\hat{P}^{\prime}_{nm})=\frac{1}{m}R_{v,n}^{*}(\ell_{2}^{2},Q^{\prime},\hat{P}_{n}^{\prime}).$
(28)

Also, from (15), it can be easily observed that

$R_{v,nm}^{*}(\ell_{2}^{2},Q,\hat{P}_{nm})=\frac{1}{m}R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n}).$
(29)

Then, we have

$\displaystyle\frac{R_{v,nm}^{*}(\ell_{2}^{2},Q^{\prime},\hat{P}^{\prime}_{nm})}{R_{v,nm}^{*}(\ell_{2}^{2},Q,\hat{P}_{nm})}=\frac{R_{v,n}^{*}(\ell_{2}^{2},Q^{\prime},\hat{P}^{\prime}_{n})}{R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})}.$
(30)

By taking $\liminf_{m\rightarrow\infty}$ to both sides of (30) and applying
Theorem III.5, we get the desired inequality. ∎

Finally, from Theorems III.5 and III.7, we obtain the following corollary.

###### Corollary III.8

Given $v,\epsilon$, a block design scheme $(Q,\hat{P}_{n})$ with $k\in
K_{opt}(v,\epsilon)$ achieves both the asymptotic and non-asymptotic minimax
risks, that is

$\displaystyle\lim_{n\rightarrow\infty}n^{u/2}R_{v,n}^{*}(\ell_{u}^{u},Q,\hat{P}_{n})=M_{\infty}(v,u,\epsilon),\;\forall
1\leq u\leq 2,$ (31)

and

$\displaystyle R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})=M(v,n,\epsilon),~{}$
$\displaystyle\forall n.$ (32)

###  III-C Block design schemes with low communication costs

Corollary III.8 shows that for any given $(v,\epsilon)$, a block design scheme
satisfying $k\in K_{opt}(v,\epsilon)$ achieves the asymptotic and the non-
asymptotic minimax risks for $\ell_{u}^{u}$, $1\leq u\leq 2$, loss and
$\ell_{2}^{2}$ loss, respectively. There might be several different block
design schemes with $k\in K_{opt}(v,\epsilon)$. Among them, a block design
scheme with $b=v$ uses the smallest communication cost: Fisher’s
inequality[33] tells that any block design should satisfy $b\geq v$. Such
block designs with $b=v$ are called symmetric block designs. Furthermore, we
can prove that $b\geq v$ is also required for the unbiasedness of a scheme, in
the same way to the proof of [36, Thm. 6].

###### Theorem III.9

Let $\mathcal{X}=\\{1,2,\cdots,v\\},\mathcal{Y}$ be a finite set, and
${Q:\mathcal{X}\rightarrow\mathcal{Y}}$ be any conditional distribution. If
$(Q,\hat{P}_{n})$ is an unbiased scheme, then $|\mathcal{Y}|\geq v$.

Thus, a symmetric block design scheme with $k\in K_{opt}(v,\epsilon)$ is an
unbiased scheme which achieves the minimax risk while using the minimum
communication cost. We note that the block designs in Table I except the
complete block design are all symmetric block designs. Also, there are many
other symmetric block designs not listed in Table I, e.g., 23 families of
symmetric block designs are listed in [33, Appendix]. In Section IV-A, we plot
the points of $(v,\epsilon)$ for which the minimax risk is achieved with the
minimum communication cost by using the symmetric block designs listed in
Table I.

In general, however, a symmetric block design scheme may or may not exist for
given $(v,k)$. For example, if $v=8$ and $\epsilon=\log 3$, then
$K_{opt}(v,\epsilon)=\\{2\\}$. If we assume the existence of a symmetric block
design with $v=b=8$ and $k=2$, then Lemma III.1 says that
$\lambda=2/7\notin\mathbb{Z}$, which gives a contradiction. Also, there are
some other necessary conditions for the existence of a symmetric block design,
for example the Bruck-Ryser-Chowla theorem[33, Theorem 2.5.10]. If there is no
symmetric block design with $k\in K_{opt}(v,\epsilon)$, then a block design
with $k\in K_{opt}(v,\epsilon)$, $b\gtrsim v$, could be used to achieve the
exactly optimal risk with reasonably low communication cost. Furthermore, if
we also sacrifice the utility, i.e., near-optimal risk instead of optimal, a
block design with $k\approx v/(e^{\epsilon}+1)$, i.e., $v/k\approx
e^{\epsilon}+1$, and $b\gtrsim v$, can be used. In the following, we show an
example of obtaining a non-symmetric block design achieving (near-) optimal
risk with reasonably low $b$.

###### Example 1

One way of obtaining a non-symmetric block design with reasonably low $b$ is
to utilize derived and residual block designs [33]. Let
$(\mathcal{X},\mathcal{Y},\mathcal{I})$ be a $(v,b,r,k,\lambda)$-symmetric
block design with $\lambda>0$, and let $y\in\mathcal{Y}$. Note that from Lemma
III.1 with $b=v$, we must have $r=k$ and $\lambda=k(k-1)/(v-1)$. Then the
following two incidence structures
$(\mathcal{X}^{\prime},\mathcal{Y}^{\prime},\mathcal{I}^{\prime})$,
$(\mathcal{X}^{\prime\prime},\mathcal{Y}^{\prime\prime},\mathcal{I}^{\prime\prime})$
given by

$\displaystyle\mathcal{X}^{\prime}=\mathcal{I}^{y},\quad\mathcal{X}^{\prime\prime}=\mathcal{X}\backslash\mathcal{I}^{y},$
(33)
$\displaystyle\mathcal{Y}^{\prime}=\mathcal{Y}^{\prime\prime}=\mathcal{Y}\backslash\\{y\\},$
(34)
$\displaystyle\mathcal{I}^{\prime}=\mathcal{I}\cap(\mathcal{X}^{\prime}\times\mathcal{Y}^{\prime}),\quad\mathcal{I}^{\prime\prime}=\mathcal{I}\cap(\mathcal{X}^{\prime\prime}\times\mathcal{Y}^{\prime\prime}),$
(35)

are $(k,v-1,k-1,\lambda,\lambda-1)$\- and
$(v-k,v-1,k,k-\lambda,\lambda)$-block designs, respectively, called the
derived block design and the residual block design, respectively. The proof
that they satisfy the properties of block design can be found in [33,
Proposition 2.4.15]. Note that if $v/k\approx e^{\epsilon}+1$, then from Lemma
III.1, the parameters
$(v^{\prime},b^{\prime},r^{\prime},k^{\prime},\lambda^{\prime})$ and
$(v^{\prime\prime},b^{\prime\prime},r^{\prime\prime},k^{\prime\prime},\lambda^{\prime\prime})$
of the derived and residual block designs satisfy

$\displaystyle\frac{v^{\prime}}{k^{\prime}}=\frac{k}{\lambda}=\frac{v-1}{k-1}\approx\frac{v}{k}\approx
e^{\epsilon}+1$ (36)

and

$\displaystyle
v^{\prime\prime}/k^{\prime\prime}=\frac{v-k}{k-\lambda}=\frac{v-k}{k\left(1-\frac{k-1}{v-1}\right)}=\frac{v-1}{k}\approx\frac{v}{k}\approx
e^{\epsilon}+1,$ (37)

respectively, for $v,k\gg 1$. Hence, if a
$(v,b,r,k,\lambda,\epsilon)$-symmetric block design scheme achieves a (near-)
optimal risk, then the derived and residual block design schemes from the
symmetric block design have (near-) optimal risk with $v^{\prime}=k$ and
$v^{\prime\prime}=v-k$, respectively, for the same $\epsilon$.

Up to now, we have considered block-design schemes achieving (near-) optimal
risks with low communication costs. In the next subsection, to overcome the
sparse existence of block designs due to some necessary conditions on the
parameters, we consider a broader class of schemes by relaxing a constraint on
the block design.

###  III-D RPBD schemes: A broader class of schemes based on regular and
pairwise-balanced designs

By carefully analyzing the block design schemes, it can be checked that the
regular and pairwise balanced properties play crucial roles in their
construction, while the uniformity does not. Also, the framework in [18, 20]
used for HR and PGR does not consider uniformity in the construction of
schemes. Motivated from this, we propose a larger class of schemes than block
design schemes by relaxing the uniformity constraint on the block designs.
This class is also a generalization of the aforementioned framework of [18,
20].

###### Definition 8

Let $v,b,r$, and $\lambda$ be integers such that ${v>0}$, $b>r>\lambda\geq 0$.
A regular and pairwise-balanced design (RPBD) with parameters
$(v,b,r,\lambda)$, or in short a $(v,b,r,\lambda)$-RPBD, is an incidence
structure $(\mathcal{X},\mathcal{Y},\mathcal{I})$, where

  * •

$\mathcal{X},\mathcal{Y}$ are non-empty finite sets with $|\mathcal{X}|=v$,
$|\mathcal{Y}|=b$.

  * •

$(\mathcal{X},\mathcal{Y},\mathcal{I})$ is $r$-regular and $\lambda$-pairwise
balanced.

###### Remark 3

A typical example of an RPBD is obtained by truncating a block design. Given a
$(v^{\prime},b,r,k,\lambda)$-block design
$(\mathcal{X}^{\prime},\mathcal{Y},\mathcal{I}^{\prime})$ and a subset
$\mathcal{X}\subset\mathcal{X}^{\prime}$ where $|\mathcal{X}|=v$, an incidence
structure $(\mathcal{X},\mathcal{Y},\mathcal{I})$ given by

$\displaystyle\mathcal{I}=\mathcal{I}^{\prime}\cap(\mathcal{X}\times\mathcal{Y})$
(38)

is a $(v,b,r,\lambda)$-RPBD, but not necessarily is a block design.

Now, we define an RPBD scheme based on RPBD and present its risk.

###### Definition 9

For given $\mathcal{X}=\\{1,2,\cdots,v\\}$ and $\epsilon>0$, a privacy
mechanism $Q$ is called an RPBD mechanism with parameter
$(v,b,r,\lambda,\epsilon)$ if $Q$ is given as (11) for some
$(v,b,r,\lambda)$-RPBD $(\mathcal{X},\mathcal{Y},\mathcal{I})$.

###### Theorem III.10

Given $n$ and a $(v,b,r,\lambda,\epsilon)$-RPBD mechanism $Q$, there is an
unbiased estimator given as (12). A $(v,b,r,\lambda,\epsilon)$-RPBD mechanism
and its corresponding unbiased estimator (12) is called a
$(v,b,r,\lambda,\epsilon)$-RPBD scheme. The risk of a
$(v,b,r,\lambda,\epsilon)$-RPBD scheme under the mean squared loss is given by

$R_{v,n}(\ell_{2}^{2},P,Q,\hat{P}_{n})=\frac{1}{n}\Biggl{[}\frac{re^{\epsilon}+(v-1)(\lambda
e^{\epsilon}+r-\lambda)}{(r-\lambda)^{2}(e^{\epsilon}-1)^{2}v}\times\left[v(b-r)+(v-1)(r-\lambda)(e^{\epsilon}-1)\right]+\frac{1}{v}-\sum_{x\in\mathcal{X}}P_{x}^{2}\Biggr{]},$
(39)

and the worst-case risk is given by

$R^{*}_{v,n}(\ell_{2}^{2},Q,\hat{P}_{n})=\frac{re^{\epsilon}+(v-1)(\lambda
e^{\epsilon}+r-\lambda)}{(r-\lambda)^{2}(e^{\epsilon}-1)^{2}nv}\times\left[v(b-r)+(v-1)(r-\lambda)(e^{\epsilon}-1)\right],$
(40)

which is attained when $P$ is the uniform distribution.

The proof of the above theorem is in Appendix A.

Now, the following theorem gives a condition for the marginal equivalence of
two RPBD schemes, whose proof is in Appendix A.

###### Theorem III.11

For given $(v,n,\epsilon)$, let $(Q,\hat{P}_{n})$ and
$(Q^{\prime},\hat{P}_{n}^{\prime})$ be two RPBD schemes with parameters
$(v,b,r,\lambda,\epsilon)$ and
$(v,b^{\prime},r^{\prime},\lambda^{\prime},\epsilon)$, respectively. Then, the
two schemes are marginally equivalent if and only if there exists a constant
$t>0$ such that $(b^{\prime},r^{\prime},\lambda^{\prime})=t(b,r,\lambda)$. In
other words, the marginal equivalence is determined by the ratio
$[b:r:\lambda]$.

We note that by Lemma III.1 and the formula of $K_{opt}(v,\epsilon)$ in Remark
2, the optimal SS scheme has

$\displaystyle[b:r:\lambda]$
$\displaystyle=\left[\frac{v}{k}\frac{v-1}{k-1}:\frac{v-1}{k-1}:1\right]$ (41)
$\displaystyle\approx[(e^{\epsilon}+1)^{2}:(e^{\epsilon}+1):1],$ (42)

when $v\gg 1$. Hence, we may want to construct an RPBD scheme satisfying (41)
to get an exactly optimal privacy-utility trade-off. However, we show that
such an RPBD scheme must be a block design scheme in the following
proposition, whose proof is in Appendix A.

###### Proposition III.12

Let $(\mathcal{X},\mathcal{Y},\mathcal{I})$ be a $(v,b,r,\lambda)$-RPBD.
Suppose that there exists an integer $k$ such that

$\displaystyle[b:r:\lambda]=\left[\frac{v}{k}\frac{v-1}{k-1}:\frac{v-1}{k-1}:1\right].$
(43)

Then $\mathcal{I}$ is $k$-uniform, hence it is a $(v,b,r,k,\lambda)$-block
design.

This implies that it is not able to find a non-uniform RPBD scheme marginally
equivalent to the optimal SS scheme. Nevertheless, by the continuity of the
worst-case risk (40), we expect that an RPBD scheme with the ratio similar to
(42) has a near-optimal risk. One easy way to find a near-optimal RPBD scheme
with low communication cost is to use an RPBD obtained by truncating a
symmetric block design as explained in Remark 3. In particular, let
$(\mathcal{X}^{\prime},\mathcal{Y},\mathcal{I}^{\prime})$ be a
$(v^{\prime},b,r,k,\lambda)$-block design with $v^{\prime}/k\approx
e^{\epsilon}+1$, and let $(\mathcal{X},\mathcal{Y},\mathcal{I})$ be a
$(v,b,r,\lambda)$-RPBD obtained by truncating the block design. Then we have

$\displaystyle[b:r:\lambda]$
$\displaystyle=\left[\frac{v^{\prime}}{k}\frac{v^{\prime}-1}{k-1}:\frac{v^{\prime}-1}{k-1}:1\right]$
(44) $\displaystyle\approx[(e^{\epsilon}+1)^{2}:(e^{\epsilon}+1):1]$ (45)

when $v\gg 1$. Hence, if a $(v^{\prime},b,r,k,\lambda)$-block design gives a
block design scheme achieving (near-) optimal risk for given $\epsilon$, then
its truncation gives an RPBD scheme achieving near-optimal risk for each
$v<v^{\prime}$ and the same $\epsilon$. We note that the way that HR and
PGR[18, 20] are applied to the input data size not of the form of possible
input data size for Sylvester’s Hadamard matrices or projective geometry-based
block design schemes is equivalent to the use of truncated RPBD schemes.

For example, suppose we want to find a near-optimal RPBD scheme with low
communication cost at $v=2000$ and ${\epsilon=\log 3}$. In this case, a
symmetric block design from projective geometry in Table I with $q=4$ and
$t=7$ satisfies

$[b:r:\lambda]\approx[16:4:1]=[(e^{\epsilon}+1)^{2}:(e^{\epsilon}+1):1],$ (46)

and $b=(4^{7}-1)/(4-1)=5461$. If we use an RPBD scheme obtained by truncating
this symmetric block design (which is PGR[20]), then it achieves near-optimal
risk $R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})=5998.0713\times\frac{1}{n}$,
only $0.08\%$ larger than the minimax risk
$M(v,n,\epsilon)=5993.0025\times\frac{1}{n}$, with communication cost 5461.
Note that the optimal SS for those $v$ and $\epsilon$ uses the communication
cost of $\binom{2000}{500}>5\times 10^{486}$. If we employ other block
designs, then we can even lower the communication cost while attaining near-
optimal risk. For the above example, we may instead use an RPBD scheme
obtained by truncating a symmetric block design from nonzero quartic residue
difference set in Table I with $v^{\prime}=2917$. Then, we obtain slightly
lower risk
$R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})=5996.5160\times\frac{1}{n}$ and
smaller communication cost $b=2917$.

As such, by considering RPBD schemes based on RPBDs obtained by truncating
symmetric block designs, we can achieve (near-) optimal risks with lower
communication costs for a larger set of $(v,\epsilon)$. Indeed, in Section
IV-B, we numerically show that RPBD schemes based on symmetric block designs
listed in Table I achieve (near-) optimal risks by consuming lower
communication costs than some previously known schemes for a broad range of
$v$ for some $\epsilon$.

##  IV Numerical results

###  IV-A Symmetric block design schemes achieving the minimax risks

In Fig. 1, we plot the points of $(v,\epsilon)$ for which both the minimax
risk and the minimum communication cost are achievable by using the symmetric
block designs listed in Table I. For simplicity, we only draw points
$(v,\epsilon=\log((v/k)-1))$ for $v$ and $k$ specified in Table I, for which
$k\in K_{opt}(v,\epsilon)$ trivially holds.222In fact, the minimax risk and
the minimum communication cost is obtained when $\epsilon$ is in a
neighborhood $[\log E(k,k+1;v),\log E(k-1,k;v)]$ of $\log((v/k)-1))$ as stated
in Proposition III.6. In Fig. 1, the red crosses are the points where minimax
risks are achievable by HR [18] or PGR [20], green dash-dot line by RR [14],
and blue dots by newly covered points by using other symmetric block designs
in Table I. We group PGR and HR since HR is equivalent to PGR with $q=2$. As
shown in the figure, many new points of $(v,\epsilon)$ are covered by
considering only the four symmetric block designs not used in the previously
proposed mechanisms in Table I, especially in high privacy ($\epsilon\approx
0$) region.

Figure 1: The points of $(v,\epsilon)$ for which both the minimax risk and the
minimum communication cost are achievable by using the symmetric block designs
listed in Table I.

###  IV-B Numerical comparison of truncated RPBD schemes

In this subsection, we evaluate the risks and the communication costs of the
RPBD schemes truncated from the symmetric block designs in Table I. For the
block designs from Sylvester/Paley’s Hadamard matrix or twin prime power
difference set, we have $k/v\approx 2$. Thus, schemes from these block designs
give near-optimal risks when $\epsilon\approx\log((k/v)-1)\approx 0$. For the
block designs from quartic residue difference sets (both nonzero and including
zero versions), we have $k/v\approx 4$, and hence schemes from these block
designs achieve near-optimal risks when $\epsilon\approx\log 3$. Finally, for
the block designs from projective geometry, we have $k/v\approx q$, yielding
near-optimal risks when $\epsilon\approx\log((k/v)-1)\approx\log(q-1)$. In
particular, for $q=4$, the near-optimality is obtained when
$\epsilon\approx\log 3$. These arguments coincide with the claims in [18, 20],
which state that HR and PGR perform well for $\epsilon\approx 0$ and
$\epsilon\approx\log(q-1)$, respectively.

Motivated from this, we consider two cases of $\epsilon=0.01$ and
$\epsilon=\log 3$, and plot the ratio of the worst-case $\ell_{2}^{2}$ risk of
the proposed and baseline schemes to the minimax risk, i.e.,
$R_{v,n}^{*}(\ell_{2}^{2},Q,\hat{P}_{n})/M(v,n,\epsilon)$, and the required
communication cost $b$, with respect to $v$, in Figs. 2, 3. Note that the
ratio of the worst-case risk to the minimax risk is independent of $n$, and
$M(v,n,\epsilon)$ is the risk of the optimal SS. Also, we can calculate the
risks of the schemes by using Theorems III.2 and III.10. The details for the
schemes used in these figures are given in the following:

  1. 1.

$\epsilon=0.01$: For our proposed scheme, we find a
$(v^{\prime},b,r,k,\lambda)$-symmetric block design from Sylvester’s Hadamard
matrix, Paley’s Hadamard matrix, and twin prime power difference set with
smallest $v^{\prime}\geq v$. Then, we truncate it to obtain a
$(v,b,r,\lambda)$-RPBD, and construct an RPBD scheme using this. We compare
our scheme to HR [18], which applies the same truncation method but only uses
a block design from Sylvester’s Hadamard matrix and achieves a near-optimal
risk for $\epsilon=0.01$. Here, we set the range of $v$ from $1024=2^{10}$ to
$16383=2^{14}-1$.

Figure 2: Comparison of the proposed scheme, based on the truncation of the
symmetric block designs from Sylvester/Paley’s Hadamard matrix and twin prime
power difference set, and the HR scheme for $\epsilon=0.01$.

  2. 2.

$\epsilon=\log 3$: For our proposed scheme, we find a
$(v^{\prime},b,r,k,\lambda)$-symmetric block design from projective geometry
with $q=4$, nonzero quartic residue difference set, and quartic residue
difference set with smallest ${v^{\prime}\geq v}$. Then, we truncate it to
obtain a $(v,b,r,\lambda)$-RPBD, and construct an RPBD scheme using this. We
compare our scheme to PGR [20] with $q=4$, which applies the same truncation
method but only uses a block design from projective geometry with $q=4$ and
achieves a nearly optimal risk for $\epsilon=\log 3$. Here, we set the range
of $v$ from $1366=\frac{4^{6}-1}{3}+1$ to $21845=\frac{4^{8}-1}{3}$.

Figure 3: Comparison of the proposed scheme, based on the truncation of the
symmetric block designs of projective geometry with $q=4$ and quartic residue
difference sets (of both nonzero/including zero types), and the PGR scheme
with $q=4$ for $\epsilon=\log 3$.

Figs. 2 and 3 show that our schemes use smaller communication costs while
achieving nearly-optimal risks in both cases of $\epsilon$.

##  V Discussions

###  V-A Hadamard conjecture and an optimal block design scheme at high
privacy regime

There is a long unsolved conjecture, called the _Hadamard conjecture_[37]. One
of the equivalent statements for this conjecture is as follows:

######  Conjecture 1 (Hadamard conjecture[37])

For any positive integer $v\equiv 3\mod 4$, there is a symmetric block design
with $k=(v-1)/2$ and $\lambda=(v-3)/4$.

Remarkably, this conjecture is directly related to the existence of an optimal
block design scheme at high privacy regime ($\epsilon\approx 0$) for any input
data size $v$ with communication cost at most one bit larger than the input
data size. Specifically, the implication of Hadamard conjecture is as follows:

###### Proposition V.1

Suppose that the Hadamard conjecture is true. Then, for any $v\geq 2$, the
following statements hold:

  1. 1.

If $v\equiv 3\mod 4$ and
$\epsilon\leq\frac{1}{2}\log\frac{(v+1)(v+3)}{(v-1)(v-3)}$, there is a
symmetric block design scheme which achieves both the minimax risk (in both
the asymptotic and the non-asymptotic unbiased settings) and the minimum
communication cost of $b=v$.

  2. 2.

If $v\equiv 1\mod 4$ and
$\epsilon\leq\frac{1}{2}\log\frac{(v+1)(v+3)}{(v-1)(v-3)}$, there is a block
design scheme which achieves the minimax risk and the communication cost of
$b=2v$.

  3. 3.

If $v$ is even and $\epsilon\leq\frac{1}{2}\log\frac{v+2}{v-2}$, there is a
block design scheme which achieves the minimax risk and the communication cost
of $b=2v-2$.

###### Proof:

First, when $v$ is odd, we construct a block design scheme with $k=(v-1)/2$.
Note that for such $k$, we have

$\displaystyle E(k-1,k;v)$
$\displaystyle=\sqrt{\frac{(v+1)(v+3)}{(v-1)(v-3)}},$ (47) $\displaystyle
E(k,k+1;v)$ $\displaystyle=1.$ (48)

Thus, by Proposition III.6, such block design scheme achieves the minimax risk
for

$\displaystyle 1\leq e^{\epsilon}\leq\sqrt{\frac{(v+1)(v+3)}{(v-1)(v-3)}},$
(49)

and equivalently,

$\epsilon\leq\frac{1}{2}\log\frac{(v+1)(v+3)}{(v-1)(v-3)}.$ (50)

Next, when $v$ is even, we construct a block design scheme with $k=v/2$. For
such $k$, we have

$\displaystyle E(k-1,k;v)$ $\displaystyle=\sqrt{\frac{v+2}{v-2}},$ (51)
$\displaystyle E(k,k+1;v)$ $\displaystyle=\sqrt{\frac{v-2}{v+2}}<1.$ (52)

Thus, such block design scheme achieves the minimax risk for

$\displaystyle\sqrt{\frac{v-2}{v+2}}\leq
e^{\epsilon}\leq\sqrt{\frac{v+2}{v-2}},$ (53)

and equivalently,

$\epsilon\leq\frac{1}{2}\log\frac{v+2}{v-2}.$ (54)

  1. 1.

If $v\equiv 3\mod 4$ and
$\epsilon\leq\frac{1}{2}\log\frac{(v+1)(v+3)}{(v-1)(v-3)}$, the symmetric
block design with $k=(v-1)/2$ from the Hadamard conjecture gives the desired
scheme because of (50).

  2. 2.

If $v\equiv 1\mod 4$ and
$\epsilon\leq\frac{1}{2}\log\frac{(v+1)(v+3)}{(v-1)(v-3)}$, then
$v^{\prime}:=2v+1$ satisfies $v^{\prime}\equiv 3\mod 4$. Thus, by the Hadamard
conjecture, there is a
$(v^{\prime},b^{\prime},r^{\prime},k^{\prime},\lambda^{\prime})$-symmetric
block design with $k^{\prime}=(v^{\prime}-1)/2=v$ and
$\lambda^{\prime}=(v^{\prime}-3)/4=(v-1)/2$. Then, the derived block design
explained in Example 1 of such symmetric block design has parameters

$\displaystyle(v,b,r,k,\lambda)=(k^{\prime},v^{\prime}-1,k^{\prime}-1,\lambda^{\prime},\lambda^{\prime}-1)$
(55) $\displaystyle=(v,2v,v-1,(v-1)/2,(v-3)/2).$ (56)

Combining with (50), such derived block design gives the desired scheme.

  3. 3.

If $v$ is even and $\epsilon\leq\frac{1}{2}\log\frac{v+2}{v-2}$, then
$v^{\prime}:=2v-1$ satisfies $v^{\prime}\equiv 3\mod 4$. Thus, by the Hadamard
conjecture, there is a
$(v^{\prime},b^{\prime},r^{\prime},k^{\prime},\lambda^{\prime})$-symmetric
block design with $k^{\prime}=(v^{\prime}-1)/2=v-1$ and
$\lambda^{\prime}=(v^{\prime}-3)/4=(v/2)-1$. Then, the residual block design
explained in Example 1 of such symmetric block design has parameters

$\displaystyle(v,b,r,k,\lambda)=(v^{\prime}-k^{\prime},v^{\prime}-1,k^{\prime},k^{\prime}-\lambda^{\prime},\lambda^{\prime})$
(57) $\displaystyle=(v,2v-2,v-1,v/2,(v/2)-1).$ (58)

Combining with (54), such residual block design gives the desired scheme.

∎

###  V-B Other decomposable loss functions

In this paper, the (near) optimality of block design schemes and RPBD schemes
hinges on the asymptotic optimality of the SS under the $\ell_{u}^{u}$ loss,
$1\leq u\leq 2$ [26]. If the SS is optimal under some other decomposable loss
functions, most of the optimality results in this paper would be extended to
such loss functions. We note that the complete block designs [33], the block
designs used for the SS, satisfy more symmetry conditions than general block
designs. Due to such a strong symmetry, we conjecture that the SS would also
attain the minimax risk under other decomposable loss functions with nice
symmetry, e.g., $\ell_{u}^{u}$ loss for $u>2$, although the optimal value of
$k$ for given $(v,\epsilon)$ may differ. We provide two reasons supporting
this conjecture.

  * •

First, [38] showed that a SS mechanism with appropriately chosen $k$ maximizes
the mutual information between the mechanism input and the output for a
uniformly distributed input among all the $\epsilon$-LDP mechanisms, where the
appropriate $k$ is in general different from the one achieving the optimal
$\ell_{2}^{2}$ risks. From the definition of the mutual information, we can
show that two block design mechanisms with the same $(v,k,\epsilon)$ also have
the same mutual information. Hence, block design mechanisms with appropriate
$k$ also achieve the maximum mutual information.

  * •

Second, in the proof of showing the optimality of PrivUnit2[23] for mean
estimation in [27], it was shown that given a scheme, its ‘symmetrized’
version gives a lower or equal worst-case risk. Although this was shown for a
different target task of mean estimation and only for the $\ell_{2}^{2}$ loss,
we expect that the same would hold for discrete distribution estimation and
other decomposable loss functions with nice symmetry.

##  VI Conclusion

In this paper, we presented a new class of LDP schemes for private discrete
distribution estimation based on combinatorial block designs, and more
generally, regular and pairwise-balanced designs, which we call block design
schemes and RPBD schemes, respectively. In particular, the subset selection
(SS) scheme [16] achieving the minimax risk is a special case of the block
design schemes and hence also a special case of the RPBD schemes. By showing
sufficient and necessary conditions for the marginal equivalence between two
block design schemes and for two RPBD schemes, which guarantee that the two
schemes achieve the same risk, we could find many new schemes that achieve
(near-) optimal risks with much lower communication costs than SS.

##  Appendix A Proofs

In this section, we give the proofs for Theorems III.2, III.3, III.10, and
III.11, and Propositions III.6 and III.12. As block design schemes are special
cases of RPBD schemes, we first prove the theorems for the RPBD schemes, and
then extend the proofs to show the theorems for the block design schemes. We
first prove Theorems III.10 and III.11, and using them, we prove Theorems
III.2 and III.3. The proofs of Proposition III.6 and Proposition III.12 are
independent of other theorems and shown in the last part of this section.

####  A-1 Proof of Theorem III.10

By the $r$-regular and $\lambda$-pairwise balanced properties, we have

$\displaystyle Q(\mathcal{I}_{x}|x)$ $\displaystyle=\alpha
e^{\epsilon}|\mathcal{I}_{x}|=\alpha re^{\epsilon},$ (59)

and

$\displaystyle Q(\mathcal{I}_{x}|x^{\prime})$
$\displaystyle=|\mathcal{I}_{x}\cap\mathcal{I}_{x^{\prime}}|\alpha
e^{\epsilon}+|\mathcal{I}_{x}\backslash\mathcal{I}_{x^{\prime}}|\alpha$ (60)
$\displaystyle=\alpha(\lambda e^{\epsilon}+(r-\lambda)),$ (61)

for all $x\neq x^{\prime}$.

Therefore, for $X_{i}\sim P$ and $Y_{i}\sim Q(\cdot|X_{i})$, we have

$\displaystyle\Pr[(x,Y_{i})\in\mathcal{I}]$ $\displaystyle=$
$\displaystyle\sum_{x^{\prime}\in\mathcal{X}}Q(\mathcal{I}_{x}|x^{\prime})$
(62) $\displaystyle=$ $\displaystyle p_{x}\alpha
re^{\epsilon}+(1-P_{x})\alpha(\lambda e^{\epsilon}+(r-\lambda))$ (63)
$\displaystyle=$
$\displaystyle\alpha(P_{x}(r-\lambda)(e^{\epsilon}-1)+(\lambda
e^{\epsilon}+(r-\lambda))).$ (64)

Thus, $N_{x}(Y_{1},\cdots,Y_{n})$ is a binomial random variable with $n$
trials and success probability

$\displaystyle\alpha(P_{x}(r-\lambda)(e^{\epsilon}-1)+(\lambda
e^{\epsilon}+(r-\lambda))).$ (65)

In particular, its mean under $P$ is

$\displaystyle\mathbb{E}_{P}[N_{x}(Y_{1},\cdots,Y_{n})]=n\alpha(P_{x}(r-\lambda)(e^{\epsilon}-1)+(\lambda
e^{\epsilon}+(r-\lambda))).$ (66)

Hence, we have

$\displaystyle
P_{x}=\frac{1}{(r-\lambda)(e^{\epsilon}-1)}\left(\frac{\mathbb{E}_{P}\left[N_{x}(Y_{1},\cdots,Y_{n})\right]}{n\alpha}-(\lambda
e^{\epsilon}+(r-\lambda))\right).$ (67)

Thus, the following estimator

$\displaystyle\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})=\frac{1}{(r-\lambda)(e^{\epsilon}-1)}\left(\frac{N_{x}(Y_{1},\cdots,Y_{n})}{n\alpha}-(\lambda
e^{\epsilon}+(r-\lambda))\right)$ (68)

is an unbiased estimator.

Next, let us derive the risk under the mean squared loss. We follow the same
procedures in [18, Theorem 2], except that none of upper and lower bounds are
taken to derive the risk. Recall that $N_{x}(Y_{1},\cdots,Y_{n})$ is a
binomial random variable with $n$ trials and success probability of the form
$cP_{x}+d$, where

$\displaystyle c$ $\displaystyle=$
$\displaystyle\alpha(r-\lambda)(e^{\epsilon}-1),$ (69) $\displaystyle d$
$\displaystyle=$ $\displaystyle\alpha(\lambda e^{\epsilon}+r-\lambda),$ (70)
$\displaystyle\alpha$ $\displaystyle=$
$\displaystyle\frac{1}{re^{\epsilon}+b-r}.$ (71)

Hence, we get

$\displaystyle\mathbb{E}[N_{x}(Y_{1},\cdots,Y_{n})]=n(cP_{x}+d),$ (72)
$\displaystyle
P_{x}=\frac{\mathbb{E}[N_{x}(Y_{1},\cdots,Y_{n})]}{nc}-\frac{d}{c}.$ (73)

Using this, we set the estimator into

$\displaystyle\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})=\frac{N_{x}(Y_{1},\cdots,Y_{n})}{nc}-\frac{d}{c},$
(74)

so that it is unbiased.

Since this estimator is unbiased, the risk under the $\ell_{2}^{2}$ loss is
the same as the sum of the variances of all $\hat{P}_{x}(Y_{1},\cdots,Y_{n})$.
Therefore, we have

$\displaystyle R_{v,n}(\ell_{2}^{2},P,Q,\hat{P}_{n})$ $\displaystyle=$
$\displaystyle\sum_{x\in\mathcal{X}}\mathrm{Var}[\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})]$
(75) $\displaystyle=$
$\displaystyle\frac{1}{n^{2}c^{2}}\sum_{x\in\mathcal{X}}\mathrm{Var}[N_{x}(Y_{1},\cdots,Y_{n})]$
(76) $\displaystyle=$
$\displaystyle\frac{1}{n^{2}c^{2}}\sum_{x\in\mathcal{X}}n(cP_{x}+d)(1-(cP_{x}+d))$
(77) $\displaystyle=$
$\displaystyle\frac{1}{nc^{2}}\sum_{x\in\mathcal{X}}(cP_{x}+d)(1-(cP_{x}+d))$
(78) $\displaystyle=$
$\displaystyle\frac{1}{nc^{2}}\sum_{x\in\mathcal{X}}(-c^{2}P_{x}^{2}+\gamma_{1}P_{x}+\gamma_{0})$
(79) $\displaystyle=$
$\displaystyle\frac{1}{nc^{2}}\left(-c^{2}\sum_{x\in\mathcal{X}}P_{x}^{2}+\gamma_{1}+\gamma_{0}v\right)$
(80) $\displaystyle=$
$\displaystyle\frac{1}{n}\left(\delta-\sum_{x\in\mathcal{X}}P_{x}^{2}\right),$
(81)

where $\gamma_{1},\gamma_{0},\delta$ are constants which depend on parameters
and do not depend on $P$. Hence, the worst-case risk is attained when
$\sum_{x\in\mathcal{X}}P_{x}^{2}$ is minimized. Since
$\sum_{x\in\mathcal{X}}P_{x}=1$, by the Cauchy-Schwartz inequality, we have

$\displaystyle\sum_{x\in\mathcal{X}}P_{x}^{2}\geq\frac{1}{\left(\sum_{x\in\mathcal{X}}1\right)}=\frac{1}{v},$
(82)

and the equality is attained when $P_{x}=\frac{1}{v}$ for all
$x\in\mathcal{X}$. Thus, the worst-case risk is attained when $P$ is the
uniform distribution.

From equation (78) and substituting $P_{x}=1/v$, we have

$\displaystyle R^{*}_{v,n}(\ell_{2}^{2},Q,\hat{P}_{n})$ $\displaystyle=$
$\displaystyle\frac{1}{nc^{2}}\sum_{x\in\mathcal{X}}\left(\frac{c}{v}+d\right)\left(1-\left(\frac{c}{v}+d\right)\right)$
(83) $\displaystyle=$
$\displaystyle\frac{v}{nc^{2}}\left(\frac{c}{v}+d\right)\left(1-\left(\frac{c}{v}+d\right)\right)$
(84) $\displaystyle=$ $\displaystyle\frac{1}{nc^{2}v}(c+dv)(v-c-dv).$ (85)

Observe that $c+d=\alpha re^{\epsilon}$. Using this, we have

$\displaystyle c+dv$ $\displaystyle=$ $\displaystyle(c+d)+(v-1)d$ (86)
$\displaystyle=$ $\displaystyle\alpha re^{\epsilon}+(v-1)\alpha(\lambda
e^{\epsilon}+r-\lambda)$ (87) $\displaystyle=$
$\displaystyle\alpha(re^{\epsilon}+(v-1)(\lambda e^{\epsilon}+r-\lambda)),$
(88)

and

$\displaystyle v-c-dv$ $\displaystyle=$ $\displaystyle
v-\alpha(re^{\epsilon}+(v-1)(\lambda e^{\epsilon}+r-\lambda))$ (89)
$\displaystyle=$
$\displaystyle\alpha\left(\frac{v}{\alpha}-(re^{\epsilon}+(v-1)(\lambda
e^{\epsilon}+r-\lambda))\right)$ (90) $\displaystyle=$
$\displaystyle\alpha\left(\frac{1}{\alpha}-re^{\epsilon}-(v-1)\left(\lambda
e^{\epsilon}+r-\lambda-\frac{1}{\alpha}\right)\right)$ (91) $\displaystyle=$
$\displaystyle\alpha(b-r-(v-1)\left((\lambda-r)(e^{\epsilon}-1)-(b-r)\right))$
(92) $\displaystyle=$
$\displaystyle\alpha(v(b-r)-(v-1)(\lambda-r)(e^{\epsilon}-1)).$ (93)

Hence, we have

$\displaystyle
R^{*}_{v,n}(\ell_{2}^{2},Q,\hat{P}_{n})=\frac{1}{nc^{2}v}(c+dv)(v-c-dv)$ (94)
$\displaystyle=\frac{re^{\epsilon}+(v-1)(\lambda
e^{\epsilon}+r-\lambda)}{(r-\lambda)^{2}(e^{\epsilon}-1)^{2}nk}\left[v(b-r)+(v-1)(r-\lambda)(e^{\epsilon}-1)\right].$

Also, from equation (81), we have

$\displaystyle R^{*}_{v,n}(\ell_{2}^{2},Q,\hat{P})$ $\displaystyle=$
$\displaystyle R_{v,n}(\ell_{2}^{2},P,Q,\hat{P})|_{P_{x}=1/v}$ (95)
$\displaystyle=$
$\displaystyle\frac{1}{n}\left(\delta-\sum_{x\in\mathcal{X}}\frac{1}{v^{2}}\right)$
(96) $\displaystyle=$
$\displaystyle\frac{1}{n}\left(\delta-\frac{v}{v^{2}}\right)$ (97)
$\displaystyle=$ $\displaystyle\frac{1}{n}\left(\delta-\frac{1}{v}\right).$
(98)

Thus, we have

$\displaystyle\delta=\frac{re^{\epsilon}+(v-1)(\lambda
e^{\epsilon}+r-\lambda)}{(r-\lambda)^{2}(e^{\epsilon}-1)^{2}v}\left[v(b-r)+(v-1)(r-\lambda)(e^{\epsilon}-1)\right]+\frac{1}{v}.$
(99)

This proves the theorem.

####  A-2 Proof of Theorem III.11

Let $(Q,\hat{P}_{n})$ and $(Q^{\prime},\hat{P}_{n}^{\prime})$ be RPBD schemes
with parameters $(v,b,r,\lambda,\epsilon)$ and
$(v,b^{\prime},r^{\prime},\lambda^{\prime},\epsilon)$, constructed from
incidence structures $\mathcal{I},\mathcal{I}^{\prime}$, respectively.

Let ${\alpha=1/(re^{\epsilon}+b-r)}$ and
${\alpha^{\prime}=1/(r^{\prime}e^{\epsilon}+b^{\prime}-r^{\prime})}$ be the
normalization constants for $Q$ and $Q^{\prime}$, respectively. Also, let

$\displaystyle N_{x}(Y_{1},\cdots,Y_{n})$
$\displaystyle=\sum_{i=1}^{n}\mathbbm{1}(Y_{i}\in\mathcal{I}_{x}),$ (100)
$\displaystyle N_{x}^{\prime}(Y_{1}^{\prime},\cdots,Y_{n}^{\prime})$
$\displaystyle=\sum_{i=1}^{n}\mathbbm{1}(Y_{i}^{\prime}\in\mathcal{I}^{\prime}_{x}).$
(101)

First, assume that $(b^{\prime},r^{\prime},\lambda^{\prime})=t(b,r,\lambda)$,
$t>0$. By the assumption, we have $\alpha^{\prime}=\frac{1}{t}\alpha$. By
comparing the success probability in (65), we can see that

$\displaystyle\alpha(P_{x}(r-\lambda)(e^{\epsilon}-1)+(\lambda
e^{\epsilon}+(r-\lambda)))=\alpha^{\prime}(P_{x}(r^{\prime}-\lambda^{\prime})(e^{\epsilon}-1)+(\lambda^{\prime}e^{\epsilon}+(r^{\prime}-\lambda^{\prime}))),$
(102)

for all $P_{x}\in[0,1]$. Hence

$\displaystyle
N_{x}(Y_{1},\cdots,Y_{n})\overset{d}{=}N_{x}^{\prime}(Y_{1}^{\prime},\cdots,Y_{n}^{\prime}),$
(103)

for all $P\in\Delta_{v}$.

Next, let us compare the formula of the estimator in (68). The formula is of
the form

$\displaystyle\hat{P}_{n,x}=g\frac{N_{x}}{n}-h,\quad\hat{P}^{\prime}_{n,x}=g^{\prime}\frac{N_{x}^{\prime}}{n}-h^{\prime},$
(104)

where

$\displaystyle g$
$\displaystyle=\frac{1}{\alpha}\frac{1}{(r-\lambda)(e^{\epsilon}-1)},$
$\displaystyle h$ $\displaystyle=\frac{\lambda
e^{\epsilon}+(r-\lambda)}{(r-\lambda)(e^{\epsilon}-1)},$ (105) $\displaystyle
g^{\prime}$
$\displaystyle=\frac{1}{\alpha^{\prime}}\frac{1}{(r^{\prime}-\lambda^{\prime})(e^{\epsilon}-1)},$
$\displaystyle h^{\prime}$
$\displaystyle=\frac{\lambda^{\prime}e^{\epsilon}+(r^{\prime}-\lambda^{\prime})}{(r^{\prime}-\lambda^{\prime})(e^{\epsilon}-1)}.$
(106)

Again, we can see that $g=g^{\prime}$ and $h=h^{\prime}$. Together with (103),
we get the desired marginal equivalence.

Conversely, assume that $(Q,\hat{P}_{n})$ and
$(Q^{\prime},\hat{P}_{n}^{\prime})$ are marginally equivalent. From
$b>r>\lambda$, we can show that (65) is neither $0$ nor $1$ for $P_{x}=0$.
Thus, $N_{x}(Y_{1},\cdots,Y_{n})$ have support $\\{0,1,\cdots,n\\}$. From
(104), the estimator $\hat{P}_{n,x}(Y_{1},\cdots,Y_{n})$ have support
$\\{-h,-h+g/n,-h+2g/n,\cdots,g-h\\}$. Similarly,
$\hat{P}_{n,x}^{\prime}(Y_{1}^{\prime},\cdots,Y_{n}^{\prime})$ have support
$\\{-h^{\prime},-h^{\prime}+g^{\prime}/n,-h^{\prime}+2g^{\prime}/n,\cdots,g^{\prime}-h^{\prime}\\}$.
For the marginal equivalence, the support must be the same. Thus, either

$\displaystyle-h=-h^{\prime},\quad g-h=g^{\prime}-h^{\prime},$ (107)

or

$\displaystyle-h=g^{\prime}-h^{\prime},\quad g-h=-h^{\prime}.$ (108)

Note that from $b>r>\lambda$, we have $\alpha,g,h,g^{\prime},h^{\prime}>0$.
Hence, (108) implies $g=h-h^{\prime}=-g^{\prime}$, which is impossible. Thus
we must have (107). This implies $g=g^{\prime}$ and $h=h^{\prime}$.

Now, by fixing $b^{\prime},r^{\prime},\lambda^{\prime},g^{\prime},h^{\prime}$,
the equations

$\displaystyle
g=\frac{re^{\epsilon}+b-r}{(r-\lambda)(e^{\epsilon}-1)}=g^{\prime}$ (109)
$\displaystyle h=\frac{\lambda
e^{\epsilon}+(r-\lambda)}{(r-\lambda)(e^{\epsilon}-1)}=h^{\prime}$ (110)

can be seen as a system of linear equations in $(b,r,\lambda)$:

$\begin{cases}b+(e^{\epsilon}-1)(1-g^{\prime})r+(e^{\epsilon}-1)g^{\prime}\lambda=0\\\
(1-(e^{\epsilon}-1)h^{\prime})r+(e^{\epsilon}-1)(1+h^{\prime})\lambda=0\end{cases},$
(111)

which has a particular solution
$(b,r,\lambda)=(b^{\prime},r^{\prime},\lambda^{\prime})$. Since
$(e^{\epsilon}-1)(1+h^{\prime})>0$, it can be easily observed that the matrix
of the coefficients for this system has rank $2$. Hence, the dimension of the
solution space is $1$. Thus, $(b,r,\lambda)$ must be a constant multiple of a
particular solution $(b^{\prime},r^{\prime},\lambda^{\prime})$. Since
$b,b^{\prime}>0$, the constant multiplied must be a positive number. This ends
the proof of the theorem.

####  A-3 Proof of Theorems III.2 and III.3

First, let us prove Theorem III.3. From Lemma III.1, it can be easily checked
that

$\displaystyle(b,r,\lambda)=t(v(v-1),k(v-1),k(k-1)),$ (112)
$\displaystyle(b^{\prime},r^{\prime},\lambda^{\prime})=t^{\prime}(v(v-1),k^{\prime}(v-1),k^{\prime}(k^{\prime}-1)),$
(113)

for $t=\frac{b}{v(v-1)}$, $t^{\prime}=\frac{b^{\prime}}{v(v-1)}$. Hence, the
desired necessary and sufficient condition for marginal equivalence directly
follows from Theorem III.11.

For Theorem III.2, the formula of the unbiased estimator is the same as
Theorem III.10. The formula of the risk is derived by substitution of

$\displaystyle(b,r,\lambda)=t(v(v-1),k(v-1),k(k-1))$ (114)

into the formula in Theorem III.10 and cancellation of $t$.

####  A-4 Proof of Proposition III.6

Let us recall that

$\displaystyle E(k_{1},k_{2};v)=\sqrt{\frac{(v-k_{1})(v-k_{2})}{k_{1}k_{2}}},$
(115)

which is defined for $0\leq k_{1}<k_{2}\leq v$, $(k_{1},k_{2})\neq(0,v)$. We
set $E(0,k_{2};v)=\infty$ for any $k_{2}\in[1:v-1]$.

Let $L(v,k,\epsilon)=\frac{(ke^{\epsilon}+v-k)^{2}}{k(v-k)}$, $1\leq k\leq
v-1$. Also, let $L(v,0,\epsilon)=L(v,v,\epsilon)=\infty$. First, let us show
the following lemma, whose proof is at the end of this section.

###### Lemma A.1

Let $0\leq k_{1}<k_{2}\leq v$, $(k_{1},k_{2})\neq(0,v)$. Then
$L(v,k_{1},\epsilon)\leq L(v,k_{2},\epsilon)$ if and only if $e^{\epsilon}\geq
E(k_{1},k_{2};v)$.

Now, first assume that $k\in K_{opt}(v,\epsilon)$. Then, $L(v,k,\epsilon)\leq
L(v,k-1,\epsilon)$ and $L(v,k,\epsilon)\leq L(v,k+1,\epsilon)$. Then, by the
above lemma, we have $E(k,k+1;v)\leq e^{\epsilon}\leq E(k-1,k;v)$.

Conversely, assume that $E(k,k+1;v)\leq e^{\epsilon}\leq{E(k-1,k;v)}$. Note
that $E(k_{1},k_{2};v)$ is strictly decreasing in both $k_{1}$ and $k_{2}$.
Thus, we have $E(k,k^{\prime};v)\leq E(k,k+1;v)\leq e^{\epsilon}$ for all
$k^{\prime}\geq k+1$. So, by the lemma, $L(v,k,\epsilon)\leq
L(v,k^{\prime},\epsilon)$ for all $k^{\prime}\geq k+1$. Similarly,
$E(k^{\prime},k;v)\geq E(k-1,k;v)\geq e^{\epsilon}$ for all $k^{\prime}\leq
k-1$. So, $L(v,k,\epsilon)\leq L(v,k^{\prime},\epsilon)$ for all
$k^{\prime}\leq k-1$. This shows that given $k$ minimizes $L(v,k,\epsilon)$,
so that $k\in K_{opt}(v,\epsilon)$.

The statement about the cardinality of $K_{opt}(v,\epsilon)$ directly follows
from the observation that $E(k,k+1;v)$ is strictly decreasing in $k$.

####  A-5 Proof of Proposition III.12

For each $y\in\mathcal{Y}$, let ${k(y)=|\mathcal{I}^{y}|}$. We need to show
that $k(y)=k$ for all $y\in\mathcal{Y}$. The key technique is to show that the
empirical variance of $k(y)$ is zero, that is

$\displaystyle\sigma^{2}:=\frac{\sum_{y}k(y)^{2}}{b}-\left(\frac{\sum_{y}k(y)}{b}\right)^{2}=0.$
(116)

First, by the double counting argument, we can easily observe that

$\displaystyle|\mathcal{I}|=vr=\sum_{y\in\mathcal{Y}}k(y),$ (117)

and

$\displaystyle|\\{(x_{1},x_{2},y):(x_{1},y)\in\mathcal{I},(x_{2},y)\in\mathcal{I},x_{1}\neq
x_{2}\\}|=\lambda v(v-1)=\sum_{y\in\mathcal{Y}}k(y)(k(y)-1).$ (118)

From these, we get

$\displaystyle\sum_{y\in\mathcal{Y}}k(y)^{2}=v(\lambda(v-1)+r),$ (119)

and

$\displaystyle\sigma^{2}=v\left(\frac{\lambda}{b}(v-1)+\frac{r}{b}-\left(\frac{r}{b}\right)^{2}v\right).$
(120)

By substituting $\frac{\lambda}{b}=\frac{k(k-1)}{v(v-1)}$ and
$\frac{r}{b}=\frac{k}{v}$, we get $\sigma^{2}=0$. Hence, all of $k(y)$ are the
same. Also, from (117), we get $vr=bk(y)$, $k(y)=vr/b=vk/v=k$.

####  A-6 Proof of Lemma A.1

If $k_{1}=0$, then ${L(v,k_{1},\epsilon)=\infty}$,
${L(v,k_{2},\epsilon)<\infty}$, $E(k_{1},k_{2};v)=\infty$. Hence, the
statement is vacuously true. Also, if $k_{2}=v$, then
$L(v,k_{2},\epsilon)=\infty$, $E(k_{1},k_{2};v)=0$. Hence, the statement is
always true. Thus, it suffices to show for $k_{1},k_{2}\in[1:v-1]$.

We can observe that

$\displaystyle\sqrt{L(v,k,\epsilon)}$
$\displaystyle=\frac{ke^{\epsilon}+v-k}{\sqrt{k(v-k)}}$ (121)
$\displaystyle=\sqrt{\frac{k}{v-k}}e^{\epsilon}+\sqrt{\frac{v-k}{k}}.$ (122)

Let $C_{1}=\sqrt{\frac{v-k_{1}}{k_{1}}}$,
$C_{2}=\sqrt{\frac{v-k_{2}}{k_{2}}}$. Note that $C_{1}>C_{2}$ and
$C_{1}C_{2}=E(k_{1},k_{2};v)$. Then, the condition $L(v,k_{1},\epsilon)\leq
L(v,k_{2},\epsilon)$ can be equivalently written as

$\displaystyle\sqrt{L(v,k_{1},\epsilon)}\leq\sqrt{L(v,k_{2},\epsilon)}$ (123)
$\displaystyle\Leftrightarrow\frac{1}{C_{1}}e^{\epsilon}+C_{1}\leq\frac{1}{C_{2}}e^{\epsilon}+C_{2}$
(124)
$\displaystyle\Leftrightarrow\frac{C_{2}-C_{1}}{C_{1}C_{2}}e^{\epsilon}\leq
C_{2}-C_{1}$ (125) $\displaystyle\Leftrightarrow e^{\epsilon}\geq
C_{1}C_{2}=E(k_{1},k_{2};v).$ (126)

This ends the proof of the lemma.

##  Appendix B Descriptions of block designs

The proofs showing that the below incidence structures indeed satisfy the
properties of block designs can be found in [35, 33].

####  B-1 Trivial symmetric block design

Let $v\geq 2$ be given. For $\mathcal{X}=\\{1,2,\cdots,v\\}$, let
$\mathcal{Y}=\mathcal{X}$, and $\mathcal{I}=\\{(x,y):x=y\\}.$ This is a
symmetric block design with $k=1$.

####  B-2 Complete block design

This is in general non-symmetric block design. Let $1\leq k<v$ be given. For
$\mathcal{X}=\\{1,2,\cdots,v\\}$, let $\mathcal{Y}$ be the collection of all
subsets of $\mathcal{X}$ of size $k$, that is

$\displaystyle\mathcal{Y}=\binom{\mathcal{X}}{k}.$ (127)

Each $y\in\mathcal{Y}$ is a subset of $\mathcal{X}$. An incidence structure is
defined by

$\displaystyle\mathcal{I}=\\{(x,y):x\in y\\}.$ (128)

Note that the complete block design with $k=1$ is the same as the trivial
symmetric block design.

####  B-3 Projective geometry

Let $q,t$ be positive integers such that $q$ is a prime power and $t\geq 2$.
Let $\mathbb{F}_{q}$ be the finite field of order $q$, and let
$P(\mathbb{F}_{q}^{t})$ be the set of all 1-dimensional subspaces of
$t$-dimensional vector space $\mathbb{F}_{q}^{t}$, called the projective
space. We identify $\mathcal{X}$ as this projective space
$\mathcal{X}=P(\mathbb{F}_{q}^{t})$, which has size $\frac{q^{t}-1}{q-1}$.
Also, let $\mathcal{Y}$ be the collection of all $(t-1)$-dimensional subspaces
of $\mathbb{F}_{q}^{t}$. By letting

$\displaystyle\mathcal{I}=\\{(x,y):x\subset y\\},$ (129)

this is a symmetric block design with $v=\frac{q^{t}-1}{q-1}$,
$k=\frac{q^{t-1}-1}{q-1}$.

####  B-4 Sylvester’s Hadamard matrix

Define the Sylvester’s Hadamard matrix as follows: Let
$H_{2}=\begin{pmatrix}1&1\\\ 1&-1\end{pmatrix}$, and for each $t\geq 2$,
recursively define

$\displaystyle H_{2^{t}}=\begin{pmatrix}H_{2^{t-1}}&H_{2^{t-1}}\\\
H_{2^{t-1}}&-H_{2^{t-1}}\end{pmatrix}.$ (130)

Let $t\geq 2$. We identify $\mathcal{X}=\mathcal{Y}=\\{2,3,4,\cdots,2^{t}\\}$,
and define

$\displaystyle\mathcal{I}=\\{(x,y):\text{the }(x,y)\text{'th component of
}H_{2^{t}}\text{ is }1\\}.$ (131)

This is a symmetric block design with $v=2^{t}-1$, $k=2^{t-1}-1$.

####  B-5 Paley’s Hadamard matrix

Although the description by Hadamard matrix is well-known, we present an
alternative but equivalent description by difference set[35], which gives an
easy way to implement the scheme.

Let $v$ be a prime power such that $v\equiv 3\mod 4$. We identify
$\mathcal{X}=\mathcal{Y}=\mathbb{F}_{v}$, the finite field of order $v$. By
letting

$\displaystyle\mathcal{I}=\\{(x,y):y-x=a^{2}\text{ for some
}a\in\mathbb{F}_{v}^{\times}\\},$ (132)

this is a symmetric block design with $k=(v-1)/2$.

####  B-6 Twin prime power difference set

Let $q$ be an odd natural number such that both $q$ and $q+2$ are prime
powers. We identify
$\mathcal{X}=\mathcal{Y}=\mathbb{F}_{q}\times\mathbb{F}_{q+2}$, the direct
product of finite fields of order $q$ and $q+2$. Define $\mathcal{I}$ to be
the set of all $(x,y)$ such that

$\displaystyle y-x=(a_{1},a_{2})\in\mathbb{F}_{q}\times\mathbb{F}_{q+2}$ (133)

implies $(a_{1},a_{2})$ to satisfy either one of the following three
conditions:

  * •

$a_{2}=0$.

  * •

both $a_{1},a_{2}$ are non-zero squares in
$\mathbb{F}_{q}^{\times},\mathbb{F}_{q+2}^{\times}$ respectively.

  * •

both $a_{1},a_{2}$ are non-zero non-squares in
$\mathbb{F}_{q}^{\times},\mathbb{F}_{q+2}^{\times}$ respectively.

This is a symmetric block design with $v=q(q+2)$, ${k=\frac{q(q+2)-1}{2}}$.

####  B-7 Nonzero quartic residue difference set

Let $v$ be a prime power such that $v=4t^{2}+1$ for some odd integer $t$. We
identify $\mathcal{X}=\mathcal{Y}=\mathbb{F}_{v}$, the finite field of order
$v$. Define

$\displaystyle\mathcal{I}=\\{(x,y):y-x=a^{4}\text{ for some
}a\in\mathbb{F}_{v}^{\times}\\}.$ (134)

This is a symmetric block design with $k=(v-1)/4$.

####  B-8 (Including zero) Quartic residue difference set

Let $v$ be a prime power such that $v=4t^{2}+9$ for some odd integer $t$. We
identify $\mathcal{X}=\mathcal{Y}=\mathbb{F}_{v}$, the finite field of order
$v$. We define

$\displaystyle\mathcal{I}=\\{(x,y):y-x=a^{4}\text{ for some
}a\in\mathbb{F}_{v}\\}.$ (135)

Note that we allow $a=0$ in this definition. This is a symmetric block design
with $k=(v+3)/4$.

## References

  * [1] H.-Y. Park, S.-H. Nam, and S.-H. Lee, “Block Design-Based local differential privacy mechanisms,” in _2023 IEEE Int. Symp. Inf. Theory (ISIT) (ISIT’2023)_ , Taipei, Taiwan, Jun. 2023.
  * [2] A. Narayanan and V. Shmatikov, “How to break anonymity of the Netflix prize dataset,” 2006. [Online]. Available: arXiv:cs/0610105
  * [3] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in _Proc. 22nd ACM SIGSAC Conf. Computer and Communications Security_ , ser. CCS ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 1322–1333.
  * [4] R. Shokri, M. Stronati, C. Song, and V. Shmatikov, “Membership inference attacks against machine learning models,” in _2017 IEEE Symp. Security and Privacy (SP)_ , 2017, pp. 3–18.
  * [5] S. Yeom, I. Giacomelli, M. Fredrikson, and S. Jha, “Privacy risk in machine learning: Analyzing the connection to overfitting,” in _2018 IEEE 31st Computer Security Foundations Symp. (CSF)_ , 2018, pp. 268–282.
  * [6] A. Salem, A. Bhattacharya, M. Backes, M. Fritz, and Y. Zhang, “Updates-Leak: Data set inference and reconstruction attacks in online learning,” in _29th USENIX security Symp. (USENIX Security 20)_ , 2020, pp. 1291–1308.
  * [7] L. Melis, C. Song, E. De Cristofaro, and V. Shmatikov, “Exploiting unintended feature leakage in collaborative learning,” in _2019 IEEE Symp. Security and Privacy (SP)_ , 2019, pp. 691–706.
  * [8] J. Geiping, H. Bauermeister, H. Dröge, and M. Moeller, “Inverting gradients - How easy is it to break privacy in federated learning?” in _Advances in Neural Information Processing Systems_ , vol. 33. Curran Associates, Inc., 2020, pp. 16 937–16 947.
  * [9] J. Liao, O. Kosut, L. Sankar, and F. du Pin Calmon, “Tunable measures for information leakage and applications to privacy-utility tradeoffs,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 12, pp. 8043–8066, 2019.
  * [10] I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 3, pp. 1625–1657, 2020\.
  * [11] C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” in _Theory of cryptography conference_. Springer, 2006, pp. 265–284.
  * [12] I. Mironov, “Rényi differential privacy,” in _2017 IEEE 30th Computer Security Foundations Symp. (CSF)_ , 2017, pp. 263–275.
  * [13] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 6, pp. 4037–4049, 2017\.
  * [14] S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” _Journal of the American Statistical Association_ , vol. 60, no. 309, pp. 63–69, 1965.
  * [15] U. Erlingsson, V. Pihur, and A. Korolova, “RAPPOR: Randomized aggregatable privacy-preserving ordinal response,” in _Proc. 2014 ACM SIGSAC Conf. Computer and Communications Security_ , ser. CCS ’14. New York, NY, USA: Association for Computing Machinery, 2014, pp. 1054–1067.
  * [16] M. Ye and A. Barg, “Optimal schemes for discrete distribution estimation under locally differential privacy,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 8, pp. 5662–5676, 2018.
  * [17] T. Wang, J. Blocki, N. Li, and S. Jha, “Locally differentially private protocols for frequency estimation,” in _26th USENIX Security Symp. (USENIX Security 17)_. Vancouver, BC: USENIX Association, Aug. 2017, pp. 729–745.
  * [18] J. Acharya, Z. Sun, and H. Zhang, “Hadamard response: Estimating distributions privately, efficiently, and with little communication,” in _Proc. 22nd Int. Conf. Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, vol. 89. PMLR, 16–18 Apr 2019, pp. 1120–1129.
  * [19] W.-N. Chen, P. Kairouz, and A. Özgür, “Breaking the communication-privacy-accuracy trilemma,” in _Advances in Neural Information Processing Systems_ , vol. 33. Curran Associates, Inc., 2020, pp. 3312–3324.
  * [20] V. Feldman, J. Nelson, H. Nguyen, and K. Talwar, “Private frequency estimation via projective geometry,” in _Proc. 39th Int. Conf. Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 162. PMLR, 17–23 Jul 2022, pp. 6418–6433.
  * [21] J. Duchi, M. J. Wainwright, and M. I. Jordan, “Local privacy and minimax bounds: Sharp rates for probability estimation,” in _Advances in Neural Information Processing Systems_ , vol. 26, 2013, pp. 1529–1537.
  * [22] N. Wang, X. Xiao, Y. Yang, J. Zhao, S. C. Hui, H. Shin, J. Shin, and G. Yu, “Collecting and analyzing multidimensional data with local differential privacy,” in _2019 IEEE 35th Int. Conf. Data Engineering (ICDE)_ , 2019, pp. 638–649.
  * [23] A. Bhowmick, J. Duchi, J. Freudiger, G. Kapoor, and R. Rogers, “Protection against reconstruction and its applications in private federated learning,” 2018\. [Online]. Available: arXiv:1812.00984
  * [24] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in _2013 IEEE 54th Annu. Symp. Foundations of Computer Science_ , 2013, pp. 429–438.
  * [25] L. P. Barnes, W.-N. Chen, and A. Özgür, “Fisher information under local differential privacy,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 1, no. 3, pp. 645–659, 2020.
  * [26] M. Ye and A. Barg, “Optimal locally private estimation under $\ell_{p}$ loss for $1\leq p\leq 2$,” _Electronic Journal of Statistics_ , vol. 13, no. 2, pp. 4102 – 4120, 2019.
  * [27] H. Asi, V. Feldman, and K. Talwar, “Optimal algorithms for mean estimation under local differential privacy,” 2022. [Online]. Available: arXiv:2205.02466
  * [28] M. Li, D. G. Andersen, A. J. Smola, and K. Yu, “Communication efficient distributed machine learning with the parameter server,” in _Advances in Neural Information Processing Systems_ , vol. 27. Curran Associates, Inc., 2014, pp. 19–27.
  * [29] M. I. Jordan, J. D. Lee, and Y. Yang, “Communication-efficient distributed statistical inference,” _Journal of the American Statistical Association_ , vol. 114, no. 526, pp. 668–681, 2019.
  * [30] Y. Zhang, M. J. Wainwright, and J. C. Duchi, “Communication-efficient algorithms for statistical optimization,” in _Advances in Neural Information Processing Systems_ , vol. 25. Curran Associates, Inc., 2012, pp. 1502–1510.
  * [31] R. Bassily and A. Smith, “Local, private, efficient protocols for succinct histograms,” in _Proc. 47th Annu. ACM Symp. Theory of Computing_ , ser. STOC ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 127–135.
  * [32] A. Shah, W.-N. Chen, J. Ballé, P. Kairouz, and L. Theis, “Optimal compression of locally differentially private mechanisms,” in _Proc. 25th Int. Conf. Artificial Intelligence and Statistics_ , ser. Proceedings of Machine Learning Research, vol. 151. PMLR, 28–30 Mar 2022, pp. 7680–7723.
  * [33] Y. J. Ionin and M. S. Shrikhande, _Combinatorics of Symmetric Designs_. Cambridge University Press, 2006, vol. 5.
  * [34] S. Jukna, _Extremal Combinatorics: With Applications in Computer Science_. Springer, 2011, vol. 571.
  * [35] E. H. Moore and H. S. K. Pollatsek, _Difference sets: Connecting Algebra, Combinatorics, and Geometry_. American Mathematical Soc., 2013, vol. 67.
  * [36] J. Acharya and Z. Sun, “Communication complexity in locally private distribution estimation and heavy hitters,” in _Proc. 36th Int. Conf. Machine Learning_ , ser. Proceedings of Machine Learning Research, vol. 97. PMLR, 09–15 Jun 2019, pp. 51–60.
  * [37] E. P. Tressler, “A survey of the Hadamard conjecture,” Ph.D. dissertation, Dept. Math., Virginia Polytech. Inst. State Univ., Blacksburg, VA, USA, 2004.
  * [38] S. Wang, L. Huang, P. Wang, Y. Nie, H. Xu, W. Yang, X.-Y. Li, and C. Qiao, “Mutual information optimally local private discrete distribution estimation,” 2016. [Online]. Available: arXiv:1607.08025