acceptodds
Under review as a conference paper at ICLR 2027

Cardinality-Preserving Continual Release of Private Synthetic Longitudinal Data

Abstract

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 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 occurring in the dataset of users in the last 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 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 for , avoiding an exponential dependence on . (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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Differential Privacy, Synthetic Data, Longitudinal Data

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_6QSzOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the problem of continual release of differentially private synthetic data in a longitudinal data collection. The authors introduce a new recursive mechanism that bakes the consistency insights of Bun et al.'s seminal work directly into its private count generation. By replacing the discrete gaussian mechanism with exponential mechanism, they avoid the need for padding, so the dataset size always stays the same. The theoretical privacy-accuracy tradeoff is worse than Bun et al. by a k2k^2 factor, but the empirical experiment demonstrates great utility, at the cost of longer run time.

Critical strengths

The mechanism proposed is intuitive and presented cleanly. It preserves the cardinality, gives the additional smaller length pattern benefits, and has a nice extension to categorical data case, at the cost of worse accuracy in worst case. I find it acceptable given the extra benefits mentioned above. Moreover, empirically, the proposed method outperforms bun et al. and the runtime overhead is completely reasonable.

Critical weaknesses

None.

Questions for authors
  • The reported experimental results suggest substantial improvements over Bun et al., but the metric does not seem to subtract the effect of the extra padding. I understand the motivation, but I wonder whether the proposed method still outperforms Bun et al. on length-kk patterns, when compared against their padding-debiased estimates. This would help me understand whether the benefit comes mostly from no-padding or from your exp. mech. count generation

  • Another question is about the recursive nature of the propose mechanism. I think the benefit of smaller length-ll patterns with l≤kl\le k is attractive, but the error cumulation seems unavoidable. Suppose we don't care about smaller length patterns, could we do noising, and then do a projection in a "feasible set", instead of padding + post-hoc correction as in Bun et al.? This would preserve the cardinality and i wonder if this can avoid the error accumulation.

Reviewer_k7WROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the problem of continually releasing longtitudinal synthetic data, meaning that columns of the data arrive one at a time, at a synthetic dataset must be generated with differential privacy at each arrival. A previous algorithm for this setting requires potentially releasing a very large synthetic datasets, which may not be feasible in practice. The paper's proposed method fixes this issue, and provides stronger theoretical error bounds. The paper also compares with the previous method experimentally, and shows clear improvements across several datasets.

Critical strengths

The paper goes beyond most theory papers in DP synthetic data by having an explicit construction handling categorical data, not just binary data, and even implementing this in the experiments.

Critical weaknesses

The metrics used in the experiments are completely unfair to the previous BGNZ methods, since they do not account for the fact that BGNZ can generate larger synthetic datasets than the original. The metrics compare the raw counts of real vs. synthetic rows, which can have large differences simply because the synthetic dataset is larger than the original one, even if the synthetic data perfectly captured the distribution of the real data. Instead, the proportion of each possible row in real vs. synthetic data should be compared.

The paper is missing a clear baseline: using a continual release mechanism, such as one of the ones cited in Appendix A, to release DP counts, and then using a synthetic data generator that minimises the difference between the noisy counts and the counts from the synthetic data. The Private-PGM algorithm (McKenna et al. 2019) is likely a strong candidate for the synthetic data generator, but it likely will not scale to large TT. There are still options for large TT, such as training a neural network to generate data matching the noisy counts (Liu et al. 2021), or for example Private Evolution (Tran et al. 2026). These may not have theoretical error guarantees, but they may still perform well in practice.

References:

  • McKenna, Ryan, Daniel Sheldon, and Gerome Miklau. “Graphical-Model Based Estimation and Inference for Differential Privacy.” ICML 2019
  • Liu, Terrance, Giuseppe Vietri, and Steven Z. Wu. “Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods.” NeurIPS 2021
  • Tran, Toan, Arturs Backurs, Zinan Lin, Victor Reis, Li Xiong, and Sergey Yekhanin. “Differentially Private Synthetic Data via APIs 4: Tabular Data.” ICML 2026
Questions for authors

None

Reviewer_GpDxOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies differentially private continual release of synthetic longitudinal data. Building on Bun et al. (PODS 2024), the authors propose a new mechanism that preserves the original dataset cardinality while maintaining approximate counts of temporal patterns of lengths up to (k). The mechanism uses recursive consistency-preserving count generation with the exponential mechanism and a deficit-based score function. The authors establish privacy and accuracy guarantees, extend the construction to categorical data, and evaluate it on synthetic and real-world datasets.

Critical strengths
  1. Meaningful technical contribution. Maintaining exactly (n) synthetic users addresses an important limitation of prior work, which may incur exponential dataset-size inflation. The recursive construction and deficit-based analysis are technically interesting.

  2. Strong theoretical results. The paper provides user-level zCDP guarantees and simultaneous accuracy bounds for all pattern lengths up to (k). The categorical extension with polylogarithmic dependence on the alphabet size is another valuable contribution.

  3. Extensive empirical evaluation. The experiments cover multiple synthetic and real-world datasets and demonstrate substantial improvements in cardinality preservation, count errors, and efficiency for larger window sizes.

Critical weaknesses
  1. Theorem 3 gives an additive error bound of (O(\ell^2\sqrt{kT/\rho}\log(nkT/\beta))), which can substantially exceed the maximum possible count error (n). For example, with (n=200), (k=4), (T=500), and (\rho=0.05), the stated bound for length-4 patterns is approximately 84,793, whereas the actual error cannot exceed 200. This raises concerns about the practical informativeness of the theoretical guarantees. It would be useful to characterize the parameter regimes where the bounds are nontrivial and investigate whether tighter, data-dependent guarantees are possible.

  2. Much of the reported improvement, particularly the several-orders-of-magnitude reduction in normalized count errors, arises because the baseline introduces additional synthetic records through padding. When evaluated using normalized proportions error, which accounts for the different dataset sizes, the proposed method does not consistently outperform the baseline. For example, Appendix Table 6 reports substantially worse proportions error on several configurations, including uniform artificial data and some real-world datasets. While preserving cardinality is itself a meaningful contribution, the paper should more clearly distinguish improvements due to this structural constraint from improvements in statistical fidelity. The abstract's claim of improved normalized error should also be qualified.

  3. The evaluation focuses on suffix-count errors and runtime. While these metrics align with the theoretical objective, additional experiments on downstream longitudinal analyses would help demonstrate the practical utility of the generated synthetic data.

Questions for authors

see weakness 1 & 2.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.