Abowd 2022 - The TopDown Algorithm and Privacy Accounting Proof

Summary

TDA has a measurement phase (noisy discrete-Gaussian measurements of key queries at every geographic level) and an estimation phase (sequential top-down constrained non-negative least squares plus controlled rounding, each level conditioned on the fixed estimate above). Total privacy loss is the sum of the per-level budgets. Theorem 2 (Appendix B): with noise variances ${\sigma }_{ijkl}^2={\psi }^2/(c_{ij}{d}_{ijk})$ and budget shares $c_{ij},d_{ijk}$ satisfying the stated sum constraints, TDA is $\rho$-zCDP with $\rho =1/{\psi }^2$.

Overview

The motivation is to exploit the tree-like geographic hierarchy to get estimates more precise than estimating block-level vectors independently and aggregating (the block-by-block baseline in Abowd 2022 - Geography Spines, Computing Environment and Block-by-Block Baseline), in a scalable manner.

Main Content

Table 1: the TopDown Algorithm

Measurement phase.

1. For each level $i\in \{\text{US, state, county, tract, block group, block}\}$: (a) determine the privacy-loss budget for level $i$; (b) take DP noisy measurements ${\tilde{M}}_{\gamma }$ for all nodes $\gamma$ in level $i$.

Estimation phase.

1. For the US root ${\gamma }_0$, estimate $x_{{\gamma }_0}$ by (a) a non-negative solution ${\tilde{x}}_{{\gamma }_0}$ from the DP measurements ${\tilde{M}}_{{\gamma }_0}$, invariants and edit constraints at the US level; (b) a non-negative integer solution ${\hat{x}}_{{\gamma }_0}$ from ${\tilde{x}}_{{\gamma }_0}$ by controlled rounding.
2. For each level $i\in \{\text{state, county, tract, block group, block}\}$ let $P_i$ be the set of distinct parents among its nodes. For each parent $\gamma \in P_i$ estimate the joint contingency vector $x_{\text{children}(\gamma )}$ by (a) a non-negative solution ${\tilde{x}}_{\text{children}(\gamma )}$ from ${\tilde{M}}_{\text{children}(\gamma )}$, invariants, edit constraints and aggregate constraints enforcing that the children sum to ${\hat{x}}_{\gamma }$; (b) a non-negative integer solution ${\hat{x}}_{\text{children}(\gamma )}$ by controlled rounding.

Why two phases. In the measurement phase, queries at different levels involve the same individuals, so the total privacy loss is the sum of losses across levels; the distribution of the global budget across levels and queries is a design choice. The estimation phase is pure post-processing and costs no privacy. In each step the already-estimated higher level is held fixed and becomes an extra constraint on the next subproblem. Two-step solving (continuous least squares, then rounding) is needed because the integer program at full size is intractable. Sequential details are in Abowd 2022 - Least Squares and Rounder Estimators.

Privacy accounting (Appendix B)

Convert noise variances to $\rho$: let $q_{ijkl}$ be the univariate query for geographic level $i$, node $j$ within the level, marginal query set $k$ within the node, and cell $l$ of that marginal. The query strategy has two parts: which queries are asked and which budget each gets. Early versions were symmetric over levels and nodes; the current strategy lets the set of queries differ by level, but requires that the same queries are asked for every node within a level.

Relative precision of a query is $c_{ij}\times d_{ijk}$ with $c_{ij}\in (0,1]$ the $\rho$ proportion for node $j$ in level $i$ and $d_{ijk}\in (0,1]$ the proportion for the $k$-th query at that node. The goal is a global scale $\psi$ such that discrete Gaussian noise with variance

$${\sigma }_{ijkl}^2=\frac{{\psi }^2}{c_{ij}{d}_{ijk}}$$

gives $\rho$-zCDP. Structure requirements: (R1) for all $i,j$: ${\sum }_{k=1}^{K_{ij}}{d}_{ijk}=1$ (relative split of precision across queries sums to 1); (R2) for every block $j$, summing $c_{ij}$ over the directed path $P(1,Ij)$ from the root (US) down to block $j$ gives 1.

Theorem 2 (TDA satisfies zCDP)

The set of queries $\{q_{ijkl}\}$ processed by the discrete Gaussian mechanism with parameters ${\sigma }_{ijkl}^2={\psi }^2/(c_{ij}{d}_{ijk})$, where (1) all queries are marginals, (2) $c_{ij}\ge 0$, $d_{ijk}\ge 0$, (3) ${\sum }_k{d}_{ijk}=1$ for all $i,j$, (4) ${\sum }_{ij\in P(1,Ij)}{c}_{ij}=1$ for all blocks $j$, satisfies $\rho$-zCDP with $\rho =1/{\psi }^2$.

(Functionally, if $c_{ij}$ or $d_{ijk}$ is 0 the query is not asked.)

Proof sketch. By Theorem 1 it suffices to show $\frac{1}{{\psi }^2}{\sum }_i{\sum }_j{\sum }_k{\sum }_l{c}_{ij}{d}_{ijk}(q_{ijkl}(x)-q_{ijkl}(x^{\prime }){)}^2\le 2\rho$ for neighbors $x\sim x^{\prime }$ (bounded: one record changes).

• Case 1: the changed record keeps its block (so the same node is affected at every level, say $j_i^{\ast }$ at level $i$). Only those nodes contribute; since queries are marginals, at most two cells differ in each marginal group (one down by 1, one up by 1), giving $\frac{1}{{\psi }^2}{\sum }_i{c}_{i{j}_i^{\ast }}{\sum }_k{d}_{i{j}_i^{\ast }k}(1^2+(-1{)}^2)=\frac{2}{{\psi }^2}{\sum }_i{c}_{i{j}_i^{\ast }}=\frac{2}{{\psi }^2}$ using (3) and (4).
• Case 2: the record changes block. Let $j_i^{\ast },j_i^{\ast \ast }$ be the nodes at level $i$ before/after. Because the geography is a tree, there is a level $S$ such that the nodes coincide for all $i\le S$ (including the US). For $i\le S$ the cells change as in Case 1, contributing $\frac{2}{{\psi }^2}{\sum }_{i\le S}{c}_{i{j}_i^{\ast }}$. For $i>S$ the affected nodes differ, and in each one marginal cell changes by exactly $+1$ or $-1$ (contributing $1^2$ each): $\frac{1}{{\psi }^2}[{\sum }_{i>S}{c}_{i{j}_i^{\ast }}+{\sum }_{i>S}{c}_{i{j}_i^{\ast \ast }}]$. Adding, the total is $\frac{1}{{\psi }^2}[{\sum }_{\text{all }i}{c}_{i{j}_i^{\ast }}+{\sum }_{\text{all }i}{c}_{i{j}_i^{\ast \ast }}]=\frac{2}{{\psi }^2}$ by (4) applied to both paths.

In both cases the bound is $2/{\psi }^2=2\rho$, so $\rho =1/{\psi }^2$. (The arXiv text of the Case 2 derivation is truncated at the end of the appendix; the final combination above is this note’s completion by the same argument and the statement of Theorem 2.)

Consequences for design

Because the allocation $\{c_{ij}\}$ sums to 1 along every root-to-block path, the global $\rho$ is independent of the number of nodes at a level: nodes at the same level are disjoint, so parallel composition applies across them, while sequential composition applies along the path. This is why the ”$\rho$ proportions” in Tables 3 and 6 add to one across levels for each of persons and housing units.

Examples

Budget bookkeeping for the April 2021 person allocation

Setup: person $\rho$ proportions by level (US, state, county, tract, CBG, block) $=(51,153,78,51,172,519)/1024$, global person budget $\rho =1.05$. Solution: the proportions sum to $1024/1024=1$ (R2), so the total is $\rho =1.05$ regardless of how many nodes there are. Level budgets: US $0.0523$, state $0.157$, county $0.080$, tract $0.052$, CBG $0.176$, block $0.532$. Within the block level, the DETAILED query gets $989/1024$ of that. Interpretation: half of the person budget sits on blocks (location protection and block-level accuracy), as the paper states.

import numpy as np
 
# Table 3 (April 2021) and Table 6 (production): person and housing-unit rho proportions by level
levels = ["US", "state", "county", "tract", "CBG", "block"]
person_apr = np.array([51, 153, 78, 51, 172, 519]) / 1024
housing_apr = np.array([1, 1, 18, 75, 906, 23]) / 1024
person_prod = np.array([104, 1440, 447, 687, 1256, 165]) / 4099
housing_prod = np.array([1/205, 1/205, 7/82, 364/1025, 1759/4100, 99/820])
for name, v in (("person Apr21", person_apr), ("housing Apr21", housing_apr),
                ("person prod", person_prod), ("housing prod", housing_prod)):
    print(name, v.sum())                      # each ~1.0 (requirement R2 at the level scale)
 
rho_person = 2.56
print(dict(zip(levels, np.round(rho_person * person_prod, 4))))
# noise variance for a query: sigma^2 = 1 / (rho_total * c * d)
c_county, d_total = 447/4099, 3126/4097
print(1 / (rho_person * c_county * d_total))  # ~4.7

Connections

• The discrete Gaussian and the $L_2$-sensitivity $\sqrt{2}$ premise: Abowd 2022 - Discrete Gaussian, Queries and the Optimization Problem.
• Parallel vs sequential composition is the zCDP version of RDP composition: Mironov 2017 - RDP Properties and Composition; GDP composition adds in quadrature: Dong Roth Su 2022 - Composition Theorem and Central Limit Theorems (for GDP, $\mu =\sqrt{2\rho }$ and $\rho$‘s add).
• Hierarchical estimation with inverse-variance weights: Hierarchical Forecast Reconciliation (MinT).

See Also

• Abowd 2022 - 2020 Census TopDown Algorithm - Overview
• Abowd 2022 - Privacy-Loss Budget Allocation and Tuning