Necessity of Block Designs for Optimal Locally Private Distribution Estimation
Abigail Gentle · 2025
Read Necessity of Block Designs for Optimal Locally Private Distribution Estimation by Abigail Gentle (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05110.txt.
Introduction
Abigail Gentle proves that the best private data-collection schemes must have a combinatorial shape, in a 2025 paper. Local differential privacy scrambles each person's answer before it leaves their phone, so a company can estimate population statistics without seeing anyone's true value. Protocols built on balanced incomplete block designs, tidy arrangements of subsets, were known to achieve the lowest possible error.
The open question was whether anything else could match them. Gentle's answer is no: any protocol reaching optimal error corresponds to such a design. Combined with earlier work, this completely characterizes the optimal protocols. Requiring optimal communication too narrows the field further, to the symmetric designs. For engineers, the theorem ends a search: there is one family of shapes to use, and it is already known.
Catalog record
| CREATOR | Abigail Gentle |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05110
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Necessity of Block Designs for Optimal Locally Private Distribution Estimation Thanks: This work was supported by an Australian Government Research Training Program (RTP) Scholarship. Thanks: This is a preprint of a paper accepted for presentation at ITW 2025. Abigail Gentle Abstract Local differential privacy represents the gold standard for preserving the privacy of data before it leaves the device, and distribution estimation under this model has been well studied. Recently, protocols built upon balanced incomplete block designs were shown to achieve optimal error for this problem. However, it remained unknown whether other constructions could also be optimal. We resolve this question by proving that any protocol achieving optimal error must correspond to some balanced incomplete block design. This result, combined with prior work, completely characterises the set of optimal protocols for this problem. As a consequence, the protocols that achieve optimal error and optimal communication are only those based on symmetrical balanced incomplete block designs. I Introduction Over the past decades, as data collection has grown exponentially, so too have privacy concerns. In response to this need differential privacy (DP) [ 1 , 2 ] has emerged as the gold standard for privacy-preserving data analysis, providing rigorous worst-case guarantees. As most of this data is collected in a distributed fashion, a natural point to apply privacy has become on the device, motivating massive advances in the field of local differential privacy (LDP) over the past years. Definition 1 (Local differential privacy [ 3 ] ) . For \varepsilon>0 , a randomised algorithm Q provides \varepsilon -local differential privacy if for all i,j\in\mathcal{X} \max_{y\in\mathcal{Y}}\frac{\Pr[Q(i)=y]}{\Pr[Q(j)=y]}\leq e^{\varepsilon}. (1) In other words, the probability of seeing any specific output y does not vary much between any two inputs i and j . We consider private distribution estimation over discrete domains. Let \mu be a discrete distribution over the domain \mathcal{X}\triangleq[v]\triangleq\{1,\dots,v\} , and let X\triangleq\{x_{1},\dots,x_{n}\} be n i.i.d.samples from \mu , each held by one of n (possibly distributed) users. We are interested in locally private protocols for distribution estimation , defined as follows. Definition 2 (LDP distribution estimation) . An \varepsilon -LDP protocol for distribution estimation comprises a local randomiser Q\colon\mathcal{X}\to\mathcal{Y} that satisfies Definition 1 and a “debiasing” function \mathcal{D}\colon\mathcal{Y}^{n}\to\mathbb{R}^{v} that converts private outputs into an estimate of the true distribution. The output space \mathcal{Y}\triangleq[b]\triangleq\{1,\dots,b\} need not be the same size as that of \mathcal{X} , and is frequently much larger [ 4 , 5 , 6 , 7 ] . The communication complexity of a protocol is the number of bits a user must send to the server after applying the local randomiser. It is apparent that this is at most \lceil\log_{2}(b)\rceil bits. As Q amounts to a procedure mapping inputs onto probability distributions, we can represent it by its underlying transition probability matrix (TPM) where Q_{ij}=\Pr[Y=i\mid X=j] . We abuse notation slightly, and allow Q to refer to the local randomiser and the TPM interchangeably. The problem now becomes learning the true probabilities of \mu_{i} given n samples over the induced distribution \displaystyle P \displaystyle=Q\mu. (2) We measure the utility , or accuracy , of a protocol by the expected error of the debiased estimate. In this work we will consider the expected \ell_{2}^{2} risk, \mathbb{E}\left[\ell_{2}^{2}(\hat{\mu},\mu)\right]=\mathbb{E}\left[\left\lVert\hat{\mu}-\mu\right\rVert_{2}^{2}\right] (3) where the expectation is taken over the input distribution and the local randomiser. Protocols that share a common source of randomness with the server are called “public-coin”, and can reduce communication overhead and increase accuracy [ 8 , 9 ] . We here consider only “private-coin” protocols, where there is no coordination between the server and the users. If all users implement the same local randomiser the protocol is called symmetric . Symmetric protocols are the only type considered in this work. Recent work has demonstrated that a certain family of protocols based on balanced incomplete block designs (as per Definition 3 ) achieve minimax optimality (as per Lemma 1 ) [ 7 ] ; however, it remained unknown whether other constructions could also be optimal. In Theorem 2 we resolve this by proving the converse: any locally private protocol for distribution estimation that achieves minimax optimality must have a transition probability matrix derived from a balanced incomplete block design. This implies that the family of block-design randomised response protocols in [ 7 ] exactly characterises all minimax optimal protocols. Balanced incomplete block designs, otherwise known as block designs, or (b,v,r,k,\lambda) -configurations are well-studied combinatorial objects, whose connection to statistics and experiment design are well known [ 10 , 11 ] . Historically, these objects were first considered in the context of randomised response procedures [ 12 , 13 ] . They have since been used implicitly to construct optimal LDP protocols for distribution estimation in the works of [ 14 , 15 ] . This connection was made explicit in [ 7 ] . To aid our discussion of these objects, we first introduce their basic properties. Definition 3 ( [ 11 , Chapter 8] ) . A balanced incomplete block design (BIBD), or a (b,v,r,k,\lambda) -configuration is a generalisation of finite projective planes. Let \mathcal{X} be a set of v elements (a v -set) and let \mathcal{B}_{1},\mathcal{B}_{2},\dots,\mathcal{B}_{b} be b distinct subsets (blocks) of \mathcal{X} . These subsets form a balanced incomplete block design provided that: 1. Each block \mathcal{B}_{i} has \lvert\mathcal{B}_{i}\rvert=k (call it a k -subset of \mathcal{X} ), 2. each 2-subset of \mathcal{X} is a subset of exactly \lambda of the sets \mathcal{B}_{1},\mathcal{B}_{2},\dots\mathcal{B}_{b} , and 3. the integers v , k , and \lambda satisfy 0<\lambda and k<v-1 . These conditions imply that each element of \mathcal{X} is contained in exactly r blocks. Our use of the letters v , b , and r reflect their origin in experiment design, where we have varieties assigned to blocks , and each variety is replicated r times 1 1 1 Typically it is required that \lambda>0 to exclude trivial designs, however we do not make this distinction here. . These constraints ensure that \displaystyle r(k-1) \displaystyle=\lambda(v-1) (4) \displaystyle bk \displaystyle=vr (5) Now let A be the incidence matrix of this configuration. That is, A is a zero-one matrix with A_{ij}=1 if j\in\mathcal{B}_{i} . The properties above imply that \displaystyle AJ \displaystyle=kJ^{\prime} (6) \displaystyle A^{\prime}A \displaystyle=(r-\lambda)I+\lambda J, (7) A^{\prime} denotes the transpose of A , J is the all-ones matrix of order v , J^{\prime} is the all-ones matrix of size b\times v , and I is the identity matrix of order v . Conversely, if A satisfies these properties, then it is the incidence matrix of a BIBD. If b=v and r=k , we call it a symmetrical balanced incomplete block design (SBIBD), or a (v,k,\lambda) -configuration. Optimal protocols for locally private distribution estimation are those that achieve the smallest error over all possible input distributions. We formalise this with the standard definition of minimax optimality. Definition 4 (Minimax optimality) . A protocol (Q,L) is minimax optimal for privacy level \varepsilon , and for risk function R , if it achieves the minimax risk: \sup_{\mu\in\Delta_{v}}R(Q,L;\mu)=\inf_{Q^{\prime}\in\mathcal{C}}\inf_{L^{\prime}}\sup_{\mu\in\Delta_{v}}R(Q^{\prime},L^{\prime};\mu) (8) where \mathcal{C} is the set of all \varepsilon -LDP local randomisers. In this work R is the expected \ell_{2}^{2} error. Our primary focus are protocols that are minimax, or “exactly,” optimal with respect to constant factors. This is