Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

Technical Summary: Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

Problem Formulation
The paper addresses the problem of private discrete distribution estimation under the Local Differential Privacy (LDP) framework. In this setting, $n$ clients observe data points $X_i$ drawn from an unknown distribution $P$ over a domain of size $v$. Each client applies a privacy mechanism $Q$ to generate a privatized output $Y_i$ satisfying $\epsilon$-LDP before sending it to a central server. The server then constructs an estimator $\hat{P}_n$ to recover $P$. The objective is to minimize the worst-case risk (estimation error) under a specific loss function (primarily $\ell_u^u$ for $1 \le u \le 2$) while simultaneously minimizing the communication cost, defined as the size of the output alphabet $b = |\mathcal{Y}|$.

While the Subset Selection (SS) scheme is known to achieve the exactly optimal privacy-utility trade-off for all $(v, \epsilon)$, it suffers from prohibitively high communication costs (exponential in $v$). Conversely, communication-efficient schemes like Hadamard Response (HR) and Projective Geometry Response (PGR) often achieve only order-optimal or near-optimal performance, with performance gaps becoming significant in medium privacy regimes. The paper seeks to bridge this gap by finding schemes that are both exactly optimal (or near-optimal) and communication-efficient.

Methodology
The authors propose a new class of LDP schemes based on combinatorial block designs and a broader class called Regular and Pairwise-Balanced Designs (RPBD).

1. Block Design Schemes:

   • The mechanism is constructed using an incidence structure $(X, Y, I)$ where $X$ is the input domain and $Y$ is the output domain.
   • The structure is defined by parameters $(v, b, r, k, \lambda)$, representing input size, output size, regularity, uniformity, and pairwise balance, respectively.
   • The mechanism outputs an element $y \in I_x$ with probability proportional to $e^\epsilon$ and an element in $Y \setminus I_x$ otherwise.
   • A canonical unbiased estimator is derived based on the counts of outputs falling into specific sets.
   • Key Insight: The authors establish that for a fixed input size $v$ and privacy budget $\epsilon$, the risk of a block design scheme depends only on the parameter $k$ (the size of the intersection between input and output sets), not on $b$, $r$, or $\lambda$. Specifically, two block design schemes with the same $k$ are "marginally equivalent" and yield identical risks for decomposable loss functions.

2. Optimality Conditions:

   • Leveraging the known exact optimality of the SS scheme, the paper proves that any block design scheme with a parameter $k \in K^*_{v,\epsilon}$ (the set of integers minimizing the risk function) is also exactly optimal.
   • The paper characterizes $K^*_{v,\epsilon}$ precisely, showing that a scheme is exactly optimal if $k$ satisfies specific bounds related to $\epsilon$ and $v$.

3. Communication Efficiency:

   • Fisher's inequality dictates that for any unbiased or consistent scheme, $b \ge v$.
   • The authors focus on symmetric block designs where $b = v$, achieving the theoretical minimum communication cost for unbiased schemes.
   • When a symmetric block design with the optimal $k$ does not exist for a given $(v, \epsilon)$, the paper utilizes derived and residual block designs to construct non-symmetric schemes that remain exactly optimal or near-optimal with low $b$.

4. RPBD Schemes:

   • To address the "sparse existence" of block designs for arbitrary parameters, the authors relax the uniformity constraint, proposing Regular and Pairwise-Balanced Designs (RPBD).
   • RPBD schemes drop the requirement that $|I_y| = k$ for all $y$, retaining only regularity ($r$) and pairwise balance ($\lambda$).
   • The authors show that RPBD schemes with a ratio $[b:r:\lambda]$ similar to that of the optimal SS scheme achieve near-optimal risk. These can be constructed by truncating existing symmetric block designs.

Key Results

• Exact Optimality with Low Cost: The paper identifies numerous new LDP schemes that achieve the exactly optimal privacy-utility trade-off (matching the lower bound $M_{v,u,\epsilon}$) with the minimum possible communication cost ($b=v$) for a wider range of $(v, \epsilon)$ pairs than previously known.
• Unification: The framework unifies existing schemes (Randomized Response, Subset Selection, Hadamard Response, Projective Geometry Response) under the single umbrella of block designs.
• Near-Optimality via Truncation: For cases where exact optimal block designs do not exist, the paper demonstrates that truncating symmetric block designs to form RPBD schemes yields near-optimal performance with significantly lower communication costs than previous state-of-the-art methods (e.g., PGR).
  • Example: For $v=100, \epsilon=1$, a truncated RPBD scheme based on a quartic residue difference set achieves lower estimation error and requires ~6.66 bits per client, compared to ~8.41 bits for a truncated PGR scheme.
• Hadamard Conjecture Connection: The paper links the existence of exactly optimal schemes with minimum communication cost in the high privacy regime ($\epsilon \approx 0$) to the Hadamard conjecture. If the conjecture holds, exactly optimal schemes with $b=v$ (or $b=2v$) exist for all $v$.

Significance
The paper claims to provide a novel, unified framework for discovering LDP schemes that overcome the traditional trade-off between exact optimality and communication efficiency. By shifting the focus from specific ad-hoc constructions to the combinatorial properties of block designs, the authors demonstrate that:

1. Many previously proposed schemes (HR, PGR) are actually exactly optimal for specific regimes, a fact not previously established.
2. New schemes can be systematically generated to achieve exact optimality with minimal communication costs for a broader set of parameters.
3. The relaxation to RPBD schemes allows for near-optimal performance with low communication costs in scenarios where exact optimal block designs are mathematically impossible to construct.

The work emphasizes that analyzing the exact privacy-utility trade-off (including constant factors) is crucial for practical deployment, and the proposed block design approach offers a rigorous path to achieving this without sacrificing communication efficiency.