Optimal Allocation of Privacy Budget on Hierarchical Data Release

Joonhyuk Ko, Juba Ziani, Ferdinando FiorettoarXiv 2025 · DOI · arXiv

Introduction

Releasing sensitive hierarchical data, such as national census counts, requires balancing data utility with individual privacy. Differential Privacy (DP) is the standard framework for this, adding noise scaled by a privacy budget ($\epsilon$). However, when data is organized hierarchically (e.g., State -> Tract -> Block), a major challenge arises: how should a fixed total budget be distributed across these levels?

Hierarchical structure of data release levels.

Standard approaches often use a uniform split, but this fails to account for the unique properties of hierarchical data. Higher levels contain large aggregates, while bottom levels consist of many small counts. Post-processing steps, such as enforcing non-negativity (setting negative noisy counts to zero), introduce significant bias and variance, particularly at the granular levels where counts are small.

Methodology

The authors propose a principled optimization framework to address this. They model the privacy budget allocation as a constrained convex optimization problem. Key components include:

  1. Analytical Error Modeling: Deriving closed-form expressions for Mean Squared Error (MSE) that incorporate the effects of non-negativity post-processing. This modeling shows that post-processing makes error behavior more complex than simple Laplace noise.
  2. Convexity Proof: Demonstrating that MSE is a strictly convex function of $\epsilon$, ensuring that a global optimum can be efficiently found by optimization algorithms.
  3. Optimization Objectives: Developing programs to either minimize total error for a fixed budget or minimize the budget required to meet a specific utility target.
  4. Weighting: Allowing curators to prioritize accuracy at specific levels of the hierarchy (e.g., prioritizing County-level accuracy over State-level).

Experimental Setup

The framework was evaluated using U.S. Census Bureau data, specifically the 2010 and 2020 Census Privacy-Protected Microdata Files (PPMF). Detailed experiments focused on states like Wyoming, New Mexico, and Delaware, involving hierarchies with tens of thousands of nodes. To remain DP-compliant, the authors suggest using previously released data (like the 2010 Census) as "prior" information to set the budget for current releases.

Key Insights: The "Bottom-Heavy" Rule

A central finding of the research is the "bottom-heavy" rule. To minimize total error, the optimal strategy is to allocate significantly more of the privacy budget to the lower, more granular levels of the hierarchy. This is because small population counts at the bottom suffer most from the positive bias of non-negativity constraints; a higher budget at these levels more effectively reduces this bias compared to the same budget increase at higher levels.

Results and Performance

The optimized allocation demonstrates substantial improvements over naive uniform splitting. In tests on the Wyoming dataset, the framework achieved a tenfold reduction in squared bias and a fourfold reduction in variance for the same total privacy budget.

Comparison of Bias^2 and Variance between optimal and uniform budget allocations.

Furthermore, the framework allows for precise budget setting to meet utility targets. For resource allocation tasks, such as distributing funds based on population, the optimal strategy significantly reduced misallocation errors across various policy preference functions (logarithmic, linear, and quadratic).

Limitations and Future Directions

While effective, the current approach has limitations. The current focus is on the Laplace mechanism, though Gaussian mechanisms are expected to behave similarly. Future work includes incorporating explicit fairness constraints to protect minority groups and exploring bottom-up consistency projections for cases where top-level data is extremely noisy. Additionally, ensuring that the optimization process itself does not leak information remains a key consideration for strict DP compliance.

Summary updated

Abstract

Releasing useful information from datasets with hierarchical structures while preserving individual privacy presents a significant challenge. Standard privacy-preserving mechanisms, and in particular Differential Privacy, often require careful allocation of a finite privacy budget across different levels and components of the hierarchy. Sub-optimal allocation can lead to either excessive noise, rendering the data useless, or to insufficient protections for sensitive information. This paper addresses the critical problem of optimal privacy budget allocation for hierarchical data release. It formulates this challenge as a constrained optimization problem, aiming to maximize data utility subject to a total privacy budget while considering the inherent trade-offs between data granularity and privacy loss. The proposed approach is supported by theoretical analysis and validated through comprehensive experiments on real hierarchical datasets. These experiments demonstrate that optimal privacy budget allocation significantly enhances the utility of the released data and improves the performance of downstream tasks.
BibTeX
@misc{ko2025optimal,
  author = {Joonhyuk Ko and Juba Ziani and Ferdinando Fioretto},
  title = {{Optimal Allocation of Privacy Budget on Hierarchical Data Release}},
  year = {2025},
  eprint = {2505.10871},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.10871},
}
Figure