Privacy Amplification by Structured Subsampling for Deep Differentially Private Time Series Forecasting

Thank you for your review and great suggestions for further expanding our experimental evaluation!
Please note that we cannot update the manuscript during this phase, but will integrate your suggestions as soon as possible.

Additional experiments/baselines

Effect of subsampling parameters on utility, independent of privacy

There are three key parameters: How we select sequences ("top-level"), how many subsequences $\lambda$ we sample per sequence, and batch size $\Lambda$.

In the following, we first let $\lambda=1$ (like in our other experiments), and vary the top-level scheme and $\Lambda$:
https://figshare.com/s/490812bd1b089d5c1dc5
Larger batch sizes $\Lambda$ improve utility on solar_10_minutes for some models, potentially due to its sparsity. However, the top-level scheme has no significant effect on utility.
Based on this observation, we choose large batch sizes $\Lambda=128$ and vary $\lambda$:
https://figshare.com/s/c4068a78b2d4f06aee25
There is no significant difference between $\lambda=1$ and $\lambda=16$, and no top-level scheme consistently outperforms any other.

We will add these results to Appendix C.2 and reference them from 5.2 to motivate our parameter choices for DP training.

Black-Box DP-SGD Baseline

Thank you for this suggestion, which will let us better explain to readers why structured subsampling is preferable to standard DP-SGD.

With standard fixed-batchsize DP-SGD, we would directly sample a batch of size $\Lambda$ from the $N_\mathrm{total} = N \cdot (L-L_F+1)$ subsequences of which $L_C+L_F$ contain sensitive information, with $L_C$ and $L_F$ being the context and forecast length. For $L_C+L_F=1$, one can use known tight bounds in a black-box manner (see Theorem 11.2 from Zhu et al. (2022)). However, they assume that only $1$ sensitive subsequence can appear in a batch, which makes them invalid when there are multiple sensitive subsequences ($L_C+L_F>1$)

Like in our Theorem 4.3, we know that with $L_C + L_F > 1$ the privacy of standard DP-SGD is in fact optimistically lower-bounded by $H_{e^\varepsilon}(\sum_{i=0}^{L_C+L_F} \gamma_i \cdot N(2i, \sigma)||N(0,\sigma))$, where $\gamma_i$ is the probability of sampling $i$ substituted subsequences, i.e., there is a risk of multiple leakage.

The following compares this lower bound to our upper bound for structured subsampling with $\lambda=1$ under $N_\mathrm{total}=10^6$ and varying $\Lambda,L_C+L_F$:
https://figshare.com/s/c061340645d5132c4a7e
Standard DP-SGD is equally private for $L_C+L_F=1$ and less private for $L_C+L_F>1$, precisely because it cannot prevent multiple leakage.

We will include this discussion and reference it from ll.90-92 in Section 1.1: "This risk of multiple leakage is underestimated if we apply guarantees for standard DP-SGD in a black-box manner (see Appendix C.3), [...]".

Wider range of $\varepsilon$ in Table 1

Thank you! We expanded the set of $\varepsilon$: https://figshare.com/s/bbef7e6e8ad6ce500bf1

---

Novelty of Techniques

Since our work is the first to analyze multi-level subsampling and privacy amplification for sequential data, we assume that you are referring to the fact that we use couplings to bound divergences in our derivations (please let us know if we misunderstood you).

Please note that defining couplings only makes up a part of our overall proof strategy. For example, of our derivations for bottom-level sampling in on pp. 28-37, only Appendices E.1.3 and E.2.0 on pp.31-32;35 make use of this technique, whereas the remaining proofs introduce novel techniques and results (e.g. adaptive parallel composition for dominating pairs in E.1.1).

Furthermore, applying couplings still requires non-trivial efforts (defining partitionings, proving validity of couplings, identifying distance constraints, deriving worst-case components given constraints,...)

Applications Beyond Forecasting

While we focus on forecasting, the underlying approach generalizes to multiple domains:

1. Our method can be directly applied to private self-supervised training for language models, where one also predicts "ground truth sequences" from a "context window" (see Section 4.5).
2. Our bounds directly apply to user-level privacy for arbitrary data, where $K$ records from one of $N$ data holders are substituted (see ll. 709-711).
3. Our novel amplification-by-augmentation method from Section 4.3 applies to any neighboring relations that enforces a bounded $\ell_2$ distance between datasets (e.g. privacy for patches in images).

Based on your feedback, we will mention all applications at the end of Section 4.5 so that the broader impact of our work is highlighted in one specific paragraph and not scattered over the manuscript.

---

Thank you again for your efforts! Please let us know if you have any additional questions during the discussion period.

---

Zhu et al. Optimal Accounting of Differential Privacy via Characteristic Function. AISTATS 2022

Thank you for your review! Please note that we cannot update the manuscript during the current rebuttal phase, but will integrate your feedback as soon as possible.

Motivation for Section 5.2

Upon re-reading the section, we agree that we could have done a better job of explaining what exactly we intend to demonstrate by evaluating the CRPS of different models at different $\epsilon$, especially because our paper may also be read by forecasting practitioners outside the differential privacy community.

Based on your feedback, we will replace the first paragraph of Section 5.2 with the following:
"Our previous experiments show how different parameterizations of the considered subsampling scheme affect the privacy of DP-SGD applied to time series. However, altering how batches are sampled will affect the training dynamics of forecasting models. Parameterizations that offer strong privacy (small $\epsilon$ and $\delta$) could potentially result in low model utility. The following experiments serve to show that we can in fact train neural forecasting models with strong privacy guarantees while retaining better utility than non-neural methods, i.e., DP-SGD for time series offers a good privacy--utility trade-off."

Please let us know if there are other parts of Section 5.2 that you think should be improved.

Implementation of Bounds

For reference, the bounds for $\lambda=1$ in Theorems 4.2, 4.4, and 4.5 are of the form $\begin{cases} H_\alpha((1-q) \cdot N(0, \sigma) + q \cdot N(2, \sigma)|| N(0,\sigma) ) & \text{if } \alpha \geq 1\\\\ H_\alpha(N(0,\sigma) || (1-q) \cdot N(0, \sigma) + q \cdot N(2, \sigma) ) & \text{if } \alpha < 1 \end{cases}$ where $q$ depends on the neighboring relation, top-level scheme, bottom-level scheme, and amount of Gaussian data augmentation.

The first case is equivalent to a GaussianPrivacyLoss with sensitivity=2, sampling_prob=q and AdjacencyType.REMOVE. The second case is equivalent to sensitivity=2, sampling_prob=q and AdjacencyType.ADD. We implement the case distinction through a class SwitchingPrivacyLoss that overrides get_delta_for_epsilon and evaluates one of the two PrivacyLoss objects, depending on the value of $\varepsilon$ (see src/dp_timeseries/privacy/pld.py in the supplementary material).

For $\lambda > 1$ and our optimistic bounds (e.g. Theorem 4.3), we need to consider a mixture with more than two components. For this, we can apply the same approach to the existing MixtureGaussianPrivacyLoss with AdjacencyType.REMOVE and AdjacencyType.ADD.

For $\lambda > 1$ and our pessimistic bounds (e.g. Theorem F.2), we need pairs of Gaussian mixtures and weighted sums of privacy profiles. These cannot be implemented via existing child classes and require custom classes (see DoubleMixtureGaussianPrivacyLoss and WeightedSumPrivacyLoss in src/dp_timeseries/privacy/pld.py in the supplementary material)

Motivation for Bi-Level Subsampling (LLMs?)

The bi-level approach is actually not motivated by LLMs, although your comment made us realize that a reader may get this impression from the "Bi-Level Subsampling for LLMs" paragraph in Section 2.

Instead, our goal is to analyze the privacy implications of combining DP-SGD with a batching approach that has already been used to train forecasting models before the advent of LLMs. For example, in GluonTS, top-level sampling is implemented by a TrainDataLoader and bottom-level sampling is implemented by an InstanceSampler.

Based on your feedback, we will replace the first sentence of Section 4.2 with the following:
"Recall from Section 1.1 that typical approaches for training forecasting models may also randomize which sequences $x_n$ contribute to a batch (e.g. by shuffling). As is standard with DP-SGD, we replace this shuffling operation with an independent sampling operation per batch to simplify privacy accounting".

Application to LLMs

There is in fact nothing that would prevent the direct application to token/sentence-level private self-supervised training with teacher forcing.

Just like in forecasting, one samples a finite "context window" from which a "ground truth sequence" is predicted. One would just need to replace the data loader in existing LLM implementations. The main limitation is that this method may be less optimized for memory access in distributed training than the highly refined data loaders that are likely being used to train commercial models on large clusters.

Based on your comment, we will replace the last sentence of Section 4.5 with the above paragraph, since "the connection [... to ...] language modeling is immediate" is somewhat ambiguous.

---

We hope that we addressed all your comments to your satisfaction. Please let us know if you have any additional questions during the discussion period.

Thank you for your review and great questions! Please note that we cannot update the manuscript during the current rebuttal phase, but will integrate your feedback as soon as possible.

Sampling choices/parameters for model training

Thank you for pointing out this ommission. We will of course specify these additional parameters in Section 5.2.

Our models were trained using top-level sampling without replacement, bottom-level sampling with replacement, and $\lambda=1$, i.e., one subsequence per sequence. For the datasets (electricity, solar, traffic) we used batch sizes $\Lambda=(128, 128, 256)$, noise multipliers $\sigma=(2.0, 4.0, 4.0)$, clipping constants $C=(10^{-4}, 10^{-4},10^{-4})$, and relative context lengths $L_C \mathbin{/} L_F = (1, 4, 8)$. The remaining parameters are already specified in Appendix B.2.

Effect of Sampling Choices on Utility

Based on your comment and a suggestion from Reviewer 3, we investigated the effect of different sampling choices on model utility, which we will include in our revised manuscript. Due to the character limit on rebuttals, please see our response to Reviewer 3 for details.

Prior Work on Graph DP

Thank you for pointing us to the work by Kasivishwanathan et al (2015). We will reference their work - as well as Nissim et al. (2007), who first studied edge privacy - in Section 1.

1 - Dominating Pairs for Substitution

You are right, any dominating pair for $K$ insertions and $K$ removals is also dominating for $K$ substitutions. We erroneously assumed that the "insert-$K$-remove-$K$" neighboring relation admitted more pairs of datasets, which would have made the statement for Poisson sampling. But this is of course not the case, thank you.

Please note that this was not intended to be a core contribution, but just a corollary of our more general, novel results for multiple sequences/users. Our Theorem E.1 (sampling with replacement under group substitution) also remains novel, since no prior work has analyzed WR sampling under group insertion/removal either.

We will update ll. 264-266 of the "Other Guarantees" paragraph to:
"Thus far, dominating pairs for sampling with replacement have only been known for individual substitutions. Thus, these guarantees are of interest beyond forecasting".

3 - Why a Single Subsequence is Preferable Under Composition

You are right. If we were to use pointwise addition of the $\delta(\epsilon,\lambda)$, then the ordering w.r.t. number of subsequences $\lambda$ would stay the same.

However, tight composition works by (1) determining the privacy loss distribution corresponding to the entire privacy profile $\delta : \mathbb{R} \rightarrow [0,1]$, (2) self-convolving the PLD, and (3) converting back to privacy profiles. Unlike pointwise addition, this is a non-linear functional operating on entire privacy profiles and may thus change their ordering.

We posit that $\lambda=1$ is better because $\lambda > 1$ allows more catastrophic failures of privacy (sampling multiple sensitive subsequences), whose probability accumulates under composition (see ll.381-387).

We believe that this effect could be better understood by studying the infinite limit of composition using central limit theorems for DP, which provide a simple formula in terms of privacy loss moments.

To make this clearer to readers, we will update Section 4.5 as follows:
"[...], future work may also want to investigate them analytically, e.g., via central limit theorems (Sommer et al. 2019), in particular to understand why $\lambda=1$ offers better privacy under composition."

2 - Why Top-Level Sampling is Preferable

As with the previous point, tight composition does not have a nice analytical expression that could be used to answer this question. Again, we believe that considering the infinite limit of composition (here: epoch length) could be a promising direction towards understanding why top-level subsampling offers better privacy despite requiring more compositions.

4 - Relative Improvement under Composition

Thank you for pointing out this inconsistency. We will use the following formulation instead:
"We observe that, after 100 training steps, $\lambda=1$ offers better privacy than $\lambda \in \{2,4\}$. It also offers better privacy than $\lambda \in \{8,16\}$ for small top- and bottom-level sampling probabilitites."

We will also include a column for $1000$ steps, where $\lambda=1$ actually outperforms $\lambda=16$ across all $\epsilon$ for the same parameterization as in Fig. 5: https://figshare.com/s/4292ea34e216427a0ded

5 - Interpolation on Page 20

We agree that interpolation makes the figures on p. 20 somewhat hard to read, and will remove it: https://figshare.com/s/9a3282037c6d268cd37a

---

Thank you again for your review! Please let us know if you have any additional questions during the discussion period.

---

Nissim et al. Smooth sensitivity and sampling in private data analysis. STOC 2007.