Cardinality-Preserving Continual Release of Private Synthetic Longitudinal Data

Longitudinal data consists of repeated observations of the same individuals over time and thus allows us to learn trajectories, trends, and potential causal relations between events. We study the continual release of differentially private synthetic data in a longitudinal data collection setting of $n$ users. At every time step each user reports a private bit and the synthetic dataset must be updated in a differentially private manner (with regard to each user's data), such that desired statistics are close between the original and the synthetic dataset. Prior work by Bun, Gaboardi, Neunhoeffer, and Zhang (PODS 2024) studies as statistics the frequency of every pattern $s\in \{0,1{\}}^k$ occurring in the dataset of $n$ users in the last $k$ time steps. We introduce a new differentially private mechanism for continually generating synthetic data which improves upon prior work in three directions. (1) It maintains the same number of individuals as the original dataset, avoiding an exponential in $k$ blow up in the size of the generated synthetic dataset of Bun et al. (2) Our mechanism simultaneously achieves lower worst-case asymptotic error for the class of queries considered by Bun et al. when the pattern frequencies are normalized by dataset size, and lower error for answering queries corresponding to shorter patterns $s\in \{0,1{\}}^{\ell }$ for $\ell \le k$, avoiding an exponential dependence on $k-\ell$. (3) We extend our results from binary data to categorical data, with error that scales only polylogarithmically with the number of categories, giving the first such continual algorithm. Finally, we corroborate our theoretical findings with an empirical evaluation showing that our algorithm outperforms all other algorithms along multiple axes on real-world datasets.