Drift-Aware Privacy Budget Splits for Hierarchical Preference Statistics

Platforms often publish, or feed into their recommenders, counts of what people engage with, organized as a tree: department, then category, then product; or artist, then track. When those counts must be differentially private, which means adding calibrated random noise so that no single user's data can be inferred, the operator has to decide how much of a fixed privacy budget each level of the tree receives. The best existing answer comes from a single snapshot: give most of the budget to the finest, leaf level, where true counts are small and noise hurts most. Real preference data, though, is a stream that drifts. Leaf-level tastes churn from month to month, while coarse categories move slowly. This proposal argues that once releases are repeated over time, the right budget split depends on how fast each level drifts relative to its noise. The reason is that a slowly drifting level can be denoised for free by averaging across past releases, while a fast-drifting level cannot.

The core contribution is a per-period allocation rule and a matching estimator. The rule minimizes error in forecasting next period's tree, not error in reconstructing the current one. Its only inputs are drift rates estimated from previously published noisy releases, so the estimation costs no extra privacy. The question the work settles is whether this matters beyond what a simple temporal smoother already provides. If static allocation plus smoothing turns out to be as good, that is itself a useful negative result about the bottom-heavy rule in streaming deployments.

Core Claim

Two lines of work set up the question. On the privacy side, Optimal Allocation of Privacy Budget on Hierarchical Data Release treats budget splitting across a census hierarchy as a convex program. It accounts for the bias introduced when negative noisy counts are clamped to zero, and it proves a "bottom-heavy" rule. Optimizing Hierarchical Queries for the Attribution Reporting API chooses splits greedily from a previous month's noisy data and then makes children sum to parents with a linear-time best linear unbiased estimator. Both papers motivate this proposal and supply parts of its method. Both also assume that the quantity of interest is the current snapshot and that last period resembles this period.

On the drift side, Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift down-weights old preference pairs by a fixed exponential discount and observes that the right discount depends on an unknown drift magnitude. PISA shows empirically that long-run, coarse memory denoises volatile short-run behaviour. Neither of these papers involves privacy.

The claim joining them is concrete. Model each node value at level $l$ as a random walk with per-period innovation variance $q_l$, released with noise variance $\sigma_l^2 = c/\epsilon_l^2$, where $\epsilon_l$ is the level's budget and $c$ is a constant fixed by the mechanism and the per-user contribution bound. Under this model, a steady-state Kalman filter over the release history has a one-step-ahead forecast variance of

$$P_l(\epsilon_l) = \tfrac{1}{2}\left(q_l + \sqrt{q_l^2 + 4 q_l \sigma_l^2}\right),$$

which is the fixed point of the scalar filter recursion. The proposed allocation solves

$$\min_{\epsilon_1,\dots,\epsilon_L} \sum_{l} w_l\, n_l\, P_l(\epsilon_l) \quad \text{s.t.} \quad \sum_l \epsilon_l = \epsilon_{\text{period}},$$

where $n_l$ is the number of nodes at level $l$ and $w_l$ is a level weight chosen by the downstream use. Two limits show why this differs from snapshot allocation. When $q_l \ll \sigma_l^2$, the marginal value of budget scales like $\sqrt{q_l}/\sigma_l$, because past releases substitute for current budget. When $q_l \gg \sigma_l^2$, budget buys back noise one-for-one, but the forecast error is dominated by $q_l$ itself.

The bottom-heavy rule is recovered only in the stationary, single-release limit. The empirical prediction is that, when the objective is weighted by relative error, the forecast-optimal split moves budget toward levels whose drift-to-noise ratio is intermediate. On preference taxonomies, these are typically interior category levels rather than leaves.

The drift rates come at no privacy cost. Because the noise variance is known, differencing past releases gives

$$\hat q_l = \widehat{\mathrm{Var}}(y_t - y_{t-1}) - \sigma_{l,t}^2 - \sigma_{l,t-1}^2,$$

pooled across the nodes of a level and truncated at zero. This is pure post-processing of published outputs, so the allocation adapts to drift without spending budget to learn it. That is the key difference from the prior-based heuristic of Optimizing Hierarchical Queries for the Attribution Reporting API, which uses the previous noisy release as a stand-in for the current one.

Research Program

The system has three components.

The first is a release mechanism. It applies per-period Gaussian noise under zero-concentrated differential privacy, a variant whose privacy losses add simply across releases. Each user's contributions per period are clipped to a fixed number of interactions, so the sensitivity is known at every level.

The second is a joint estimator over tree and time. It runs a Kalman filter per node and then the two-pass tree projection of Optimizing Hierarchical Queries for the Attribution Reporting API, so that parent-child consistency and temporal pooling are both enforced. Non-negativity clamping is applied only after filtering. This step tests a secondary hypothesis: the truncation bias that drives the bottom-heavy rule in Optimal Allocation of Privacy Budget on Hierarchical Data Release largely disappears once leaves are temporally pooled, because the filtered estimates are farther from zero than raw noisy counts.

The third is the allocator. It re-solves the convex program each period using the current $\hat q_l$, and it begins with the bottom-heavy split until enough history accumulates. On the analysis side, we will characterize when the forecast-optimal split differs from the snapshot-optimal split in closed form for the random-walk model. We will also measure how far real taxonomies depart from that model, specifically whether innovation variance is roughly homogeneous within a level or needs to be estimated per subtree.

The privacy accounting is stated plainly. Over $T$ periods, a user who is active in every period accrues the composed zero-concentrated privacy loss of $T$ releases. We do not reset budgets. Continual Counting with Gradual Privacy Expiration warns that resetting yields linear privacy loss presented as if it were a fixed guarantee. Every method in the comparison receives the identical per-period and total budget, so the comparison concerns accuracy at equal privacy, not accounting.

Baselines

The naive reference is a uniform split, $\epsilon_l = \epsilon_{\text{period}}/L$, released fresh each period with the tree projection but without temporal filtering. Every hierarchical paper in the file treats this as the floor. Optimal Allocation of Privacy Budget on Hierarchical Data Release reports a tenfold reduction in squared bias and a fourfold reduction in variance over it on the Wyoming census hierarchy. We expect to beat it easily, and it calibrates the scale of all other gains.

The first strong competitor is the convex bottom-heavy allocation of Optimal Allocation of Privacy Budget on Hierarchical Data Release, computed once and held fixed. It is the strongest snapshot-optimal method and is the method our claim most directly contradicts.

The second strong competitor is prior-based greedy budgeting with tree projection from Optimizing Hierarchical Queries for the Attribution Reporting API, re-run each period on the previous period's noisy release. It is the strongest existing method that already adapts over time. Its reported result is a root mean squared relative error of approximately 0.17 on the Criteo Sponsored Search Conversion Log with a depth-5 tree at $\epsilon = 5$. We reproduce that setting first as a correctness check. Our method must at least match this number in the stationary single-snapshot case.

The decisive ablation keeps our estimator and replaces our allocator with each static split. Concretely, it is the bottom-heavy allocation followed by the same Kalman-plus-projection post-processing. This isolates the claim that allocation, not smoothing, carries the gain.

A second ablation replaces the Kalman filter with a fixed exponential discount over past releases, in the style of Right Now, Wrong Then. The discount is tuned on a held-out time prefix with the same tuning budget given to our allocator's single hyperparameter, the history length used for estimating drift.

Beating a competitor means lower next-period forecast error, measured as relative mean squared error weighted by node, with confidence intervals over twenty noise seeds that exclude zero. It also means equal or better recall of nodes whose true volume rises sharply.

Why not just…?

Why not just keep the bottom-heavy split and smooth the releases over time? This is the real threat, and the program is built around it. Smoothing is free post-processing, and if it already absorbs most of the drift benefit, the allocator is unnecessary. The model predicts the gap should be large only when per-level drift rates differ by an order of magnitude or more. The ablation above measures the gap directly across synthetic drift regimes and on the real datasets. If the gap is within noise on real taxonomies, we will report that the bottom-heavy rule survives streaming deployment when paired with a temporal filter. That would still be a new finding, since Optimal Allocation of Privacy Budget on Hierarchical Data Release analyzes only single releases.

Why not just re-run prior-based budgeting each period? Optimizing Hierarchical Queries for the Attribution Reporting API uses the previous noisy release as a proxy for the current counts. That allocates well for the snapshot but ignores two things: that past releases can be pooled, and that high-churn levels are hard to forecast however much budget they receive. Its weakness should appear at abrupt shifts, which we inject at known change points, mirroring the flipped-preference benchmarks of Right Now, Wrong Then. In that setting, a one-period-stale prior misallocates budget for at least one period after each shift.

Why not just use a sliding window or a fixed discount? A fixed discount needs a decay rate that depends on the unknown amount of drift, as Right Now, Wrong Then itself notes. A single window also applies the same memory to every level, whereas PISA shows that coarse long-run structure and fine short-run structure need different memories. The discount ablation tests whether level-specific memory from the Kalman gains matters beyond one tuned global rate.

Proposed Experiments

Each experiment answers one question.

The first asks whether the closed form predicts the optimum. We generate synthetic hierarchies with controlled per-level random-walk drift, plus injected change points, at depths 3 to 6. In this setting the true forecast-optimal split can be found by brute-force search over allocations and compared against the formula's split.

The second is a correctness check. We reproduce the stationary Criteo depth-5 setting against the 0.17 root mean squared relative error reported by Optimizing Hierarchical Queries for the Attribution Reporting API. Here we also use the Day level of that tree as the time axis, which gives a mildly drifting real stream.

The third asks whether the method helps on real preference taxonomies. We use Amazon Reviews, with the product category tree and monthly periods, as used in Privacy Budget Scheduling and Fairness-aware Differentially Private Collaborative Filtering. We also use MovieLens-1M with genre-to-movie hierarchies and timestamps, as in Towards Differential Privacy in Sequential Recommendation, and Last.fm listening logs with an artist-to-track hierarchy, as in PISA. For hierarchical private release on these three datasets, no reported result was found on Lacuna, so all baselines are run by us under identical clipping, budgets, and seeds.

The fourth asks whether the method reaches the downstream recommender. We feed each method's released popularity tree as a candidate prior into a popularity-reranked next-item recommender and report NDCG at a fixed cutoff. This tests whether gains in release error carry through to recommendation quality.

The checks that decide the question are as follows. The forecast-optimal split must differ visibly from the bottom-heavy split on at least one real dataset. The allocator must beat bottom-heavy-plus-smoothing on next-period error at matched budget. Recall of surging nodes must improve after injected shifts. This last check connects to the observation in AcCoRD that newly triggered preferences are where systems fail most. If the second check fails, the paper reports that temporal post-processing, not allocation, is what streaming hierarchical privacy needs.