Source-linked AI summary
Geographic Spines in the 2020 Census Disclosure Avoidance System
Ryan Cumings-Menon, John M. Abowd, Robert Ashmead, Daniel Kifer, Philip Leclerc, Jeffrey Ocker, Michael Ratcliffe, Pavel Zhuravlev
TL;DR
The paper examines how the internal geographic spine used for noisy DAS measurements affects accuracy, given that important areas may be far from the conventional spine. It describes AIAN and optimized alternatives and their construction, then reports tradeoffs across geographic levels, including the Census Bureau’s judgment that optimization’s accuracy gains outweighed lower accuracy for conventional block groups.
Problem
The conventional spine can leave AIAN tribal areas and other important off-spine areas far from its geounits, and distant areas can have higher query-estimate mean squared error.
Source: §1.1 · p. 2Method
The paper describes AIAN and optimized internal spines, including splitting geounits into AIAN and non-AIAN portions and optimizing geolevels and redundant geounits.
Source: §1.1 · pp. 3–4Results
Optimized spines improve accuracy at remaining geolevels relative to the AIAN spine and, in most cases, the conventional spine, while conventional block groups become much less accurate.
Source: §7 · pp. 23–24Takeaways & Limitations
Redistricting tuning experiments found the accuracy improvements from spine optimization outweighed the cost of lower accuracy in conventional block groups.
Source: §7 · pp. 23–24The DAS privacy guarantees do not protect state total populations or the locations of group-quarter types.
Source: §2.1 · p. 5
Abstract
from arXiv · showhide
The 2020 Census Disclosure Avoidance System (DAS) is a formally private mechanism that first adds independent noise to cross tabulations for a set of pre-specified hierarchical geographic units, which is known as the geographic spine. After post-processing these noisy measurements, DAS outputs a formally private database with fields indicating location in the standard census geographic spine, which is defined by the United States as a whole, states, counties, census tracts, block groups, and census blocks. This paper describes how the geographic spine used internally within DAS to define the initial noisy measurements impacts accuracy of the output database. Specifically, tabulations for geographic areas tend to be most accurate for geographic areas that both 1) can be derived by aggregating together geographic units above the block geographic level of the internal spine, and 2) are closer to the geographic units of the internal spine. After describing the accuracy tradeoffs relevant to the choice of internal DAS geographic spine, we provide the settings used to define the 2020 Census production DAS runs.
1. Introduction
The DAS builds noisy measurements over a hierarchical geographic spine and post-processes them into consistent estimates. This introduction explains why alternative internal spines were explored and previews their construction and evaluation.
1. Introduction
- The conventional spine places AIAN tribal areas and other legal, political, or census-designated areas far from its geounits, and distant areas can have higher query-estimate mean squared error.The paper identifies minor civil divisions and incorporated places as examples of off-spine entities.Source: §1.1 · p. 2
1.1. Contributions.
- The paper describes alternative spines, their construction methods, production settings, and accuracy comparisons across conventional, AIAN, and optimized spines.These alternatives are intended to address shortcomings of the conventional internal spine.Source: §1.1 · pp. 3–4
- An AIAN spine replaces each state-level and lower geounit with portions inside and outside the aggregated AIAN-areas off-spine entity, when both portions exist.This creates separate AIAN and non-AIAN branches below the state level.Source: §1.1 · p. 3
- Spine optimization redefines selected geolevels to bring target off-spine entities closer, then bypasses redundant geounits to reduce final-histogram variance.For a parent with one child, bypassing removes the parent and reduces variance in the child’s noisy measurements.Source: §1.1 · pp. 3–4
1.2. Paper Outline.
- The paper outlines prior differential-privacy results, spine representations and privacy guarantees, optimization methods, production configurations, and accuracy comparisons.Its final comparison concerns redistricting-person DAS executions using conventional, AIAN, or optimized internal spines.Source: §1.2 · p. 4
1.3. Notation.
- The notation section specifies matrix and vector conventions and distinguishes discrete Gaussian and discrete Laplace distributions from their continuous counterparts.It also defines notation for independently distributed vectors using these distributions.Source: §1.3 · pp. 4–5
2. Differential Privacy
The section defines the DAS privacy framework and develops accounting tools for its linear queries, culminating in matrix-mechanism estimation of workload answers.
2.1. Privacy Definitions.
- DAS privacy guarantees bound output-distribution differences for neighboring databases, with neighbors constrained by same-state changes and group-quarter, imputation, and edit invariants.The DAS’s guarantees do not protect state total populations or group-quarter locations.Source: §2.1 · pp. 5–6
2.2. Privacy-Loss Accounting Results.
- Privacy accounting establishes each query mechanism’s DP or zCDP guarantee, then combines guarantees through sequential and parallel composition.Parallel composition applies to mechanisms depending on disjoint input subsets.Source: §2.2 · p. 6
2.3. Linear Queries and Marginal Query Groups.
- DAS queries are linear maps, query groups stack queries for the same marginal, and privacy-loss budget proportions allocate budget across queries.A query answer is the inner product of a query vector and histogram cell counts.Source: §2.2 · p. 7, §2.3 · p. 7
2.4. The Matrix Mechanism.
- Matrix mechanisms use noisy strategy queries to estimate histogram counts and release workload answers; prior work uses output variance to assess expected squared error.The variance matrix is W(eA⊤eA)^−1W⊤, whose trace gives expected sum of squared errors.Source: §2.4 · p. 9
3. Representing Linear Queries on the Spine
The section represents the geographic spine and its per-geounit queries as matrices, so query answers at each level can be expressed from block-level counts. It also specifies how query-group privacy-budget proportions enter the mechanism and states privacy guarantees for conventional and AIAN spines.
3. Representing Linear Queries on the Spine
- B stacks query-group matrices for a geounit; the notation generalizes from a shared strategy matrix to distinct B[l] matrices by geolevel.The section represents geounits as (l, u) and orders blocks so those sharing higher-level geography are adjacent.Source: §3 · pp. 9–10
- A encodes adjacency among spine geounits, and A[l]⊗B expresses level-l query answers from block-level cell counts.Stacking the level matrices gives the matrix representation of the spine.Source: §3 · p. 9
- The workload W need not consist only of linear queries for a hierarchical set of geographic entities; the stated restriction is W ∈ R^(f×n_b[1,1]).By contrast, the strategy matrix S contains the spine-structured linear queries.Source: §3 · p. 10
- The global PLB share for query group i at geounit (l, u) is β_lα_i,l, and spine optimization can change geounit allocations without changing per-geounit workloads or query-group proportions.α_i,l denotes a query group's share of its geolevel PLB; conventional and AIAN spines use the unaltered initial strategy matrix.Source: §3 · pp. 10–12
- For conventional or AIAN spines, the theorem establishes ε-DP or ρ-zCDP for the mechanism and DAS under the stated dH(x, x′) = 2 neighbor definition.The guarantee depends on whether the pure-DP or zCDP framework and implementing mechanism are used.Source: §3 · pp. 11–12
4. Bringing Off-Spine Entities Closer to the Spine
The section presents two ways to bring target off-spine entities closer to the spine, with accuracy gains traded against accuracy at replaced input-spine levels. One approach defines geographic levels directly as intersections; another automates definitions by reducing off-spine entity distance, using a tractable heuristic when the general optimization is difficult.
4. Bringing Off-Spine Entities Closer to the Spine
- Bringing target OSEs closer to the spine can improve their accuracy but sacrifices accuracy at replaced input-spine levels; production settings replacing AIAN block groups with optimized block groups degraded census block-group accuracy.The two approaches alter one or more geographic levels to move them closer to the target OSEs.Source: §4 · p. 12
- The 2020 redistricting and DHC implementations defined new spine levels directly as intersections of OSEs and existing geounits, including tracts and AIAN areas.The redistricting production example defined each optimized block group as an intersection of selected OSEs and geounits.Source: §4 · pp. 12–13
- The alternative approach automates new geounit definitions to bring OSEs closer to the optimized spine, but was not used in the 2020 production DAS settings.It differs from directly defining new levels as intersections of OSEs.Source: §4 · p. 13
4.1. Automating the Choice of Alternative Geolevel Definitions.
- The automated approach uses a heuristic to reduce an objective based on OSED, the minimum number of geounits added or subtracted to derive an OSE; it generally reduces estimate variance, particularly with sufficiently high global PLB allocation per geolevel.When an OSE has the same geographic extent as a spine geounit, its OSED is one.Source: §4.1 · p. 13
- Because polynomial-time minimization appears difficult for potentially overlapping OSEs, the example uses a greedy, computationally tractable approach to reduce OSEDs by redefining block groups and tract groups.Optimized block groups combine blocks within a tract and the same OSE intersection; the algorithm iteratively tests sibling combinations against current OSEDs.Source: §4.1 · pp. 14–15
- The block-count bound for optimized block groups aims to keep tract and child fanout low, since high fanout can increase DAS runtime and appears to degrade accuracy.The bound uses √n plus a user-chosen fanout cutoff, where n is the number of blocks in the parent tract.Source: §4.1 · pp. 14–15
5. A Pareto Frontier of Geounit Definitions
The section gives decision rules for bypassing parent geounits to improve or preserve estimation accuracy under specified conditions. It also shows that spine optimization preserves the stated privacy guarantees for the supported mechanisms.
5. A Pareto Frontier of Geounit Definitions
- In the DAS, bypassing replaces a parent with new parent-level geounits and moves its PLB to the children; the analysis models this as reallocating the parent’s PLB to its children.Source: §5 · p. 16
- With equal per-level strategies and query PLB proportions, equal child PLB allocations, and the stated threshold, bypassing a parent decreases or preserves every diagonal of the WLS variance matrix.The threshold is that each child’s PLB proportion is at least (c − 1) times the parent’s proportion divided by 2.Source: §5 · pp. 16–17
- For Gaussian mechanisms, bypassing a parent with two or more children increases at least one variance diagonal, so the DAS rule bypasses only parents with one child.With one child, the variance diagonals remain unchanged under bypassing.Source: Remark 2 · p. 18
- A child without siblings contributes no noisy answer to the DAS output, so bypassing its parent can reduce the variance of the noisy answers used for that child’s estimates.Source: Remark 2 · p. 19
- Algorithm 3 processes from block groups upward to the US level so one pass leaves no remaining geounits to bypass.Source: Remark 2 · p. 19
5.1. The impact of Spine Optimization on the Privacy Guarantees of the DAS.
- For spines produced by the optimization routines, both the implementing mechanism and DAS retain ε-DP with Laplace noise or ρ-zCDP with Gaussian noise under the stated neighbor definition.Source: §5.1 · p. 19
6. Spine Settings Used for 2020 Census Production Executions
The 2020 production spines use different intermediate geographies and optimized block groups for redistricting and demographic-and-housing products. Their definitions reflect the universes and geographic entities used by each product.
6. Spine Settings Used for 2020 Census Production Executions
- The redistricting persons spine includes US, state, county, tract, optimized block group, and block levels, with an AIAN and non-AIAN branch from state downward.Optimized block groups group blocks within the same tract and AIAN, GQ, MCD, and place OSEs; bypassing then sets final PLB values.Source: §6 · p. 21
- The redistricting housing-unit spine is nearly identical to the persons spine, but does not use GQ OSEs to define optimized block groups because occupied GQs are outside its universe.Source: §6 · p. 21
- The demographic-and-housing executions use US, state, county, prim, tract subset group, tract subset, optimized block group, and block levels.Prims are the most granular geography used by PEP; tract subsets intersect a tract, a prim, and an AIAN OSE, while tract subset groups combine tract subsets.Source: §6 · pp. 21–22
- For demographic-and-housing optimized block groups, blocks are grouped within the same GQ OSE, tract subset, school-district OSE, and conventional-block-group OSE.Source: §6 · p. 22
7. Impact of Spine Optimization: Summary Metrics
The summary metrics compare total-population MAE across three internal-spine settings. The optimized spine improves accuracy for targeted off-spine entities and most conventional-spine levels, while conventional block groups become less accurate.
7. Impact of Spine Optimization: Summary Metrics
- For conventional-spine geographies, optimization makes block groups much less accurate but improves the remaining levels relative to the AIAN spine and, in most cases, the conventional spine.Table 2 reports total-population MAE values for standard-spine geographies below the county level.Source: Table 2 · p. 23, §7 · p. 23
- Optimized-spine MAEs are lower than both conventional- and AIAN-spine MAEs for every reported off-spine entity.Table 3 reports total-population MAE values for off-spine entities.Source: Table 3 · p. 23, §7 · p. 23
- Moving from the conventional to the AIAN spine yields a large accuracy improvement within AIAN areas, with only very small accuracy changes for conventional-spine geounits.The authors attribute the AIAN-area improvement to those areas being closer to the AIAN spine; conventional geounits can be composed of at most two AIAN-spine units.Source: §7 · pp. 22–23
- Census Bureau tuning experiments found the optimization’s accuracy gains outweighed the loss for conventional block groups, which are not legally or politically defined and do not correspond to functioning governmental units.Source: §7 · p. 24