Optimal Allocation of Privacy Budget on Hierarchical Data Release
Joonhyuk Ko, Juba Ziani, Ferdinando Fioretto · 2025
Read Optimal Allocation of Privacy Budget on Hierarchical Data Release by Joonhyuk Ko, Juba Ziani, Ferdinando Fioretto (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-2505-10871.txt.
Introduction
Joonhyuk Ko and co-authors divide a privacy budget wisely in a 2025 computer science paper. Census-style data comes in hierarchies, nation down to household, and differential privacy protects individuals by adding noise, but the noise budget is finite: overspend at one level and another starves.
The authors cast the division as a constrained optimization, maximizing the released data's usefulness under a total privacy cap while respecting how detail and protection trade off at each level. Theory guides the split, and experiments on real hierarchical datasets show clear gains in utility and downstream task accuracy over naive allocations.
Catalog record
| CREATOR | Joonhyuk Ko, Juba Ziani, Ferdinando Fioretto |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-10871
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimal Allocation of Privacy Budget on Hierarchical Data Release Joonhyuk Ko, Juba Ziani, Ferdinando Fioretto 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. 1 Introduction Hierarchical data structures are ubiquitous, appearing in domains such as geographical information systems, organizational charts, biological taxonomies, and product catalogs. While the analysis of such data impacts society and the economy as it touches disciplines from scientific discovery to policy-making, it is often regulated by privacy laws or ethical considerations. For instance, the U.S. Census Bureau’s data is a prime example of hierarchical data, where population statistics are organized at various levels, such as national, state, and county. This data is crucial for a wide range of applications, including resource allocation, migration studies, and public health decisions. Its release is also governed by strict privacy regulations, including the Title 13 of the U.S. Code, which prohibits the disclosure of personally identifiable information. As a result, privacy-preserving techniques have been developed to ensure that sensitive information remains confidential while still allowing for meaningful analysis. Among these, Differential Privacy (DP) [ 1 ] has emerged as the gold standard, primarily due to its strong, quantifiable guarantees against re-identification and inference attacks. However, hierarchical data presents unique challenges for differential privacy, as its privacy budget must be allocated across different levels of the hierarchy. For instance, one might need to release aggregate statistics at a coarse geographical level (e.g., state) and more fine-grained statistics at a lower level (e.g., county or city). A naive or uniform allocation of the privacy budget across these levels can lead to suboptimal outcomes: either too much noise is added to fine-grained data, destroying its utility, or coarse-grained data is overly protected at the expense of detail elsewhere. This necessitates a principled approach to privacy budget allocation that explicitly considers the structure of the data and the utility requirements at different granularities. This observation raises a fundamental question: How can we optimally allocate a given privacy budget across a hierarchical data structure to maximize the utility of the released information? The answer to this question is not straightforward, as it involves balancing the trade-off between privacy and utility across multiple levels of the hierarchy. As the paper will show, commonly adopted heuristic approaches often achieve suboptimal results, leading to inaccurate downstream analyses. This paper precisely addresses this problem, and provides the following contributions: \bm{C}_{1} It defines and characterizes the problem of optimal privacy budget allocation for hierarchical data release under differential privacy. This includes defining appropriate utility metrics that capture the usefulness of data at different levels of the hierarchy. \bm{C}_{2} It provides an analysis of the properties of the optimal allocation strategy (as detailed in Section 3 ), in particular the relationship between bias and variance of the released data, and how these are affected by the privacy budget allocation. \bm{C}_{3} Crucially, the analysis shows that the optimal allocation strategy is not necessarily uniform across levels, and utility can be significantly improved by accounting for the hierarchy’s structure. To address this, it proposes an optimization-based approach that minimizes an analytical expression for mean squared error, combining bias and variance introduced by differential privacy under non-negativity post-processing, commonly used in histogram and contingency table releases. Importantly, by minimizing this objective, the method improves the utility of the released data even after the post-processing, which is known to distort bias and variance [ 2 ] . \bm{C}_{4} Finally, the paper demonstrates the practical utility of the proposed method through extensive experiments on real-world datasets derived from the U.S. Census. The results show a substantial reduction of both bias and variance compared to uniform allocation under the same privacy budget. Furthermore, motivated by U.S. Census budget allocation, the framework is extended to a downstream resource allocation task using privatized data. This extension examines how different classes of preference functions influence bias and variance, with results consistently showing higher utility for the optimal allocation strategy over uniform allocation. The remainder of this paper is organized as follows. Section 2 introduces essential preliminaries on differential privacy and hierarchical data, and sets up the problem. Section 3 details our proposed allocation methodology. Section 4 presents the experimental results, focusing on Wyoming as a running example, with additional state experiments in Appendix D . Section 5 explores the impact on downstream tasks. Finally, Section 6 concludes the paper and outlines future research directions. Figure 1: A hierarchical structure of geographic regions, where blocks are nested within tracts, and tracts within the state of Virginia. Level Region Population Level 3 Block 1 (100) 120 Level 3 Block 2 (100) 80 Level 3 Block 3 (100) 100 Level 2 Tract 100 300 Level 3 Block 1 (200) 90 Level 3 Block 2 (200) 60 Level 2 Tract 200 150 Level 1 VA 450 Table 1: Population counts corresponding to each region in the hierarchy shown in Figure 1 . Related Work. Since the adoption of the U.S. Census Bureau’s TopDown Algorithm (TDA) [ 3 ] , there has been growing interest in exploring hierarchical data release under differential privacy. This has motivated theoretical and practical approaches for allocating privacy budgets across hierarchical levels [ 4 , 5 , 6 , 7 ] . Accurately privatizing hierarchical data releases, such as those in the U.S. Census, is crucial, as it directly impacts federal resource allocation and has significant implications for fairness in downstream decisions [ 8 , 9 , 10 ] . Beyond population statistics, hierarchical data plays a key role in other domains. Liu et al [ 11 ] explored generating private synthetic hierarchical data, while hierarchical structures have also been used in federated learning to enhance privacy and scalability [ 12 ] . Fioretto et al. [ 5 ] proposed an optimization-based method for post-processing privatized hierarchical data to ensure consistency and improve utility. Cohen et al. [ 6 ] examined how privacy budget allocation affects redistricting accuracy in the Census TopDown algorithm, finding that bottom-heavy allocations improve accuracy for small geographic units. Similarly, Dawson et al. [ 13 ] proposed a greedy iterative approach using noisy priors and demonstrated that unequal budget allocations can achieve higher accuracy than uniform splits. However, there remains a gap in understanding how to optimally allocate privacy budgets across different levels of the hierarchy, especially when common post-processing alters the bias and variance of differentially private estimates. 2 Preliminaries and Problem Setting 2.1 Hierarchical