Privacy Amplification by Structured Subsampling for Deep Differentially Private Time Series Forecasting
Authors: Jan Schuchardt
Mina Dalirrooyfard
Jed Guzelkabaagac
Anderson Schneider
Yuriy Nevmyvaka
Stephan Günnemann
Venue: ICML 2025 spotlightposter (2025)
Keywords: Differential Privacy
Privacy Amplification
Privacy Accounting
Time Series
Forecasting
Primary area: social_aspects->privacy
TL;DR: We analyze the privacy of DP-SGD adapted to time series forecasting in a domain- and task-specific manner.

Abstract: Many forms of sensitive data, such as web traffic, mobility data, or hospital occupancy, are inherently sequential. The standard method for training machine learning models while ensuring privacy for units of sensitive information, such as individual hospital visits, is differentially private stochastic gradient descent (DP-SGD). However, we observe in this work that the formal guarantees of DP-SGD are incompatible with time series specific tasks like forecasting, since they rely on the *privacy amplification* attained by training on small, unstructured batches sampled from an unstructured dataset. In contrast, batches for forecasting are generated by (1) sampling sequentially structured time series from a dataset, (2) sampling contiguous subsequences from these series, and (3) partitioning them into context and ground-truth forecast windows. We theoretically analyze the privacy amplification attained by this *structured subsampling* to enable the training of forecasting models with sound and tight event- and user-level privacy guarantees. Towards more private models, we additionally prove how data augmentation amplifies privacy in self-supervised training of sequence models. Our empirical evaluation demonstrates that amplification by structured subsampling enables the training of forecasting models with strong formal privacy guarantees.

Privacy Amplification by Structured Subsampling for Deep Differentially Private Time Series Forecasting
Jan Schuchardt It Mina Dalirrooyfard 2 Jed Guzelkabaagae' Anderson Schneider? Yuriy Nevmyvaka
Stephan Günnemann"
Abstract
studies on the privacy risks of ML (Rigaki & Garcia, 2023)) and new methods to tackle these challenges (Liu et al., 2021; Pan et al., 2024). Among these works, Differential Privacy (DP) (Dwork, 2006) plays a particularly prominent role as a formal privacy model and paradigm for privacy protection.
Many forms of sensitive data, such web traffic, mobility data, or hospital occupancy, are inher- ently sequential. The standard method for train- ing machine learning models while ensuring pri- vacy for units of sensitive information, such as individual hospital visits, is differentially private stochastic gradient descent (DP-SGD). However, we observe in this work that the formal guar- antees of DP-SGD are incompatible with time series specific tasks like forecasting, since they rely on the privacy amplification attained by train- ing on small, unstructured batches sampled from an unstructured dataset. In contrast, batches for forecasting are generated by (1) sampling sequen- tially structured time series from a dataset, (2) sampling contiguous subsequences from these se- ries, and (3) partitioning them into context and ground-truth forecast windows. We theoretically analyze the privacy amplification attained by this structured subsampling to enable the training of forecasting models with sound and tight event- and user-level privacy guarantees. Towards more private models, we additionally prove how data augmentation amplifies privacy in self-supervised training of sequence models. Our empirical eval- uation demonstrates that amplification by struc- tured subsampling enables the training of forecast- ing models with strong formal privacy guarantees.
Historically, works DP primarily focused privately querying unstructured databases (Dwork et al., 2010), and later works on differentially private ML continued to fo- cus on learning from unstructured datasets (e.g. (Abadi et al., 2016)). Recently, there has been more attention on structured data, such as graphs (Nissim et al., 2007; Ka- siviswanathan et al., 2013; Mueller et al., 2022). text (Yue et al., 2023; Charles et al., 2024; Chua al., 2024), and time series (Mao et al., 2024). Time series in particular are of interest from both MI. and DP perspective. For example, data from traffic sensors (Chen et al., 2001) can be used to train forecasting models for use in tasks like transport planning and logistics (Lana et al., 2018). Simultaneously, traffic data and its downstream use may expose sensitive in- formation such individual movement profiles (Giannotti & Pedreschi, 2008). However, most studies only focus on releasing time series or statistics thereof, rather than training ML models (e.g. (Shi et al., 2011; Fan & Xiong, 2014)).
A popular algorithm for private learning from unstruc- tured datasets is DP-SGD (Song et al., 2013; Abadi et al., 2016). which is simple modification of SGD. Given an unstructured set of input-target pairs (ZN, oN)}. DP-SGD samples a batch y S computes clipped per-sample gradients, and adds Gaussian noise. This yields privacy guarantees for insertion/remooal or substitution of a single element (I,,, o,). DP-SGD has also been used to train models for time series (Mercier et al., 2021: Imtiaz et al., 2020; Arcolezi et al., 2022). However, these works directly apply known privacy guarantees for DP-SGD in a black-box manner. This neglects the struc- tured nature of the data and the structured way in which batches are sampled in tasks like time series forecasting, It may thus lead to an under- or over-estimation of privacy.
1. Introduction
The need for privacy in Machine Learning (ML) tasks is be- coming more apparent every day with an ongoing stream of
'Technical University of Munich & Munich Data Science In- stitute "Machine Learning Research, Morgan Stanley #Wokk done during an internship at Morgan Stanley. Correspondence to: Jan Schuchardt <j. schucharrd @um.medrddtttmme...... du..
This work answers the following research question: How private is DP-SGD when adapted sequentially structured data, and specifically time series forecasting?
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Deep Differentially Private Time Series Forecasting
Top-Level Sample
Bottom-Level Sample
Split
3/2
3bs
VCJI
SPA
20.2
MPA
y4 36 B6
D014
DFA
D01
51-3
9016
Figure High-level view on batching in global forecasting, which (1) selects one or multiple sequences ("top-level sample"), (2) selects one or multiple contiguous subsequences per sequence ( ("bottom-level sample"), and (3) partitions these subsequences for self- self-super training crontext-forecast split"). Elements of sensitive information from short subsequence (red) may appear in the batch multiple times at different positions.
1.1. Our contribution
2. Related Work
Our main goal is to provide sound and tight bounds how much private information is leaked when introducing gradient clipping and noise into the training of forecasting models that generalize across multiple time series ("global forecasting" (Januschowski et al., 2020)).
In this section, we discuss some of the most directly related work, and refer the reader Appendix A for further details.
DP Time Series Release. Koga et al. (2022) and Li et al. (2023) use subsampling to amplify the privacy of differen- tially private time series release. In particular, Koga et al. (2022) consider a single time series in which any individual contributes to a bounded number of steps. They use sub- sampling in the time domain reduce the probability of accessing these steps. Note that their sampling distribution ignores temporal structure and yields irregularly sampled time series. Li et al. (2023) combine amplification by sub- sampling and shuffling on the dataset level, i.e., they only randomize which time series is accessed and not which part of the time series. In general, our goal is training private models rather than publishing sanitized data.
Fig. provides a high-level view of how a single batch sampled in commonly used forecasting libraries like GluonTS (Alexandrov et al., 2019), and what level of pri- vacy leakage this can cause. Assume we have a dataset I22 x x= (2, 2z3 of three time series and want to protect any length-2 subsequence ("2-event-level privacy" (Kel- laris et al., 2014)). First, a subset of time series is selected ("top-level sample"). Then, one or multiple contiguous subsequences are sampled per sequence ("bottom-level sam- ple"). Finally, each subsequence is split into a context win- dow and ground-truth forecast. As shown in Fig. 1, our length-2 subsequence may appear in multiple subsequences, with each of its element contributing either to the context or the forecast window. Thus, these elements may leak their information through multiple clipped and noised per- subsequence gradients- - either as context via the model's computation graph or ground-truth via the loss function.
Application of DP-SGD to Time Series. Various works have applied DP-SGD (Mercier et al., 2021; Imtiaz et al., 2020; Arcolezi et al., 2022) or random input perturba- tions (Li et al., 2019) in specific domains like healthcare data and human mobility. However, they do not adapt their analysis or algorithms to time series data, and instead use DP-SGD or other mechanisms in a black- box manner. Simi- larly, some works have applied DP-SGD generative mod- els for time series (Frigerio al., 2019; Wang al.. 2020a; Torfi et al., 2022) or applied PATE (Papernot et al., 2017) in conjunction with DP-SGD (Lamp et al., 2024). This paper differs from prior work in that we specifically tailor our analysis to the structured nature of time series and the structured sampling of batches in forecasting.
This risk of multiple leakage is underestimated if we apply privacy guarantees for standard DP-SGD in a black-box manner (see also Appendix C.3), and overestimated we assume that every subsequence always contains every piece of sensitive information (e.g. (Arcolezi et al., 2022)).
Our main contributions are that we, for the first time,
derive event- and user-level privacy guarantees for bottom-level sampling of contiguous subsequences, analyze how the strength of these guarantees can be amplified by tepelevel sampling,
Bi-Level Subsampling for LLMs. Charles al. (2024) and Chua et al. (2024) use bi-level subsampling schemes for centralized finetuning of language models on the data of multiple users with multiple sensitive records. However, their privacy analysis only leverages the randomness in- duced by one of the sampling levels. The other level could equivalently be replaced by a deterministic procedure (see Section A for more details). In comparison, interplay of the randomness inherent to both levels. Further note that their analysis considers arbitrary records, and is not tailored to the sequential structure of natural language.
and prove how data augmentation can exploit the context-forecast split further amplify privacy.
Beyond these main contributions, our work demonstrates the usefulness of coupling- based subsampling analysis (Balle et al., 2018; Schuchardt et al., 2024), which has thus far only been applied to unstructured subsampling, in analyzing non ntn-standard, structured subsampling schemes.
analyze the
2

---

Deep Differentially Private Time Series Forecasting
3. Background and Preliminaries
subsampling (Kasiviswanathan et al., 2011): Computing gradients for randomly sampled batches strengthens differ- ential privacy (Abadi et al., 2016). More generally, one can use a subsampling scheme S : X + Y that maps from dataset space X to a space of batches Y and an (s', J'DDP base mechanism B Y + P that maps these batches to outputs to construct a more private subsampled mechanism M Bo S. Balle et al. (2018) propose the use of couplings as a tool for analyzing subsampled mechanisms.
3.1. Differential Privacy
The goal of differential privacy (Dwork, 2006) is to map from a dataset space X to an output space O while ensuring indistinguissabbitty of any neighboring pair of datasets x = o' that differ in one unit of sensitive information (e.g., two sets that differ in one element). In the following, we assume O = ERP Differential privacy achieves this goal of indistin- guishability via randomization, i.e., mapping to outputs via a random mechanism M : X - D. The random outputs M(x), M(x'), are considered indistinguishable if the proba- bility of any event O S RD only differs by a small factor and constant, i.e., Pr[M E O] S ef cPPP((((xe) E O] +6 This is equivalent to bounding the hockey stick divergence of output distributions Mz, MM (Barthe & Olmedo, 2013);
Definition 3.4. A coupling I' between distributions Sn,, Szz of randomly sampled batches Sxx), S(x') E Y is joint distribution on Y2 whose marginals are S₂ and Sgr.
o
Intuitively, I indicates which batches from the support of Sg correspond to which batches from the support of S. (for more thorough introduction, see (Villani, 2009)). Balle et al. (2018) prove that any such coupling yields bound on the divergence of the subsampled output distributions Mg and My. More recently, Schuchardt et al. (2024) have generalized this tool to enable the derivation of dominating pairs for subsampled mechanisms, which we utilize in our proofs and explain in more detail in Appendix D.1.
Definition 3.1. Mechanism M : X + R is (c, DP if and only if Vz= = x'_ Hos (M))) I 5 with H. (M)))))))>>> = SRO max dM,
LaM, (0) - -,,03 dMa(o).
3.2. Private Training and Dominating Pairs
In the case of DP-SGD (Song et al., 2013), the mechanism M: X + RdD is single training step epoch that maps training samples to D updated model weights (for details, see Section 4). A training run is the repeated application of this mechanism. A central notion for determining privacy parameters (E', 8') of such a composed mechanism is that of dominating pairs (Zhu et al., 2022), which fully characterize the tradeoff between E and of its component mechanisms.
3.4. Differential Privacy for Time Series
In the following, we consider the domain A = R- of uni- variate time series of length L. We discuss the straight- forward generalization of our results to multivariate time series in Appendix I. The goal of DP time series analysis is to compute statistics for a single series a E A while protecting short contiguous subsequences ("w-event-level privacy" (Kellaris et al., 2014)) or all steps to which an individual contributed ('user-level privacy" privaccyy (Dwork et al., 2010).. For our deep learning context, we define the dataset space to be the powerset X P(A) and generalize these notions of indistinguisaability to datasets as follows:
Definition 3.2. Distributions (P, Q) are a dominating pair for component mechanism M if sup Ha(M, (Ma') S H (PIlQ) for all a 2 0. If the bound holds with equality for all a 2 0, then (P, Q) are a right dominating pair.
Tight dominating pairs optimally characterize the trade-off between DP parameters (c, 8). We will repeatedly show P and Q to be univariate Gaussian mixtures, for which we use the following short-hand Choqueete--hoo et al., 2024).
Definition 3.5. Datasets x = {=1,..., NN} and x' = (at, (r/,...,,'') -xx. ) are w--event-lveel neighboring (r "n x') if they only differ in single pair of sequences In, an that only differ in a range of indices of length w, i.e. zn[it : t + w 1] # L : + w - 1] for some S $ L. Definition 3.6. Datasets x = {aI, AND and x' (si,..., r'y} are w-user-level neighboring (r So x') if they only differ in a single pair of sequences In, n'a that only differ in w indices, i.e., I|z, 2011oo S w.
Definition 3.3. The mixture-or of Gaussians distribution with means f E IR standard deviation a E IR,, and weights p E [0, 11 is MoG P, o) = - >x> N(H,,, Pks.
Given dominating pairs for each component mechanism, one can determine s' and 8' of the composed mechanism (train- ing run) via privacy accounting methods, such as moments accounting (Abadi et al., 2016) or privacy loss distribution accounting (Meiser& & Mohammadi, 2018; Sommer et al., 2019), which we explain in more detail in Appendix D.3.
For example, if our data were the number of patients in N hospitals over L = 365 days, then 14-event level privacy would protect patient's 's visit to hospital for up to 14 days while 14-user-level privacy would also protect multiple shorter visits.' Depending on the domain, these relations
3.3. Amplification by Subsampling and Couplings
'The number of elements w in w-user-level privacy is often omitted for historical reasons, but still used in deriving privacy guarantees, see, e.g., K in Table and Fig. of (Mao et al., 2024).
A key property that enables private training for many iter- ations with strong privacy guarantees amplification by
3

---

Deep Differentially Private Time Series Forecasting
can be made more precise by constraining the magnitude of change (e.g., (Koga al., 2022)). For instance, an individual can only change the number of patients on day by #1. We refer to this as (w, evvent and (w, v) uuser-llel privacy.
Algorithm 2 Noisy Training Step
Input: Batch of subsequences y = {yI..... ................................ yr }. context
length T.c. forecast length Lr, expected batch size A, model fo. learning rate 1,, noise scale o, clipping norm C
g x- 0
Definition 3.7. Consider datasets x Eg x' or Sy x' that differ in sequences nn, Fn If i',,t: [ [t] 2,14, I v, then we refer to them as (w, e)-event and (w, v) leer- neighboring (x:
for yı do
yc,, + yi(1 Lcl
fcontext window] {forecast window]
FF -- V: vilLo + 1: La + Lp]
w.y w.y E x' and x = u x²), respectively.
9: - VoL(fo(UC.:) yF,)
9 - 9 + 9. /max(1, [sslla)
{gradient clipping)
4. Deep Differentially Private Forecasting
9 < A (g + +N(00,2202)
return n1
Now that we have the language to formally reason about pri- vacy, let us turn to our original goal of training forecasting models. Algorithm I describes the use of top- and bottom- level sampling (recall Fig. 1), which we instantiate shortly. Given dataset of sequences æ {zi..... .N.. }. we sample subset of sequences, and then independently sample À E N subsequences from each of them. All subsequences are then aggregated into a single batch y. The size of the top-level sample is chosen such that we (up to modulo division) attain a batch size of A E N. Algorithm 2 formalizes the splitting of each subsequence y: E y into a context and ground-truth forecast window. Unlike in standard training, we clip the gradient of the corresponding loss and add calibrated Gaus- sian noise with covariance matrix C. This makes the training step differentially private under insertion/removal or substitution of a batch element (Abadi et al., 2016).
4.1. Bottom-Level Subsampling
Let us begin by focusing on the amplification attained via bottom-level sampling of temporally contiguous subse- quences. To this end, we assume that the top-level sampling procedure simply iterates deterministically over our dataset and yields [A /// sequences per batch (see Algorithm 3). As our bottom-level scheme, we use Algorithm 4, which samples À subsequences per sequence with replacement to achieve fixed batch size of A. In Appendix E.2, we ad- ditionally consider Poisson sampling, which independently includes each element at a constant rate. In forecasting frameworks, these methods are also referred to as number of instances sampling and uniform split sampling, respec- tively (Alexandrov et al., 2019). In the following, mecha- nism M refers to a single epoch with top-level iteration and bottom-level sampling with replacement.
Importantly, we neither claim the batching procedure nor the noisy training step to be novel in isolation. Our novel contribution lies in analyzing the interesting and non-trivial way in which the components of the batching procedure interact to amplify the privacy of training steps.
Contribution.
Algorithm 3 TTpp-Level Deterministic "Sampling"
Input: Data x: = { (uN). expected subsequences X. expected batch size A, batch number b
Algorithm 1 DP-SGD Epoch for Global Forecasting
N' + |A/ A]
("Sample" size}
Input: Data x= = (#1,.... IN) }, context length Lc, fore- cast length Lr, expected number of subsequences X, ex- pected batch size A, model fe. learning rate 17, noise scale a, clipping norm C
for n + 1 (b - 1) N' b. N' do
yield Ir
for 6 + 1 to [N A/ AJ do
Algorithm 4 Bottom-Level Sampling with Replacement
y + 0
Input: Sequence v,, context length Lo, forecast length LF, expected subsequences À
for In in
y + y J Jevell, X, A, b) do level( Lc, Lp, A) 0 - beiisytraining_stepll Le, LF, A, So, 71 o, C)
z/, + prepend zerosstr. Lc)
{padding) {maximum start index
T - L LF +1
return 0
for + 1 to x do
t - Uniform((1,....
yield ,/ [t: : t + Lo + LF - 1]
(cropping]
Simplifying assumptions. For the sake of exposition and to simplify notation, we assume that I, - LF + 1 2 Le + LF and focus on 1-event-level privacy. In Appendix I, we discuss how to easily generalize our guarantees to w-event and w-user-level privacy with arbitrary w E N, as well as variable-length and multivariate time series.
Effect of Number of Subsequences A. Before we pro- ceed to deriving amplification guarantees, note that bi-level subsampling introduces an additional degree of freedom not present in DP-SGD for unstructured data: batch of
4

---

Deep Differentially Private Time Scries Forecasting
size A can be composed of many subsequences from few sequences (A large) or few subsequences from many se- quences (Á small). Intuitively, the latter should be more private, because there are fewer chances to access sensitive information from any specific sequence Zn- In fact, we can prove the correctness of this intuition via stochastic dominance of amplification bounds (see Appendix E.3):
the potential of leaking private information. In Section 5, we will demonstrate numerically that composing many short, more private epochs (A = 1) nevertheless offers stronger privacy for the same number of training steps. As baselines for this experiment, we will use the following optimistic lower bounds (proof in Appendix E.1.4):
Theorem 4.3. Consider the number of subsequences À A21 1, Le+LE and let I. -. Define P(A)= = MMo p. with means 14 E N and weights p E [0, with pi 2 2(i-1) and = Binomial(i X, Further, define per- epoch privacy profile H(a) = sup wžaz' Then,
Theorem 4.1. Let P* (A), (A) be a right dominating pair of epoch M for bottom-level Poisson sampling or sampling with replacement and X E N (expected) subsequences. Then Ha (X), Q (A)) is minimized by À = 1 for all a 2 O.
Hal (M
Guarantees for Optimal A. Based on this result, let us first focus on the case À = 1 that minimizes per-epoch privacy leakage. Because we consider subsequences of length Lo + Lp, even a single sensitive element of sequence Iy can contribute to Le + Lr different subsequences at different positions. Since we deterministically iterate over our dataset, these subsequences can contribute to exactly one training step per epoch. The resultant privacy is tightly bounded by the following result (proof in Appendix E).
H(a) N (a(P()))V((OOO) fa 1, (L(N(O,))IL(()) i
Intuitively, each mixture mean 14; corresponds to the event that i subsequences with information of a specific indi- vidual are sampled, i.e., more information is leaked.
4.2. Top-Level Subsampling
Theorem 4.2. Consider the number of sampled subse- Lo+Lp be the probability quences À= 1, and let r = LLLL+11
Thus far, we only focused on how randomly selecting subse- quences from longer sequences amplifies privacy. However, standard batching procedures for time series forecasting admit two levels of randomness (recall Fig. 1). In the fol- lowing, let us explore how randomizing which sequences on contribute to a batch can further amplify privacy. For this, we use Algorithm 5, which samples without replacement. This will eliminate the chance that any particular sequence on can have its information leaked through more than À sub- sequences per batch. From here on, mechanism M refers to a single training step using top-level sampling without replacement and bottom-level sampling with replacement.
of sampling a subsequence containing any specific element. Define P11) = MoG(u, with means μ = [[o 2]= and weights p- = [1 r r]² Further, define per-epoch privacy profile (a) = sup o2 (M Then,
H(a)= Ha(P()))O(O 1, (I(N() a
In Appendix E.1.5, we discuss the tight dominating pairs corresponding to this bound. Intuitively, as r decreases, P(1) converges to (0, 1) and the hockey stick divergence decreases. This means that the mechanism becomes more private with increasing sequence length L or decreasing context length Le and forecast length Lp.
Algorithm 5 Top-Level Sampling Without Replacement
Input: Data x = (=i,.... , NN), expected subsequences X. expected batch size A, batch number b
Other Guarantees. In Appendix E. we derive tight dom- inating pairs for Poisson sampling and À 2 1, as well dominating pairs for sampling with replacement and X 2 1. The special case of N = 1, A = > is equivalent to sampling from a set in which Lc + LF elements are substituted, i.e., subsampled group privacy (Ganesh, 2024; Schuchardt et al., 2024; Jiang et al., 2025). Thus far, dominating pairs for sam- pling with replacement have only been known for individual substitutions, i.c., our group privacy guarantees for sampling with replacement are of interest beyond forecasting.
N' + [A] / AJ
{Sample size}
π < rawdaaannddaaaaaaaa permutation(N)
for n + 1 to N' do yield Tz(n)
Theorem 4.4. Consider the number of subsequences X = 1
Lo+Le and batch size A. Letr r = -I-F++I and let |A/ AJ / N be the probability of sampling any specific sequence. De- fine P(1)
MoG(H,,Do) with i = [o 2)" and
i [11 p) p. (0 r)
p.r]².
Then, per-step pri- Ha (MMMl) fulfills
Epoch Privacy vs Length. Despite the optimality guaran- tee from Theorem 1. we need to consider that sampling few subsequences (A small) means that more sequences con- tribute to a batch (LA/ / A| large). We thus need more epochs for the same number of training steps, and each epoch has
vacy profile H()) = sup suppege pdd gar
H.. (H.(P())NO)OO ifa21, 1, i(aa)
(H.(N(00)))P(1))) f00a<11.
5

---

Deep Differentially Private Time Scries Forecasting
Put simply, the probability p of sampling a sequence with sensitive information multiplies with the probability of including this sensitive information in the sampled subse- quence. This determines the weight p r of the mixture component with mean 2 that indicates privacy leakage.
yc,, or via ground-truth forecast yF.. Even if this element changes by -u, there is chance that we sample the same value after adding Gaussian noise, i.e., have zero leakage. In Appendix G, we use conditional couplings in conjunction with the maximal couplings originally used for subsamppiig analysis by Balle et al. (2018) to formalize "sampling the same value". The following result shows the special case oc OF where the context and forecast noise scale are identical (for the general case, see Theorem G.1).
Other guarantees. In Appendix F, we additionally derive dominating pairs for À 2 when using bottom-level sam- pling with replacement or Poisson sampling. There, P still has similar effect of attenuating privacy leakage.
Theorem 4.5. Consider X - batch size A, as well as context and forecast standard deviations de, OF E R4 with
Step- vs Epoch-Level Accounting. While Theorem 4.4 shows that top-level sampling amplifies privacy, it yields bounds for each training step M instead of each epoch M (cf. Theorem 4.2). We need to self-compose these bounds LAV A/A // times to obtain epoch-level guarantees (see Algo- rithm 1). In Section 5 we confirm that the resulting privacy guarantees can nevertheless be stronger than our original epoch-level guarantee. This observation is consistent with works on DP-SGD for unstructured data that self-compose subsampled mechanisms instead of deterministically iterat- ing over datasets (c.g. (Abadi et al., 2016)).
ac = dr. Let r LC+LF and p =LA / XJ / N. De-
L--x+1
fine P(1) = Mo. o) with means pa = [o 2] and weights P E [0. 1J", with p1 - p2 and
P2 = p.r. TVD
with total variation distance TVD(P.Q) (P(I))
Then, (a)= sup 2/2 2x
Ha (aMMa|)M fulfills
Choice of A. As before, we can ask ourselves which num- ber of subsequences per sequence y E N we should choose. In bi-level subsampling. there is more intricate trade-off, because increasing X decreases p. i.e., strengthens top-level amplification, but weakens bottom-level amplification (re- call Theorem 4.1). In Section 5, we demonstrate numeri- cally that À = 1 is still preferable under composition. As fair baselines for this experiment, we use optimistic lower bounds for x >>> 1 that we derive in Appendix F.4.
iT(a)= < (.(P()))N(OOO) 1fa21, (a(V(O,))IP(1)) f
Intuitively, this shows that Gaussian data augmentation has a similar effect to subsampling in that shifts probability mass to the mixture component that indicates zero leak- age. Unlike top- and bottom-level subsampling, which are interdependent through number of subsequences X, this addi- tional layer of amplification can be independently controlled through oc and op. Amplification by data augmentation thus expands the space of possible privicy-utility trade-offs.
4.3. Context-Forecass Split
We have already successfully analyzed how top- and bottom- level subsampling interact to amplify the privacy of clipped and noised gradients 9 Vf (yC,,) yF,)). However, we can use yet another level of perccasting-spccfiie random- ness- - if we assume that an individual can change each value of a series by at most E R4, i.e., we assume (w, v)- event or (w, ue-ueel-level privacy (Definition 3.7). We pro- pose to augment the context and forecast window with Gaus- sian noise Zo ~ .N(0, o. v². I), Zp ~ NN of. v2 I):
Amplification by Label Perturbation. An interesting spe- cial case is 0 oc < OF. where privacy is only further amplified when sensitive information appears as ground- truth forecast, i.e., we are in the "label privacy" (Chaudhuri & Hsu, 201 1) setting. A standard technique for deep learn- ing with label privacy is using random label perturbations as an offline pre-processing step (Ghazi et al., 2021). Our results in Appendix G show for the first time how online label perturbations can amplify privacy in settings where we randomly switch between feature- and label-privacy, such as self supervupe (pre-) ttriiiitiinn of sequence models.
g: = VoL(folye. + Zc), yr. + ve),yr.++2. Zr).
(1)
Unlike the input perturbations from (Arcolezi et al., 2022) which are an offline pre-processing that privatizes the dataset, Eq. (1) is an online data augmentation that serves as an integral part of the (now continuous) subsampling proce- dure. In the following, let M refer to single training step when combining level sampling without replacement, bottom-level sampling with replacement, and Eq. (1).
4.4. Additional Inference- -imee Privacy
Like other works on DP-SGD, we focus on ensuring privacy of parameters 0 to guarantee that information from any train- ing sequence xr, does not leak when releasing the model fo or forecasts fe(#m) for other sequences Im. In Appendix H. we additionally explore the use of input perturbations in combination with subsampling and imputation to ensure privacy for elements of Fa when releasing forecast fo(x.))
Amplification by Data Augmentation. Intuitively, any element can only contribute to gradient 9; either via context
6

---

Deep Differentially Private Time Series Forecasting
4.5. Limitations and Future Work
In addition, we train common probabilistic forecasting ar- chitectures standard datasets verify the feasibility of training deep differentially private forecasting models while retaining meaningful utility. The full experimental setup is described in Appendix B. An implementation will be made available at cs.cit. wct...tm.de//mm//// wum..eeddam///p-ffoecattii
Since we are first to analyze forecasting-specife subsam- pling, there are still opportunities for improvement, namely by tightening guarantees for (1) bottom-level sampling with replacement and À > 1, (2) top-level sampling without replacement and À > 1, and potentially (3) amplification by augmentation. A somewhat subtle challenge when consider- ing top-level sampling without replacement, bottom-level sampling with replacement, and number of subsequences A relates the fact that subsampling analysis (see Ap- pendix D. revolves around defining correspondences be- tween batches from the support of different distributions (via couplings) and determining their similarity (via induced dis- tances): Assume two datasets x = x' differ by one sensi- tive element x. [t] # r [t] in a pair of sequences Vn * x', Then, any batch that does not contain subsequences of x,, or 5e will differ in least À subsequences from any batch that contains subsequences of z z', no matter if the sensi- tive element is contained once, twice, À times or zero times. For this reason, we posit that the lower bound from Theo- rem F.7 (even though it appears like a natural generalization of Theorem 4.4) is not tight upper bound, and advise future work to not overlook this issue.
5.1. Trade-Offs in Structured Subsampling
For the following experiments, we assume that we have N = 320 sequences, batch size A = 32, and noise scale a = 1. We further assume L = 10(LF + Lc) + LF 1, so that the chance of bottom-level sampling a subsequence containing any specific element is 0.1 when choosing À as the number of subsequences. In Appendix C.I, we repeat all experiments with wider range of parameters. All results are consistent with the ones shown here.
Number of Subsequences A. The first trade-off is inherent to bi-level subsampling: One can achieve the same batch size A with different X, each leading to different top- and bottom-level amplification. We claim that À = 1 (i.e., max- imum bottom-level amplification) is preferable. For fair comparison, we compare our provably tight guarantee for X = 1 (Theorem 4.4) with optimistic lower bounds for À > (Theorem F.7) instead of our sound upper bounds (Theorem F.I), i.e., we make the competitors stronger. As shown in Fig. 2a, when considering single training step. However, after 100-fold composition, x = 1 achieves smaller 8(E) even in [10-3, 10-1] (see Fig. 2b). Our explanation is that À > 1 results in larger 8(e) for large s, i.e., is more likely to have a large privacy loss. Because the privacy loss of a composed mechanism is the sum of component privacy losses (Sommer et al., 2019), this problematic when performing multiple training steps. We will thus later use À for training.
While we numerically investigate the discussed trade-offs in parameterizing our subsampling scheme, future work may also want to investigate them analytically. In particular, central limit theorems of composition (Sommer et al., 2019; Dong et al., 2022) could potentially be used to understand why x = 1 offers the best privacy for an increasingly wide range of e as the number of composition steps grows.
only has smaller d()) for E 2 10-1
Finally, the connection between event and w-event-level privacy and token- sentence-level private language mod- eling (Hu et al., 2024) (i.e., autoregressive probabilistic fore- casting for discrete-valued time series) is immediate and should be explored in future work. Specifically, time series in a global forecasting dataset correspond to documents in a corpus. Sensitive events correspond to sensitive sentences. The notion of context windows is shared between both do- mains. Ground- forecasts correspond to ground- -tuth sequences that can, for example, be learned via teacher- forcing. Beyond event-level privacy, the derived bounds are also applicable to user-level private learning with bi-level subsampling under a fixed number of substitutions per user (such as user-level private LLM fine-tuning, see discussion of (Chua al., 2024; Charles et al., 2024) in Appendix A).
Step- vs Epoch-Level Accounting, Next, we show the ben- efit of top-level sampling sequences (Theorem 4.4) instead of deterministically iterating over them (Theorem 4.2), even though we risk privacy Ieakage at every training step. For our parameterization and A = 1, top-level sampling with replacement requires 10 compositions per epoch. As shown in Fig. 3, the resultant epoch-level profile is nevertheless smaller, and remains so after 10 epochs. This is consistent with any work on DP-SGD (e.g., (Abadi et al., 2016)) that uses subsampling instead of deterministic iteration.
Epoch Privacy vs Length. In Appendix 1.1.4 we addition- ally explore the fact that, if we wanted to use deterministic top-level iteration, the number of subsequences À would af- feet epoch length. As expected, we observe that composing many private mechanisms (A- = 1) is preferable to com- posing few much less private mechanisms (A > 1) when considering fixed number of training steps.
5. Experimental Evaluation
We already achieved our primary objective of deriving time series specific subsampling guarantees for DP-SGD adapted to forecasting. Our goal for this section is to investigate the trade-offss we discovered in discussing these guarantees.
7

---

Deep Differentially Private Time Scries Forecasting
0.006
0.25
0.20
0.004
0.15
16
16
0.10
0.002
Tight upper bound
Tight upper bound
0.05
Lower bound
Lower bound
0.000
0.00
10
10-2
10-1
10
10
10
10
10 10-1
10
10'
(a) Training step 1
(b) Training step 100
Figure 2: Top-level WOR and bottom-level WR sampling under varying number of subsequences. Under composition, even optimistic lower bounds (Theorem F.7) indicate worse privacy for À > than our tight upper bound for À (Theorem 4.4).
Amplification by Label Perturbation. Finally, because the way in which adding Gaussian noise the context and/or forecast window amplifies privacy (Theorem G.1) may be somewhat opaque, let us consider top-level sampling with- out replacement, bottom-level sampling with replacement, = 1, dc = O, and varying label noise standard deviations OF. As shown in Fig. 4, increasing OF has same effect as letting the forecast length LG go to zero, i.e., eliminates the risk of leaking private information if it appears in the forecast window. Of course, this data augmentation will have effect on model utility, which we investigate shortly.
Datasets, Models, and Metrics. We consider three standard benchmarks: traffic, e electrici ty, and solar-10 1olaar10.minutes miiiiiinnttss used in (Lai et al., 2018). We further consider four common architectures: A two-layer feed-forward neural network ("SimpleFeeFForvard) current neural network ("DeepAR" (Salinas et al., 2020)), an encoder-only transformer ("TTransformer" (Liu al., 2024)), and refined feed-forward network proposed com- pete with attention- based models ("DLinear" (Zeng et al., 2023)). We let these architectures parameterize elementwise I-distributions to obtain probabilistic forecasts. We measure the quality of these probabilistic forecasts using continuous ranked probability scores (CRPS), which we approximate via mean weighted quantile losses (details in Appendix B.3). a reference for what constitutes "meaningful utility", we compare against seasonal naïve forecasting and exponen- tial smoothing ("AutoETS") without introducing any noise. All hyperparameter values specified in Appendix B. All experiments are repeated with 5 random seeds.
5.2. Application to Probabilistic Forecasting
Our previous experiments show how different parameter- izations of the subsampling scheme affect the privacy of DP-SGD applied to time series forecasting. However, al- tering how batches are sampled will affect the training dy- namics of forecasting models. Parameterizations that offer strong privacy (small and A) could potentially result in low model utility. The following experiments serve show that in fact train neural forecasting models with strong privacy guarantees while retaining better utility than non-neural methods. In short: DP-SGD for time series forecasting offers good privacy-utility trade-off.
Event-Level Privacy. Table shows CRPS of all models on the traffic test set when setting 10-7, and train- ing on the training set until reaching pre-specified æ with l-event-level privacy. For the other datasets and standard deviations, see Appendix C.2.1. 1. The column
indi- cates non-DP training. As can be seen, models can retain much of their utility and outperform the baselines, even for < which generally considered a small privacy budget (Ponomareva et al., 2023). For instance, the aver- age CRPS of DeepAR on the traffic dataset 0. 124 with non-DP training and 0.157 for 0.5. Note that, since all models are trained using our tight privacy analysis, which specific model performs best which specific dataset is orthogonal to our contribution.
Table 1: Average CRPS on traffic for J 70-7.-0 Sea- sonal, AutoETS, and models with oc are without noise.
MODEL
= 0.5
DO
SIMPLEFF
0.207
0.195
0.193
0.136
DEEPAR
0.157
0.145
0.142
0.124
ITRANSE.
0.211
0.193
0.188
0.135
DLINEAR
0.204
0.192
0.188
0.140
SEASONAL
0.251
0.251
0.251
0.251
Other results. In Appendix C.2.2 we additionally train probabilistic forecasting models with w-event and w-usser
AUTOETS
0.407
0.407
0.407
0.407
8

---

Deep Differentially Private Time Series Forecasting
0.4
Deterministic
0.006
OF
Sampling (WOR)
0.0
0.3
8(c)
0.004
1.0
0.2
5.0
Epoch 10
0.002
Epoch
1.c
60,
I.p
=
30
Step
Le
60,
1.p
0.0
0.000
10
10
2
10 10"
10a
10-a
10-2
10-1
10
10A
C
Figure 3: Top-level deterministic iteration (Theorem 4.2) vs top-level WOR sampling (Theorem 4.4) for À = 1. Sampling more private despite requiring more compositions.
Figure 4: Varying label noise OF for top-level WOR and bottom-level WR (Theorem G.1) with de = 0, X = 1. In- creasing or is equivalent to decreasing forecast length.
privacy. In Appendix C.2.3, we demonstrate that label per- turbations can further improve the privacy-utilig trade-off. In Appendix C.2.4, we perform non-private training with dif- ferent subsampling schemes to verify that the good privacy- utility trade-off achieved via bi-level subsampling not simply due improvements in raw predictive performance. All results confirm that our guarantees for DP-SGD adapted to forecasting are strong enough to enable private training while retaining meaningful levels of utility.
Konrad Zuse Schools of Excellence in Artificial Intelligence, sponsored by the German Federal Ministry of Education and Research.
Impact Statement
This work is specifically aimed at mitigating negative soci- etal impact of machine learning by provably ensuring that forecasts made by a model trained on sensitive data does not allow for any form of membership inference or reconstruc- tion attack. As such, even though there are many potential societal consequences of our work, we do not feel that any of them must be specifically highlighted here.
6. Conclusion
In this work, we answer the question how DP-SGD can be adapted to time series forecasting while accounting for domain- and task-specific aspects. We derive privacy ampli- fication guarantees for sampling contiguous subsequences and for combining this bottom-level sampling with top-level sampling of sequences, and additionally prove that parti- tioning subsequences into context and ground -truth fore- casts enables privacy amplification by data augmentation. We further identify multiple trade-offs inherent to bi-level subsampling which we investigate theoretically and/or nu- merically. Finally, we confirm empirically that it is feasible to train differentially private forecasting models while re- taining meaningful utility. Adapting our results to natural language represents a promising direction for future work towards trustworthy machine learning on structured data.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Alexandrov, A., Benidis, K., Bohlke-Schneider, M., Flunkert, V., Gasthaus, J., Januschowski, T., Maddix, D. C.,, Rangapuram, S., Salinas, D., Schulz, J., et Glu- onts: Probabilistic time series models in python. arXiv preprint arXiv: 0ee.119666..... 2019.
Arcolezi, H. H., Couchot, J.-F., Renaud, D., Al Bouna, B., and Xiao, X. Differentially private multivariate time se- ries forecasting of aggregated human mobility with deep learning: Input or gradient perturbation? Neural Comput- ing and Applications, 34( 133555333-1339 2022.
Acknowledgements
We would like to thank Dominik Fuchsgruber, Jonas Dorn- busch, Marcel Kollovieh, and Leo Schwinn for proofreading the manuscript. We are also grateful to Marcel Kollovich, Kashif Rasul, and Marin Biloš for providing valuable in- sights into practical aspects of training forecasting models. This research partially funded by the German Research Foundation (grant GU 1409/4-1) 1) and by the DAAD program
Balle, B. and Wang, Y.-X. Improving the gaussian mecha- nism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Ma- chine Learning, pp. 394 403, 2018.

---

Deep Differentially Private Time Series Forecasting
Balle, B., Barthe, G., and Gaboardi, M. Privacy amplifica- tion by subsampling: Tight analyses via couplings and divergences, Advances in neural information processing systems, 31, 2018.
Den Hollander, F. Probability theory: The coupling method. Lecture notes available online (http://websites. math. leidenuniv. atppobbbtiyyeeuurreessssuuiginnp pdf), 2012.
Balle, B., Barthe, G., and Gaboardi, M. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1), 2020.
Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 2022.
Barthe, G. and Olmedo, F. Beyond differential pri- vacy: Composition thcorems and relational logic for divergences between probabilistic programs. In Fomin, F. V., Freivalds, R., Kwiatkowska, M., and Peleg, D. (eds.), Automata, Languages, and Programming, pp. 49- 60, 2013.
Doroshenko, V., Ghazi, B., Kamath, P., Kumar, R., and
Manurangsi, P. Connect the dots: Tighter discrete approx- imations of privacy loss distributions. Proceedings on Privucy Enhancing Technologies, 2022.
Dwork, C. Differential privacy. In Automata, Lan-
guages and Programming: 33rd International Collo- quium, ICALP 2006, Venice, Italy, July 10-14, 2006, Pro- ceedings, Part I1 33, pp. 1-12. Springer, 2006.
Carranza, A., Farahani, R., Ponomareva, N., Kurakin, A., Jagielski, M., and Nasr, M. Synthetic query generation for privacy-preservin
deep retrieval systems using dif- ferentially private language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp- 3920-3930, 2024.
Dwork, C. and Rothblum, G. N. Concentrated differential privacy. arXiv preprint
2016.
Dwork, C.,, Naor, M., Pitassi, T., and Rothblum, G. N. Dif- ferential privacy under continual observation. Proceed- ings of the Forty-Second ACM Symposiun Theory of Computing, STOC '10, pp. 715-724, 2010.
Charles, Z., Ganesh, A., McKenna, R., McMahan, H. B., Mitchell, N. E., Pillutla, K., and Rush, J. K. Fine-tuning large language models with user-level differential pri- vacy. In ICML Workshop on Theoretical Foundations of Foundation Models, 2024.
Falcetta, A. and Roveri, M. Privacy-prest preservin time series prediction with temporal convolutional neural networks. In 2022 International Joint Conference on Neural Net- works (IJCNN), pp. 1-8, 2022.
Chaudhuri, K. and Hsu, D. Sample complexity bounds for differentially private learning. In Proceedings of the 24th Annual Conference on Learning Theory, pp. 155-186, 2011.
Fan, L. and Xiong, L. An adaptive approach to real-time aggregate monitoring with differential privacy. IEEE Transactions on Knowledge and Data Engineering, 26 (9):2094-210) 2014.
Chen, C., Petty, K., Skabardonis, A., Varaiya, P., and Jia, Z. Freeway performance measurement system: mining loop detector data. Transportation research record, 1748(1): 96-102, 2001.
Feldman, V., Mironov, I., Talwar, K., and Thakurta, A. Pri- vacy amplification by iteration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018.
Chen, Y., Biloš, M., Mittal, S., Deng, W., Rasul, K., and Schneider, A. Recurrent interpolants for probabilistic time series prediction. NeurlPS 2024 Third Table Representation Learning Workshop, 2024.
Fioretto, F. and Van Hentenryck, Optstream: Releasing time series privately. Journal of Artificial Intelligence Research, 65:423-456. 2019.
A., Steinke, T., and Thakurta, A. G. Privacy amplification for matrix mecha- nisms. In International Conference Learning Repre- sentations, 2024.
Srqquette-Choo C. A., Ganesh,
Frigerio, L., de Oliveira, A. S., Gomez, L.,, and Duverger, P. Differentially private generative adversarial networks for time series, continuous, and discrete open data. In ICT Systems Security and Privacy Protection: 34th IFIP TC International Conference, SEC 2019, Lisbon, Portugal, June 25-27, 2019, Proceedings 34, pp. 151-164, 2019.
Chua, L., Ghazi, B., Huang, Y., Kamath, P., Kumar, R., Liu, D., Manurangsi, P., Sinha, A., and Zhang, C. Mind the privacy unit! user-level differential privacy for language model fine-tuning. In Conference on Language Modeling, 2024.
Ganesh, A. Tight group-level dp guarantees for dp-sgd with sampling via mixture of gaussians mechanisms, arXiv preprint arXiv:2401. 10294, 2024.
10

---

Deep Differentially Private Time Series Forecasting
Garza, A., Canseco, M., Challú, C., and Olivares, K. Stats- Forecast: Lightning fast forecasting with statistical and econometric models. PyCon Salt Lake City, Utah, US 2022, 2022. URL Stthttps:// /ttpt/u////hub///////hpppp github..hhhggogg www.coooooii....e Naxttax stat statsforecast.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What learn privately? SIAM Journal Computing, 40(3):793-826, 2011.
Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., and Smith, Analyzing graphs with node differential privacy, In Theory of Cryptography, pp- 457-476, 2013.
Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., and Zhang, C. Deep learning with label differential privacy. Advances in neural information processing systems, 34: 27131-27145, 2021.
Katsomallos, M., Tzompanaki, K., and Kotzinos, D. Privacy, space and time: survey on privacy-preserving contin- uous data publishing. Journal of Spatial Information Science, 2019(19)557-133, 2019.
Giannotti, F. and Pedreschi, D. Mobility, data mining and privacy: Geographic knowledge discovery. Springer Science Business Media, 2008. ISBN 9783540751762.
Kellaris, G., Papadopoulos, S., Xiao, X., and Papadias, D. Differentially private event sequences over infinite streams. Proc. VLDB Endow., 7(12): 155-:115511 August 2014.
Gneiting, T. and Raftery, A. E. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359-77, 2007.
Koga, T., Meehan, C., and Chaudhuri, K. Privacy amplifi- cation by subsampling in time domain. In International Conference on Artificial Intelligence and Statistics, pp. 4055-4069, PMLR, 2022.
Google Differential Privacy Team. Privacy loss distribu- tions. com/ http:oggee/dlfferemiiaaa--piiee/ main/ Distribution www.ttiiiooo...mom .df, 2024. 22, 2024.
Loss____________________________ Accessed May
Kollovieh, M., Ansari, A. E, Bohlke-Schneider, M., Zschiegner, J., Wang, H., and Wang, Y. B. Predict, refine, synthesize: Self-guiding diffusson models for probabilis- tic time series forecasting. Advances in Neural Informa- tion Processing Systems, 36, 2024.
Gopi, S., Lee, Y. T., and Wutschitz, L. Numerical composi- tion of differential privacy. Advances Neural Informa- tion Processing Systems, 34:1 111111116642 2021.
Koskela, A., Jälkö, J., and Honkela, A. Computing tight differential privacy guarantees using fft. International Conference on Artificial Intelligence and Statistics, pp- 2560-2569, 2020.
Herzen, J., Lässig, F., Piazzetta, S. G., Neuer, T., Tafti, L., Raille, G., Pottelbergh, T. V., Pasieka, M., Skrodzki, A., Huguenin, N., Dumonal, M., Košcisz, J., Bader, D., Gusset, F., Benheddi, M.. Williamson, C., Kosinski, M., Petrik, M., and Grosch, G. Darts: User-friendly modern machine learning for time series. Journal of Machine Learning Research, 23(124):1-6; 2022.
Lai, G., Chang, W.-C., Yang, Y., and Liu, H. Modeling long- and short-term temporal patterns with deep neural net- works. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR '18 pp. 95-104, 2018. ISBN 9781450356572.
Hu, L., Habernal, I., Shen, L.., and Wang, D. Differentially private natural language models: Recent advances and future directions. In Graham, Y. and Purver, M. (eds.), Findings of the Association for Computational Linguis- fies: EACL 2024, pp. 478-4994 2024.
Lamp, J., Derdzinski, M., Hannemann, C., Van der Lin- den, J., Feng. L., Wang, T., and Evans, D. Glucosynth: Generating inferentiiall--privat synthetic glucose traces. Advances in Neural Information Processing Systems, 36, 2024.
Imtiaz, S., Horchidan, S.-F., Abbas, Z., Arsalan, M., Chaudhry, H. N.. and Vlassov, V. Privacy preserving time-series forecasting of user health data streams. In 2020 IEEE International Conference on Big Data (Big Data), pp. 1428-3437, 2020.
Lana, I., Del Ser, J., Velez, M., and Vlahogianni, Road traffic forecasting: Recent advances and new challenges. IEEE Intelligent Transportation Systems Magazine, 10 (2):93-109, 2018.
Januschowski, T., Gasthaus, J., Wang, Y., Salinas, D., M., and Callot, I.. Cri-
Flunkert, V., teria for classifying forecasting methods. International Journal of Forecasting. 36(1):167-177, 2020.
Lebeda, C. J., Regehr, M., Kamath, G., and Steinke, T. Avoiding pitfalls for privacy accounting of subsam- pled mechanisms under composition. arXiv preprint arXiv:2405.20769 2024.
Jiang, Y., Luo, X., Yang, Y., and Xiao, X. Calibrating noise for group privacy in subsampled mechanisms. In Interna- tional Conference on Very Large Data Bases, 2025.
Lee, S. and Søgaard. A. Private meeting summarization without performance loss. In Proceedings of the 46th

---

Deep Differentially Private Time Series Forecasting
International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2282-2286, 2023.
Mueller, T. T., Usynin, D., Paetzold, J. C., Rueckert, D., and Kaissis, G. Sok: Differential privacy on graph-structured data. arXiv preprint arXiv: 2000::020000 2022.
Li, H., Xiong. L., Jiang, X., and Liu, Differentially private histogram publication for dynamic datasets: an adaptive sampling approach. In Proceedings of the 24th ACM International on Conference Information and Knowl- edge Management, CIKM 15, pp. 1001-1010, 2015.
Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Pro- ceedings of the Thirly-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, pp. 75-84, 2007.
Pan, K., Ong, Y.-S., Gong, M., Li, H., Qin, K., and Gao, Y. Differential privacy in deep learning: A literature survey. Neurocomputing, pp. 127663, 2024.
Li, X., Li, Y., Yang, H., Yang, L.., and Liu, X.-Y. Dp-Istm: Differential privacy-inspired lstm for stock prediction using financial news. arXiv preprint 2019.
Papernot, N., Abadi, M., Erlingsson, U., Goodfellow, I., and Talwar, K. Semi-supervised knowledge transfer for deep learning from private training data. In International Conference on Learning Representations, 2017.
Li, X., Cao, Y.,, and Yoshikawa, M. Locally private stream- ing data release with shuffling and subsampling. In 2023 IEEE 39th International Conference Data Engineering Workshops (ICDEW), pp. 125-131, 2023.
Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z.., Denison, C., McMahan, H. B., Vassilvitskii, S., Chien, S., and Thakurta, A. G. How to dp-fy ml: practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 11:1113-12011 2023.
Liu, B., Ding, M., Shaham, S., Rahayu, W., Farokhi, F., and Lin,2 Z. When machine learning meets privacy: A survey and outlook. ACM Computing Surveys (CSUR), 54(2): 1-36, 2021.
Ramaswamy, S., Thakkar, O., Mathews, R., Andrew, G., McMahan, H. B., and Beaufays, F, Training production language models without memorizing user data. arXiv preprint arXiv: 10031, 2020.
Liu, Y. Hu, T., Zhang, H., Wu, H., Wang, S., Ma, L.., and Long, M. itransformer: Inverted transformers are effective for time series forecasting. In International Conference on Learning Representations, 2024.
Rasul, K., Sheikh, A.-S., Schuster, I., Bergmann, U. M., and Vollgraf, R. Multivariate probabilistic time series forecast- ing via conditioned normalizing flows. In International Conference on Learning Representations, 2021.
Mao, Y., Ye, Q., Wang, Q., and Hu, H. Differential privacy for time series: A survey, IEEE Data Eng. Bull., 47(2): 67-92, 2024.
McMahan, H. B., Ramage, D., Talwar, K., and Zhang, L.. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Rigaki, M. and Garcia, S. A survey of privacy attacks in machine learning. ACM Computing Surveys, 56(4):1-34, 2023.
Roch, S. Modern Discrete Probability: An Essential Toolkit. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2024. doi:
McSherry, F. D. Privacy integrated queries: an extensible data analysis. In Proceed-
platform for ings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 19-30, 2009.
Salinas, D., Flunkert, V., Gasthaus, J., and Januschowski, T. Deepar: Probabilistic forecasting with autoregressive recurrent networks. International journal of forecasinng, 36(3):1181-1191, 2020.
Meiser, S. and Mohammadi, E. Tight on budget? tight bounds for r-fold approximate diffcrential privacy. In Pro- ceedings of the ACM SIGSAC Conference on Computer and Communications Security. pp. 247-264, 2018
Schuchardt, J., Stoian, M., Kosmala, A., and Günnemann, S. Unified mechanism-specifff amplification by subsam- pling and group privacy amplification. In Advances in Neural Information Processing Systems, 2024.
Mercier, D., Lucieri, A., Munir, M., Dengel, A., and Ahmed, machine learning in
S. Evaluating critical infrastructures: case study on time-series clas- sification. JEEE Transactions on Industrial Informatics, 18(1) 18(11):7834-742, 2021.
Shchur, O., Turkmen, A. C., Erickson, N., Shen, H., Shirkov, A., Hu, T., and Wang, B. Autogluon-timessrree Automl for probabilistic time series forecasting. International Conference on Automated Machine Learning, pp. 9-1. PMLR, 2023.
Mironov, I. Rényi differential privacy. In IEEE 30th com- puter security foundations symposium (CSF), pp. 263- 275, 2017.
12

---

Deep Differentially Private Time Scries Forecasting
Shi, E., Chan, H., Rieffel, E., Chow, R., and Song, D. Frivacy-presevvve aggregation of time-series data. In An- nual Network & Distributed System Security Symposium (NDSS). Internet Society.. 2011.
A., Zhao, J., Cormode, G., and Mironov, I. Opacus: User- friendly differential privacy library in PyTorch. arXiv preprint Stf:::000.112966 2021.
Yue, X., Inan, H., Li, X., Kumar, G., McAnallen, J., Shajari, H., Sun, H., Levitan, D., and Sim, R. Synthetic text gen- eration with differential privacy: A simple and practical recipe. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 1321-1342, 2023.
Sommer, D. M., Meiser, S., and Mohammadi, E. Privacy loss classes: The central limit theorem in differential privacy, Proceedings on Privacy Enhancing Technologies, 2019(2)225--26,, 2019.
Song. S., Chaudhuri, K., and Sarwate, A. D. Stochastic gra- dient descent with differentially private updates. In IEEE global conference on signal and information processing, pp.
Yue, Z., Ding, S., Zhao, L., Zhang, Y., Cao, Z., Tanveer, M., Jolfaci, A., and Zheng, X. Frivacy-preserving time-series medical images analysis using a hybrid deep learning framework. ACM Trans. Internet Technol., 21(3), June 2021. ISSN 1533-5399.
2013.
Torfi, A., Fox, E. A., and Reddy, C. K. Differentially private synthetic medical data generation using convolutional gans. Information Sciences, 586:485-500. 2022.
Zeng, A., Chen, M., Zhang, L., and Xu, Q. Are transformers effective for time series forecasting? In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 11121-11 128, 2023.
Villani, C. Optimal Transport. Springer Berlin Heidelberg, 2009. ISBN 9783540710509
Wang. Q.. Zhang, Y., Lu, X., Wang, Z., Qin, Z., and Ren, K. Rescuedp: Real-time spatio-temporal crowd-sourced data publishing with differential privacy. In IEEE INFOCOM 2016 The 35th Annual IEEE International Conference Computer Communications, pp. 1-9, 2016.
Zhang, J., Liang, X., Zhang, Z., He, S., and Shi, Z. Re- dpoctor: Real-time health data releasing with w-day dif- ferential privacy. In GLOBECOM 2017 2017 IEEE Global Communications Conference, pp. 1-6, 2017.
Zhang, X., Khalili, M. M., and Liu, M. Differentially private real-time release of sequential data. ACM Transactions on Privacy and Security, 26( 26(1):1 1-:1-99, 2022.
Wang, S., Rudolph, C., Nepal, S., Grobler, M., and Chen, S. Part-gan: Privacy-preserving time-series sharing. In Ar- tificial Neural Networks and Machine Learning-ICAN ICANN 2020: 29th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 15-18, 2020, Proceedings, Part 1 29, pp. 578-593. Springer, 2020a.
Zhu, Y., Dong, J., and Wang. Y.-X. Optimal accounting of differential privacy via characteristic function. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 4782-4817 2022.
Wang, Y.-X., Balle, B., and Kasiviswanathan, S. P. Subsam- pled rényi differential privacy and analytical moments accountant, In The 22nd International Conference on Ar- tificial Intelligence and Statistics. pp. 1226-1235, 2019.
Wang, Z., Liu, W., Pang, X., Ren, J., Liu, Z., and Chen, Y. Towards pattern-aware privacy-preserving real-time data collection. In IEEE INFOCOM 2020 JEEE Conference Computer Communicutions, pp. 109-118, 2020b.
Wunderlich, D., Bernau, D., Aldà, F., Parra-Arnau, J., and Strufe, T. On the privacy-utility trade-off in differentially private hierarchical text classification. Applied Sciences, 12(21):11177, 2022.
Ye, J. and Shokri, R. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022.
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj.
13

---

Deep Differentially Private Time Series Forecasting
A. Additional Related Work
Below we discuss additional related work in differential privacy and sequential data, and how our work differentiates from them. Note that there are works on privacy for time series outside differential privacy such as (Falcetta & Roveri, 2022; Yue et al., 2021; Shi et al., 2011) that use homomorphic encryption, but that is outside the scope of our paper.
A.1. Differentially Private Time Series Release
Publishing sanitized time series data has been the most studied application of differential privacy to temporally structured data. Most often, the goal is to release event-level differentially private time series, which are often an aggregate statistic of multiple private time series (Shi al., 2011; Fan & Xiong, 2014; Wang al., 2016; 2020b; Zhang et al., 2017; Fioretto & Van Hentenryck, 2019; Kellaris et al., 2014; Mao et al., 2024; Katsomallos et al., 2019). The high level approach in most of the mentioned works is to sample a subset of time steps, add noise, and use these samples to impute missing time steps. Here, sampling helps in improving utility by using the fact that they do not add noise to all data points. However, the sampling is not used for reducing the sensitivity, i... privacy amplification. Variants of this method include adaptive sampling based on an error estimate (Fan & Xiong, 2014), releasing DP time series over infinite time horizon (Kellaris et al., 2014), and releasing histograms only when there has been a significant change (Li et al., 2015). Zhang al. (2022) uses learned autocorrelation in the data instead of subsampling to publish sanitized time series under continual observation.
The fundamental difference between this class of work and our paper is that we are interested in training models in a DP manner rather than publishing sanitized data, and the fact that we subsample for the sake of privacy amplification.
A.2. DP-SGD for NLP/LLMS
Time series data and text data are similar in their temporal structure, and for that we give an overview of most relevant works on differential privacy in natural language models and LLMs. Perhaps the best starting point is Table I in (Hu et al., 2024), which lists over two dozen works that applied gradient perturbation (DP-SGD) for differentially private training in NLP. All of these works are categorized as providing sample-level or user-level privacy (not to be confused with user-level privacy in time series). That is, they consider natural language datasets as an unstructured set of atomic objects. Works that explicitly consider the sequential structure within these objects (categorized as token-, word-, or sentence-private exclusively use random input perturbations ensemble-basee methods. Of course, this does not in any way mean that the resultant privacy guarantees are invalid or too pessimistic (under their considered neighboring relation).
These works include, for example, DP-SGD fine-tuning of LLMs (Yue et al., 2023; Carranza et al., 2024; Lee & Søgaard, 2023; Wunderlich et al., 2022). There are also various works on DP federated learning for natural language learning models (McMahan et al., 2018; Ramaswamy et al., 2020). See (Hu et al., 2024) for a broader overview.
Bi-Level Subsampling for LLMs Charles al. (2024) and (Chua et al., 2024) both consider two specific algorithms for differentially private training in a setting where N data holders each have an arbitrary number of records and one wants to ensure privacy for insertion removal of data holder. These two algorithms are referred to OP-SGD-ELS and DP-SGD-ULS by (Charles et al., 2024) and "Group Privacy" and "User-wise DP-SGD" by (Chua et al., 2024). In DP-SGD-ELS, one randomly samples fixed number GELS of samples to construct new composite dataset of N K records. This reduces the problem of fine-tuning with user-level privacy to that of DPDSGD training with group privacy (Ganesh, 2024). In DP-SGD-ULS, one randomly samples a variable-sized set of users U via Poisson sampling. For each user in U, one then randomly samples GULS records, computes an average per-user gradient, clips the per-user gradient, accumulates them, and adds noise. This reduces the problem of fine-tuning with user-level privacy to that of standard DP-SGD training, where one user behaves like one record in standard DP-SGD. Importantly, the sampling of records from users only serves to bound their number to GELS or GUL.S. Equivalently, one could use a deterministic procedure that returns the first GELS or GULS records of each user. Using our terminology, these works do not analyze any form of amplification attained via the randomness in their bottom-level sampling procedure.
Note that this is not a limitation in the considered setting of Charles et al. (2024) and (Chua et al., 2024), as one has to make the worst case assumption that each inserted user has arbitrary worst-case records. Our results on top- and bottom-level subsampling instead correspond to what is essentially user-level privacy where we have a fixed number of users N users, and Le + LE records of single user are substituted, meaning there is some chance of accessing non-substituted records.
14

---

Deep Differentially Private Time Series Forecasting
B. Experimental Setup
B.1. Datasets
We use the traffic, electricity, and solar.10.minuter dataset as originally preprocessed by (Lai et al., 2018). We use the standard train-test splits as per GluonTS version 0.15.1 and additionally remove the last 5 Lp forecast windows of each train set sequence for validation.
Traffic. The traffic dataset was originally sourced from the following domain: http://pems..ot.ca.ggm It consists of hourly measurements from 862 traffic sensors, with each time series covering 17544 hours. The forecast length Lp is 24. Although our experiments are mostly focused on verifying that our differentially private models can fit some non-trivial time series, traffic data may allow inference about personal movement proflee (Giannotti & Pedreschi, 2008)
Electricity.
The electricity dataset was originally sourced from the following domain: wwt.su/ccccco////ttttt/teeeeteee
12014. It consists of hourly measurements from 321 electricity consumers, with each time series covering 26304 hours. The forecast length Lr is 24. As before, the contribution of this work is mainly theoretical and the specific application domain is mostly irrelevant. The electricity dataset just happens to be commonly used for testing whether models can fit non-trivial time series.
Solar. The solar_i 1.0 mm nutes dataset was originally sourced from the following domain: www.:./..ellooolrridsoooaaa
power-data. It consists of measurements per hour from 137 photovoltaic power plants, with each time series covering 52560 10-minute intervals. The forecast length Lp is 60.
B.2. Models
B.2.1. DEEP LEARNING MODELS
For all models, we use the standard hyper-parameters as per GluonTS version 0.15.1. Per forecast step, we let the model parameterize f-distribution for probabilistic forecasting. The only parameter we vary is the context length or the range of lagged values, as these affect our privacy analysis (see Appendix B.4.2). In particular, we use the following parameters per model:
Simple Feed Forward. We use two hidden layers with hidden dimension 64 and no batch normalization.
DeepAR. We use two hidden layers with hidden size 40, no dropout, no categorical embeddings, and activated target scaling,
iTrannformer. We use latent dimension 32, 4 attention heads, 128 feed-forward neurons, no droput, ReLU activations, 2 encoder layers, and activated mean scaling.
DLinear. We use hidden dimension 20 and kernel size 25.
B.2.2. TRADITIONAL BASELINES
Seasonal Naïve. We use season season length of 24 (1 day) for traffic and electricty. We use season length of 144 = 24 6 (1 day) for solar_1 1 0 mines
AutoETS. We use the standard implementation and parameters from statsforecast (Garza et al., 2022) version 1.7.8.
We additionally set the season lengths to the same values as with the seasonal naive predictor.
AutoARIMA with the standard implementation and parameters from statsforecast version 1.7.8. and with the above season lengths. However, the computation did not complete af- ter 7 days on an AMD EPYC 7542 processor with 256GB RAM on any of the datasets. Other works on time series forecasting also report "d.n.f." for AutoARIMA, e.g., (Alexandrov et al., 2019; Shchur et al., 2023). Without specifying season lengths, AutoARIMA had a CRPS of 0.472, 0.313, and 7.193 on the three datasets, i.e., it performed significantly worse than seasonal naive prediction or AutoETS with appropriate season lengths.
AutoARIMA. We attempted also
B.3. Metrics.
All experiments involving model training are repeated for 5 random seeds. We report means and standard deviation. As our training and validation loss, we use negative log likelihood.
15

---

Deep Differentially Private Time Series Forecasting
For evaluating predictive performance, the Continuous Ranked Probability Score (CRPS), which is proper scoring function (Gneiting & Raftery, 2007). Given cumulative distribution function F and ground-truth, y R, it is defined
CRPS(F = -1 /. (F(x) 1 2 y dr.
Like prior work, e.g., (Rasul et al., 2021; Chen et al., 2024; Kollovieh et al., 2024), and as implemented by default in Gluon'TS, we approximate using quantile levels (0.1,0.2..... ...2.......9). 0.9) ("Mean weighted quantile loss"). Note that this loss 0 for a Dirac-6 coinciding with ground-truth i.e., non- con-probabilistic models can also achieve loss of
B.4. Training
On all datasets, we train until reaching the prescribed privacy budget or some very liberally set maximum number of epochs that allows all models to train to convergence (details below). After training, we load the checkpoint with the lowest validation log-likelihood.
B.4.1. STANDARD TRAINING PARAMETERS
We ADAM with learning rate 10 and weight decay 10-* for all models and datasets. traffic, electricty, and 80l ar 0_mi nutes we train for 4000, 8000, and 16000 epochs, respectively.
B.4.2. DP TRAINING PARAMETERS
We wrap the optimizer and models using the privacy engine (minus the accountant) from opacus (Yousefpour et al., 2021) (version 1.5.1), replacing all recurrent and self-attention layers with their DP-compatible PyTorch-only implementation. Following (Ponomareva et al., 2023), we iteratively decreased the gradient clipping norm C until the validation loss without gradient noise increased, which led us using C 10-4 on all datasets.
Traffic. We use batch size A For DeepAR, we use the following lag indices, which contribute to the context length 5,, 2, 24, 27, 49, 71, 72, 73, 95, 96, 97, 119, 120, 121, 143, 144, 145, 167, 168, 169].
256, noise multiplier
4.0. and Le
4 Lp
Le:
Electricity, We use batch size = 128, noise multiplier o = 2.0, and Lc = 1 LF. For DeepAR, we use the following lag indices, which contribute to the context length Le: [1, 2,2,3,4,5, 6, 23, 25].
Solar: We
batch size A
4.0, and Le use the following lag indices, which contribute to the context length Lo
128. noise multiplier
LF.
For DeepAR, 11,2,3,4, 2,4,5, 5, 6, 23, 24, 25, 47, 48, 49, 71, 72, 73, 95, 96, 97, 119, 120, 121, 143, 144, 145, 167, 168, 169).
B.4.3. PRIVACY ACCOUNTING PARAMETERS
We use privacy loss distribution accounting as implemented in the the Google dp account i library (Google Differential Privacy Team, 2024) (version 0.4.4) with tail mass truncation constant of 10-15, We quantize privacy loss distributions using cconnect-the-dowt (Doroshenko et al., 2022) with value discretization interval of 10-3
16

---

Deep Differentially Private Time Series Forecasting
C. Additional Experiments
C.1. Trade-Offs in Structured Subsampling
C.I.I. NUMBER OF SUBSEQUENCES IN BI-LEVEL SAMPLING
In the following, we repeat our experiment from Fig. 2, where we wanted to determine whether we should use small À (many top-level sequences, few bottom-level subsequences) or large À (many top-level sequences, few bottom-level subsequences) for some given batch size A.
From Theorem 4.4 and Theorem F.7 know that tight upper bound and optimistie lower bounds only depend on Le and p [A X] N. Thus (up to modulo division), the parameter space is fully characterized by and I-L++I
batch-to-dataset size ratio x
In Figs. to 7, we thus keep N 320 and vary these two ratios between 0.5 (little amplification) and 0.1 (more amplification). In Fig. we observe that offers better privacy than for all E [10-3, 10 after 100 training steps. In Figs. 6 and 7, it already offers better privacy after 100 training steps. Again, this justifies our choice of in training models.
0.8
0.03
0.6
0.02
0.4
16
16
0.01
Tight upper bound
0.2
Tight upper hound
Lower bound
Lower bound
0.00
0.0
10
10
10-1
10
10a
10a
10a
10
10-2
10
10
10a
10a
10a
(a) Step
(b) Step 100
1.0
0.6
0.4
16
0.2
Tight upper bound
Lower bound
0.0
10
10-2
10
10
10!
10²
10a
E
(c) Step 1000
Figure 5: Top-level WOR and bottom-level WR sampling under varying number of subsequences. Little bottom-level amplification (r 0r-=033 0.5) and more top-level amplification (A N = 0.1).
17

---

Deep Differentially Private Time Series Forecasting
0.8
0.03
0.02
0.4
16
0.01
Tight upper bound
0.2
Tight upper bound
Lower bound
Lower hound
0.00
0.0
10
10
10
10"
10a
10a
10a
10
10
10-1
10a
101
10a
10a
6
(a) Step
(b) Step 100
0.8
0.6
0.4
16
0.2
Tight upper bound
Lower bound
0.0
10
10
10
10a
10a
10a
10a
c
(c) Step 1000
Figure 6: Top-level WOR and bottom-level WR sampling under varying number of subsequences. More bottom-level amplification (r = 0.1) and less top-level amplification (A N = 0.5).
18

---

Deep Differentially Private Time Series Forecasting
0.006
0.25
0.20
0.004
0.15
0.10
0.002
Tight upper bound
Tight upper bound
0.05
Lower bound
Lower bound
0.000
0.00
10
10
10
10
10a
10a
10a
10
10
10
10"
10a
10a
10a
(a) Step
(b) Step 100
0.6
0.4
Tight upper bound
Lower bound
0.0
10
10
10
10a
10
10a
10a
e
(c) Step 1000
Figure 7: Top-level WOR and bottom-level WR sampling under varying number of subsequences. Both significant bottom- level amplification (r = 0.1) and top-level amplification (A N 0.1).
19

---

Deep Differentially Private Time Scries Forecasting
C.1.2. STEP- VS LEOCH-LEVEL ACCOUNTING
In this section, we repeat our experiment from Fig. 3 demonstrate the benefit of top-level sampling sequences (Theorem 4.4) instead of deterministically iterating over them (Theorem 4.2), even though we risk privacy leakage every training step.
Like in Appendix C.I.1, we observe that the deterministic-oo-lleaa guarantee is only dependent on r LotLe and that L-Lx+11
the WOR-top-level guarantee is only dependent on and [A ^j N.
As before, we thus keep dataset size N = 320 and vary r and batch-to-dataset size ratio A between 0.5 and 0.1 (see Fig. 8). N In all cases, sampling without replacement offers stronger privacy after step, epoch, and 10 epochs.
Deterministic
Deterministic
0.8
Sampling (WOR)
0.8
Sampling (WOR)
0.4
0.4
Epoch 10
Epoch 10
0.2
Epoch
0.2
Epoch
Step
Step
0.0
0.0
10
10-2
10
10
10
10a
10
3
10
10
10
10
10a
(a) = 0.5 and A / N = 0.5
(b)
0.5 and A / N = 0.1
0.4
Deterministic
0.4
Deterministic
Sampling (WOR)
Sampling (WOR)
0.3
0.3
0.2
Epoch 10
Epoch 10
0.1
Epoch
0.1
Epoch
Step
Step
0.0
0.0
10
10
10-1
10
10
10a
10
3
10-2
10 1
10
10
10a
(c) = 0.1 and / N = 0.5
(d)
0.1 and A 0.1
Figure 8: Top-level deterministic iteration (Theorem 4.2) vs top-level WOR sampling (Theorem 4.4) for À We vary r= (Le + Lr) (I. Lp 1) and / N, with smaller values corresponding bottom- and top-level amplification, respectively.
20

---

Deep Differentially Private Time Scries Forecasting
C.1.3. AMPLIFICATION BY LABEL PERTURBATION
In this section, we repeat our experiment from Fig. where we consider top-level WOR and bottom-level WOR sampling, and vary label noise standard deviation oF E RR, illustrate how test-time data augmentations (i.e. continuous-valus valued subsampling) can amplify privacy (Theorem G.1) in self-supervised training of sequence models.
Just like in Appendix C.I, we observe that the privacy guarantee, for fixed forecast-to-context ratio on Lethe L-Lr+1 and p | /AJ/ / N.
La is only dependent
Le
As before, we thus keep dataset size N = 320 and vary and batch-to-dataset size ratio A between 0.5 and 0.1 (see Fig. 9). In all cases, letting OF + oo is equívalent to setting forecast length LF to O.
FF
F
0.15
0.03
0.0
0.0
0.5
0.5
0.10
1.0
0.02
1.0
2.0
2.0
5.0
5.0
0.05
0.01
Le 60, LF
30
Le
60, LF
30
Le = 60, Lp =
Le = 60, Lp 0
0.00
0.00
10
10-2
10
100
10
10a
10
10-2
10
100
10
102
(a) = 0.5 and A / N = 0.5
(b)
0.5 and A N = 0.1
0.03
OF
0.006
OF
0.0
0.0
0.5
0.5
8(c)
0.02
1.0
0.004
1.0
2.0
2.0
5.0
0.002
Le 60, 30
60, Lr
30
Le = 60, LF =0
Lc 60, LF
0
0.00
0.000
10 3
10
10
10
10a 10a
10
10-2
10
109
10a
10a
(c) r = 0.1 and A / N = 0.5
(d) r = 0.1 and A N = 0.1
Figure 9: Varying label noise of for top-level WOR and bottom-level WR (Theorem G.I) with oc 0, = 1. We additionally vary r = (Lo + LF) / (L LF + 1) and A A N, with smaller values corresponding to more bottom- and top-level amplification, respectively.
21

---

Deep Differentially Private Time Scries Forecasting
C.1.4. EPOCH PRIVACY LENGTH
This experiment differs from the previous ones in that we exclusively focus on top-level deterministic iteration and bottom- level sampling with replacement (see Theorem 4.2). Recall from discussion in Section 4.1 that 1 minimizes the privacy of each epoch, but forces to perform & times many epochs for the same number of training steps as À k. Thus, there are more chances for privacy leakage and we need to self-compose the privacy profile for À exactly k times more often.
In the following, we demonstrate that composing many epochs that are more private (i.c., À 1) can nevertheless be beneficial. To this end, we fix dataset size N 320 and (to eliminate one redundant degree of freedom) batch size A 320. With this parameterization, self-compose epoch-level mechanism 16 times for X 1, 8 times for X 2, 4 times for À = 4 etc. to determine privacy for the same number of training steps. We additionally vary the amount of bottom-level amplification by varying Lo+Le between 0.5 and 0.1.
means that we perform & training steps in single epoch. For our comparison,
thus
L-L+41
As can be seen in Fig. 10, the number of sequences = offers smaller (() at every training step that coincides with an epoch 1.
To conclude, choosing number of subsequences remains the preferred option (see also Theorem 4.1) even under composition.
1.0
1.0
0.8
0.8
0.6
0.6
0.4
16
0.4
16
0.2
Tight upper bound
0.2
Tight upper bound
Lower bound
Lower bound
0.0
0.0
0
12
16
4
12
16
Training step
Training step
(a) 1 and 0.5
(b) and 0.5
1.0
1.0
Tight upper bound
Tight upper bound Lower bound
0.8
Lower bound
0.8
0.6
0.6
6(c)
0.4
16
0.4
16
0.2
0.2
0.0
x
0.0 Ι
0
4
12
16
4
12
16
Training step
Training step
(c) and 0.1
(d) and 0.1
Figure 10: Privacy parameter 8(s) for (1,4) over the course of 16 training steps when using top-level deterministic iteration and bottom-level sampling with replacement (Theorem 4.2). We additionally vary r between 0.5 (less bottom-level amplification) and 0.1 (more bottom-level amplification).
22

---

Deep Differentially Private Time Scries Forecasting
C.2. Application to Probabilistic Forecasting
C.2.1. EVENT-LEVEL PRIVACY
Tables 2 to show average CRPS after 1-event-level private training on our three standard benchmark datasets. Since 8-1 is approximately equal or greater than the dataset sizes, e S 1 indicates strong privacy guarantees, whereas 2 S S 8 would be more commonly expected values in private training of machine learning models (Ponomareva et al., 2023).
For full description of all hyper parameters, see Appendix B.
In cases, at least one model outperforms the traditional baselines without noise for all considered E.
Table 2: Average CRPS on traffic for 1-event-level privacy and ā = 10-7 Seasonal, AutoETSS, and models with 0o are without noise. Bold font indicates the best predictor per
MODEL
0.25
= 0.5
8
SIMPLEFF
0.252 +0.007
0.207
#0.002
0.195
#0.003
0.193
+-0,003
0.194
40.002
0.193
+0.003
0.136 400001
DEEPAR
0,262
0.157
0.145
$0.001
0.142
0.141
40.002
0.141
0.124
40.0.001
ITRANSF.
0,260
+0.008
0.211
20.004
0.193
#0.003
0,188
+0.004
0.188
#0.004
0.188
#0.004
0.135
#00001
DLINEAR
0.236
10.006
0.204
20. 004
0.192
10.001
0.188
10.005
0.188
00.000
0.188
2:.000 003
0.140
100000
SEASONAL
0.251
0.251
0.251
0.251
0.251
0.251
0.251
AUTOETS
0.407
0.407
0.407
0.407
0.407
0.407
0.407
Table 3: Average CRPS e electricity for 1or1-ewee 1-event-level privacy and ó 10-7 Seasonal, AutoETS, and models with are without noise. Bold font indicates the best predictor per
MODEL
= 0.25
0.5
E 2
OC
SIMPLEFF
0,087 :0.002
0.072
10.001
0.065
100001 00.001
0.065
400.001
0.065
10.001
0.065
#:0002
0.058
20.001
DEEPAR
0.121 20.014
0.071
#0.004
0.070
20.004
0.068
20.005
0.067
20.004
0.068
20.005
0.058
10.002
ITRANSE.
0.107 20.004
0.081
10.005
0.075
20.002
0.074
20.002
0.074
10.002
0.074
20.002
0.058 20.001
DLINEAR
0.076
20.003
0.064
10.000
0.061
10.001
0.061
20.001
0.061
10.001
0.061
10.001
0.059 10.000
SEASONAL
0.070
0.070
0.070
0.070
0.070
0.070
0.070
AUTOETS
0.064
0.064
0.064
0.064
0.064
0.064
0.064
Table 4: Average CRPS on solau ar-10 O_minutes for 1-event-level privacy and 5 = 10-7. Seasonal, AutoETS, and models with = do are without noise. Bold font indicates the best predictor per
MODEL
== 0.25
0.5
2=1
== 2
4
E 8
SIMPLEFF
1.108
1.114
40.043
1.114
1.114
1.118
40.038
1.113 #0.028
0.766
DEEPAR
0.910
20.017
0.820
40.030
0.803
t0.023
0.792
20.016
0.787
40.023
0.787
40.023
0.654
20.654
ITRANSE.
1.134 15.057
0.977
1.00065
0.956
10.062
0.975
10.066
0.974
10.065
0.974 1.0065
0.804 1:0.84
DLINEAR
1.434 17.073
1.287
1.0.222
1.152
10.201
1.110
10.145
1.048
14.143
1.051
1:0
0.860 1:0.
SEASONAL
1.120
1.120
1.120
1.120
1.120
1.120
1.120
AUTOETS
6.494
6.494
6.494
6.494
6.494
6.494
6.494
23

---

Deep Differentially Private Time Scries Forecasting
C.2.2. W-EVENT AND W- W-USER-LEVER PRIVACY
As discussed in Appendix we can (for sufficiently long sequences) generalize our bounds on the mechanism's 's privacy profile from 1-event- to w-event- w-useerllvel privacy by replacing any occurrence of Le LF with Le LF + w ( Lp). Since w' w'evven- and w-user-level privacy lead to identical results for some sufficiently large w', is sufficient to experiment with w-user-level privacy.
For full description of all hyper parameters, see Appendix B.
Tables to 7 show average CRPS after w-user-level private training on our three standard benchmark datasets.
Except for traffic and w 8 (which, by the above argument and choice of Le and Lr, is equivalent requiring privacy for event spanning multiple days in our hourly datasets), at least one model outperforms the traditional baselines without noise for all considered
Table 5: Average CRPS on traffic c for w-user-level privacy and & = 4, 5 = 10-2. Seasonal and AutoETS are without noise. Bold font indicates the best predictor per w.
MODEL
1 1
W
4
W = 8
SIMPLEFF
0.193 10.003
0.194
10.003
0.194
10.003
0.211 100001
DEEPAR
0.142
1..003
0.143
10.001
0.145
10.001
0.166 10.004
ITRANSE.
0.188 10.004
0.188
0.193
0,217
DI.NNAR
0.189
0.189
20.003
0.192
40.0m
0.208
#0.004
SEASONAL
0.251
0.251
0.251
0,251
AUTOETS
0.407
0.407
0.407
0.407
Table 6: Average CRPS on electricity for w-user-level privacy and E = 4, 8 = 10-? Seasonal and AutoETS are without noise. Bold font indicates the best predictor per w.
MODEL
2
8
SIMPLEFF
0.064 +0.001
0.065
20.001
0.064
#0.001
0.074 +0.001
DEEPAR
0.068
10.005
0.069
0.068
100002
0.073
100003
ITRANSE.
0.075
10.003
0.074
10.002
0.075
1: 003
0.083
1:0004
DLINEAR
0.061
10.001
0.061
10.001
0.061
10.001
0.066
1:0001
SEASONAL
0.070
0.070
0.070
0.070
AUTOETS
0.064
0.064
0.064
0.064
Table 7: Average CRPS on solar _10 mi muntes for w-user-level privacy and 4, 8 10-7. Seasonal and AutoETS are without noise. Bold font indicates the best predictor per
MODEL
10
SIMPLEFF
1.113
1.116
1.110 40.042
1.107
DEEPAR
0.783
10.019
0.791
20.018
0.807
20.024
0.823
1:0026
ITRANSE.
0.951
10.061
0.950
40.062
0.956
40.062
0.980 1:00600
DLINEAR
1.072
10.164
1.122
10 158
1.200
2:0
1.298 1:0.00
SEASONAL
1.120
1.120
1.120
1.120
AUTOETS
6.494
6.494
6.494
6.494
24

---

Deep Differentially Private Time Series Forecasting
C.2.3. AMPLIFICATION BY LABEL PERTURBATION
Finally, can demonstrate the potential benefit of using online data augmentations amplify privacy in training forecasting models (Theorem 4.5). Consider (w. evvent-leeel or (w, -user-leee privacy with sufficiently small If is sufficiently small compared the scale of the dataset, i.c., each individual only makes small contribution to the overall value of time series at each time step, then we can introduce substantial context and label noise and or to amplify privacy without significantly affecting utility. Simultaneously, we still benefit from amplification through top- and bottom-level subsampling, ie., do not need to add as much noise as would be required for directly making the entire input dataset privacy.
For full description of all hyper parameters, see Appendix
Tables 10 show average CRPS after (1, evvent-leel private training with 0.5, 6 10- i.e. strong privacy guarantees. Note that
different e per dataset, they have different scale.
We observe that, for all models and all datasets, the best score is attained with label noise scale = 2 or OF = 2. This confirms that there a scenarios in which our novel implification-hy-aggeeentt guarantees can help improve the privacy-utility trade-off of forecasting models.
Table 8: Average CRPS on traffic for (1, 0.001) useer-leell privacy and ε = 0.5, d = 10-?. Seasonal and AutoETS are without noise. Bold font indicates the best label noise scale op per model, i.e., per row.
MODEL
0
OF
=
OF
SIMPLEFF 0.207 +0.002
0.205 #0.002
0.205
#0.002
0.205
#0.001
DEEPAR
0.156
10.003
0.156
0.156
1: 003
0.154
1: 002
ITRANSE.
0.211
1:0004
0.208
10.004
0.205
1:00000 0.0.000
0.204
1: 10.003 003
DLINEAR
0.203
10.003
0.202
10.003
0.202
1:0003
0.203 10.003
SEASONAL
0.251
0.251
0.251
0.251
AUTOETS
0.407
0.407
0,407
0.407
Table 9: Average CRPS electricity for (1, usseereveel privacy and 0.5, 8 = 10 Seasonal and AutoETS are without noise. Bold font indicates the best label noise scale o per model, i.e., per row.
MODEL
OF
OF
OF
OF
SIMPLEFF
0.072
0.069
0.068
0.067
DEEPAR
0.071
40.006
0.074
20 005
0.069 20.005
0.067 20.005
ITRANSE.
0.081
10.005
0.080
20 004
0.080 20.005
0.080 20.004
DLINEAR
0.064
10.000
0.062
10 000
0.061 10.001
0.061 10.001
SEASONAL
0.070
0.070
0.070
0.070
AUTOETS
0.064
0.064
0.064
0.064
Table 10: Average CRPS on solar 10. minutes for (1, uusereeel privacy and 0.5, d 10-?, Scasonal and AutoETS without noise. Bold font indicates the best label noise scale oF per model, i.e., per
MODEL.
OF
OF
Or 2
OF
SIMPLEFF
1.117 40.034
1.126 40.046
1.117
40.042
1.119
10.011
DEEPAR
0.820
40.030
0.818
40.028
0.814
#0.027
0.813
#0.026
ITRANSE.
0.976
+0.064
0.970
20.062
0.960
20.032
0.959
20.056
DLINEAR
1.282
10.21
1.245
20.20 232
1.238
10.240
1.246
20.227
SEASONAL
1.120
1.120
1.120
1.120
AUTOETS
6.494
6.494
6.494
6.494
25

---

Deep Differentially Private Time Scries Forecasting
C.2.4. EFFECT OF SUBSAMPLING PARAMETERS NON-PRIVATE UTILITY
In all of our experiments on probabilistic forecasting, used top-level sampling without replacement, bottom-level sampling with replacement, and À = 1 subsequence per sequence. This choice of subsampling scheme based observation that (1) top-level sampling without replacement yiclds stronger privacy than deterministic iteration despite requiring multiple compositions per epoch (see Figs. 2 and 3), and that (2) À yields stronger privacy under composition.
However, it could be that other parameterizations offer much better utility that could potentially outweigh their weaker privacy. Alternatielyy, could be that the models only achieve a good privacy-utility trade-off because our specific choice of parametermization leads massive improvement in utility compared other parameterizations.
To provide evidence against these two hypotheses, evaluate the utility of the four different model architectures under different subsampling schemes when performing standard. non-DP training the traffic dataset. Non-DP training is equivalent to using clipping constant C - oc, noise scale a + 0, and privacy budget - co. All parameters that are not being varied are identical to our previous experiments (see also Appendix B).
In Fig. 11, we fix = as in our other experiments, and vary both the batch size E {16, 32, 64, 128} and the top-level sampling scheme, addition to deterministic iteration and sampling without replacement, we also evaluate iteration over a random permutation of the sequences. As can be seen, neither the batch size nor the top-level scheme has any significant effect utility. In Fig. 12, fix batch size A 256 in other experiments, and vary the number of subsequences À E (1, 2, 4, 8, 16} and the top-level sampling scheme. Again, there is no significant effect model utility.
It can be concluded that the good privacy-utility trade-off attained in private training is not simply due to a massive increase in utility caused by our chosen subsampling parameters.
SimpleFeedForward
DLinear
0.125
0.125
0.100
0.100
CRPS
CRPS
0.075
0.075
0.050
Itcration
0.050
Iteration Shuffling WOR
Shuffling
0.025
0.025
WOR
0.000
0.000
16
32
64
128
16
32
641
128
Batch size A
Batch size A
DeepAR
ITransformer
0.125
0.125
0.100
0.100
CRPS
0.075
CRPS
0.075
0.050
Iteration
0.050
Iteration
0.025
Shufflng
0.025
Shufflig
WOR
WOR
0.000
0.000
16
32
64
128
16
32
64
128
Batch size A
Batch size A
Figure 11: Average CRPS on traffic for non-DP training with X = under varying top-level scheme and batch size A.
26

---

Deep Differentially Private Time Series Forecasting
SinplereeedFowward
DLinear
0.125
0.125
0.100
0.100
CRPS
CRPS
0.075
0.075
0.050
Iteration Shuffling WOR
0.050
Iteration Shuffling WOR
0.025
0.025
0.000
0.000
Subsequences DeepAR
Subsequences À
ITrrnsformer
0.125
0.125
0.100
0.100
CRPS
CRPS
0.075
0.075
0.050
Tteration
0.050
Iheration
Shuffling
Shuffling
0.025
0.025
WOR
WOR.
0.000
0.000
8
16
Subsequences
Subsequences X
Figure 12: Average CRPS on traffic for non-DP training with batch size 256 under varying top-level scheme and number of subsequences X.
27

---

Deep Differentially Private Time Series Forecasting
C.3. Comparison to Standard DP-SGD
Our analysis focuses on the batching procedure in Fig. in which one first selects set of sequences ("top-level sampling") and then selects subsequences from these specific sequences ("bottom-leeel sampling") to generate a batch of size A. However, could in principle also accumulate all possible subsequences of all sequences from timeseries dataset C R2 with |z]| = N into one large dataset ă _ LC++ of size |ar| Ntotal N (L Lp + +1). Once this dataset is constructed, one could sample batches of size A using a standard subsampling distribution (e.g., sampling uniformly at random). Such a batching approach is, for example, implemented in the Darts forecasting library (Herzen et al., 2022). After this dataset is constructed, one could directly train models via existing implementations of DP-SGD.
However, one must not directly apply the privacy guarantees provided by existing implementations because they assume individual-level modifications of the dataset: For substitution relation 3 = H', which indicates that there is pair of records E F, d' & I such that F' F \ {a} U {a'), the privacy profile of DP-SGD when sampling batch of size A uniformly without replacement can be tightly characterized as follows (Zhu et al., 2022):
Proposition C.1. Consider datasets of size Neotal and subsumpling without replucement with batch size A S Niotal- Let: r = Nuoial be the probability of sampling a subsequence containing any specific element. Define P(L) =
A_
(M.(H.)))) with means μ [0 2)" and weights p [1-r r)". Further, define per-step privacy profile H (a) = s Ha HaMMal|)p Then,
((o) [H((P())IN(OOO)) if (.((O).))P((1) f05a<1.
But for event-level neighboring time series datasets x R x', there are up to Le + LF subsequences that contain the sensitive element. Thus, the constructed datasets ã, would differ in up to Lo + LF records. More formally, they would be neighboring under Lc + Luususssttttionn relation SLe+Ly Lr. H' which indicates that there is a subset g S # with lgl La LF and subset g' n = 0 with Ig'I Lo + LF such that स' ã \ U g'. Using an analogous construction to Theorem 4.3, one easily show that the privacy profile is optimistically lower- bounded as follows:
Proposition C.2. Consider datasets of size Nioia and subsampling without replacement with batch size A S NNiotal- Define P(A)= MoG p, with means μa No Nhottrtt and weights p [0, 1| with μ4 = 2(i - 1) and Pa Hypergeom(i Nental, Le + A). Further, define per-epoch privacy profile H(a) suPsznctep.ar Ho (M, (M..)........................M Then,
H(a) (.(P())))()OO)) if
(I((())))IP((A)) fo
In short: When applied to dataset of subsequences å C RLo+LE constructed from time series dataset x C R DP-SGD is less private than the standard privacy guarantee would suggest. This is because there is chance of including multiple subsequences with sensitive information, which will cause more privacy leakage, as is indicated by the mixture components with larger mean.
In contrast, structured subsampling as shown in Fig. I lets us control the maximum number of times that a sensitive element can appear in a batch. In particular, sampling one subsequence per sequence (A 1) ensures that a sensitive element appears most once. In Fig. 13, we compare the optimistic lower bound from Proposition C.2 to the upper bound for structured subsampling with À 1 from Theorem 4.4. Specifically, we evaluate the bounds for Nootal {10*, 10%), A E 10.1, 0.001), ). and Le + I. E (1,2,4,5 8, 16, 32) under varying a ef. Standard DP-SGD is less private than structured subsampling with À= = 1 for larger subsequence lengths LC + Lp.
Nestal
28

---

Deep Differentially Private Time Series Forecasting
1.0
Structured Subsampling
Lc + LF
Structured Subsampling
Lc + LF
Standard DP-SGD
1
Standard DP-SGD
1
2
4
4
8
8
16
16
32
32
0.0
100
200
400
100
200
400
E
6
(a) Ntotal 10" and Ntotal 0.1
(b) Nootal 10 and A Nootal 0.1
0.5
0.5
Structured Subsampling
Lo
LF
Structured Subsampling
Lo
LF
0.4
Standard DP-SGD
0.4
Standard DP-SGD
2
0.3
0.3
0.2
16
0.2
16
32
32
0.1
0.1
0.0
0.0
3
3
C
C
Ntotal 10 and A Ntotal 0.001
Nsotal 10 and A Nootal 0.001
Figure 13: Comparison of optimistic lower bound for standard DP-SGD the tight upper bound for DP-SGD with structured subsampling and number of subsequences À under varying overall number of subsequences Ntotals batch size A, and subsequence length Lo + Lp. Standard DP-SGD, which first constructs a dataset of all possible subsequences and then samples without replacement, less private for larger Le + Lr.
29

---

Deep Differentially Private Time Scries Forecasting
D. Additional Background
In the following, we provide additional background information on the toolset we use to to derive amplification bounds for structured subsampling of time series, determine the corresponding dominating pairs, and perform privacy accounting.
We recommend reading this section before proceeding to derivations in Appendices E to G which rely the Lemmata introduced here.
D.1. Subsampling Analysis
Recall from Section 3 that goal in subsampling analysis is to determine the privacy of subsampled mechanism M B o S, where S X + Y is subsampling scheme that maps from dataset space X to a space of batches Y and Y + RD is base mechanism that maps these batches to outputs. Further recall that the hockey-stick divergence of output distributions Mr and Mg for pairs of datasets I, x, E X can be bounded via couplings:
Definition 3.4. A coupling I between distributions Sz, Sz of randomly sampled batches S(x), E is a joint distribution on Y2 whose marginals are S₂ and Sg'.
Lemma D.I. Consider subsampled mechanism M BoS and datasets x x'. Then, for any coupling of subsampling distributions Sz, Szy,
Ha (M < / Ha(ByllBy)) dt(,.
Proof. The proof is identical to that of Eq. 5 in (Balle al., 2018).
Balle al. (2018) demonstrated that this tool can be combined with the advanced joint convexity property of hockey-stick divergences to derive provably tight privacy guarantees for insertion, removal, substitution of single element in dataset:
Lemma D.2 (Advanced joint convexity). Consider mixture distributions P (1 P: pP2 and Q = (1 p) + pQ2 with P1 = Q and some w E [0, 1]. Given a 2 1, define a' = = 2-1 and ((a)) -. Then,
(a(lQ)) - H.r (Pa((1
B(a)
Proof. The proof is identical to that of Theorem 2 in (Balle et al., 2018). In notation, interchange a and a'.
More recently, Schuchardt al. (2024) demonstrated that, when considering insertion and/or removal of multiple elements ("group privacy"), tighter bounds can be obtained via couplings between multiple subsampling distributions.
Definition D.3. A coupling I between distributions Pı...., Px on Y is a distribution on Y with marginals PI...., PN-
Specifically, they propose to partition the support of subsampling distribution S₁, into events AI...,, A, and the support of subsampling distribution Sp, into events , E,, before defining a simultancous coupling between the corresponding conditional distributions. For example, these events can indicate the number of group elements that appear in random batches (xx) and S(z').
Lemma D.4. Consider subsampled mechanism M BoS and datasets = x', and let Sn and S.r denote the distribution of random batches S(z) and S(x'). Define two disjoint partitionings U A, supp(Sz) and Uن=1 E, supp( of the support of Sz and S. such that Vi Sx 0 and Vj (F,) > 0. Let r be a coupling belween the corresponding conditional subsampling distributions S_(-(Ar),.... A,),, (
(x S. Then, the hockey-stick
divergence between subsampled output distributions M₂ and M is bounded via
Lf J. (y (2) y))
H. (M <
with cost function ca : 4 x V + R2 defined by
(3) (2)) Haa
Σ
B 4
S(AD) Σ
BBg Se (A1)
(2)
1=1
1=1
30

---

Deep Differentially Private Time Series Forecasting
Proof. The proof is identical to that of Theorem 3.4 in (Schuchardt et al., 2024), since any distribution supported discrete, finite set has mass function.
While this bound is slightly more involved, it can be intuitively explained via comparison to Lemma D.I. In Lemma D.I, we couple subsampling distributions S₂ and 8 The resultant bound ís a weighted sum of divergences between base mechanism distributions By and By with batch y from the support of Sy and y' from the support of Sz. In Lemma D.4, we couple (-1E))
S (-1 Es). The resultant bound is a weighted sum of divergences between two mixtures. The components of these mixtures are base mechanism distributions B g and B (2) with batch V/ (1) from the support of (- A;) and batch y) (2) from the support of S.r(. EJ).
conditional subsampling distributions (-) A1), ,......-Se,, Sa (-IAA) and (-1,)) Sy
The benefit of this formulation is that it allows us to prove that mechanisms are dominated by mixture distributions, rather than individual distributions. This enables the derivation of tight dominating pairs in scenarios where there are multiple possible levels of privacy leakage, such as in Algorithm where single sensitive element can appear in 0, 1, or multiple subsequences within batch.
A problem with Eq. (2) is that it requires evaluating the base mechanism distribution B, for various batches y E Y, which may be defined by a complicated function, such as the noisy gradient descent update from Algorithm 2. Schuchardt et al. (2024) show that it can be sufficient to consider worst-case batches / ..... 01"' and g)()
0f that maximize the (2)
mixture divergences while retaining the pairwise distance between original batches v .......7 (1) and (2) :.]
(1)
Definition D.5 (Induced distance). Consider an arbitrary neighboring relation my on batch space Y. Then the corresponding induced distance d: Y² > N is a function such that d(y. v/) = implies that there is a sequence of batches yı, VK-1 such that y By V1, Vk: : yk =y yk+1, and æK =y y'.
Lemma D.6. Let d: Y² N be the distance induced by a symmetric neighboring relation my on batch space Y. Consider
the tuples of batches y 1) E Y and y E YY, as well as cost function ca from Eq. (2). Then,
() (2)) S
Ca (1) 9 g(2))
sup g0
subject to 7( E YYY, g(t) e y and
d(j) y/
(1)) S d(y) (1)
d() (1) ;( < d( y ())
Mu:1
d(!! (2) ; < d(y) y !)
Mtu:1
Proof. The proof is identical to that of Proposition 3.5 in (Schuchardt et al., 2024).
A particular form of this optimization problem, which we will encounter in our later derivations, arises from analyzing sensitivity- -ouunded Gaussian mechanisms. For specific set of constraints, it can be shown that the optimal solution is attained by a pair of univariate Lemma D.7. Consider standard deviation a E R and mixture weights (1 E [0, 1)' and (2) E [0, 1] Let be the set of all pairs of Gaussian mixtures (P, Q) with P = Σl w!""
mechanisms (recall Definition 3.3).
(1) -N(( (1) , I) and Q = ΣS w N(
(1) (2) , satisfying
11 = |1| = 0
|| [1(e) (1) ( 1112 S c. |t ul
Wlu: M
11 (2) (3 1|2 S c ul
121122
with some constant e R4. Then,
max (P,QQ) = Ha (MO ( wa) .0]| Mo MoG (2)x (2) (2) P.QEQ
with univariate means μ (1)+ (0
-I -))² and (2) (0
J J.
Proof. After scaling the standard deviation by e, the proof is identical to that of Theorem 0.7 in (Schuchardt et al., 2024).
31

---

Deep Differentially Private Time Series Forecasting
D.2. Dominating Pairs
In the following, we summarize multiple known results on dominating pairs due Zhu al. (2022) that we will need in our later derivations. Let begin by recalling the definition of dominating pairs:
Definition 3.2. Distributions (P. Q) are dominating pair for component mechanism M if sup Ha (Ma S (PIQ)) for all 2 0. If the bound holds with equality for all a 2 0, then (P, Q) a light dominating pair.
Further recall that a tight dominating pair is pair of distributions (P, Q) such that the bound in Definition 3.2 holds with equality. All mechanisms have tight dominating pairs:
Lemma D.8. Any mechanism M X P has light dominating pair of distributions, i.e, a pair of distributions (P, Q) such that sup (M
(PII)) for all 2 O.
Proof. This result is special case of Proposition 8 from (Zhu al., 2022) for real-valued outputs.
For privacy accounting, we will later need evaluate (P, Q) as function of a. Such functions are referred as privacy profiles (Zhu et al., 2022):
Definition D.9. A privacy profile is a function H R2 + R such that there exists a pair of distributions (P. with Va 0: Haa) Q).
Under symmetric neighboring relations (e.g. substitution of elements in a set), any privacy profile corresponding dominating pair enjoys symmetry that allows us focus many of our derivations
2 1:
Lemma D.10. Let be a symmetric neighboring relation on dataset space X. It then holds that sup (a(M)l| S Ha(P, Q) for all if and only if suppoar Ha(Ma)) s Ha(Q, P) for all 0 < a S 1.
Proof. This result corresponds to the third part of Lemma 31 from (Zhu et al., 2022).
Later on, we will use the following properties of privacy profiles in identifying dominating pairs:
Lemma D.11. A function H IR. - TR a privacy profile if and only if H convex, is decreasing, H()) = and (1 2 max - x, 0}.
Proof. This result, in combination with Definition D.9, corresponds to the first part of Lemma 9 in (Zhu al., 2022).
Furthermore, the following result shows that for the purpose of deriving dominating pairs, it is in principle sufficient to derive privacy profiles:?
Lemma D.12. Let H RRR-- - be a privacy profile. Then there exists pair of univariate distributions (P, Q) with (a)) Ha(P, Q). Specifically, distribution supported on [0, 1) and has CDF + H (x 1), where H the convex conjugate of privacy profile H. Distribution Q is Uniform((0, 1))
Proof. This result corresponds to the second part of Lemma in (Zhu al., 2022).
D.3. Privacy Accounting
Our ultimate objective to provide privacy guarantees for an entire training run. The following result motivates why we can achieve this objective by deriving dominating pairs for each update step.
Lemma D.13. Consider component mechanism M X + RD and component mechanism with auxiliary input M' : RD + PR Assume that (P.Q) is a dominating of M and (P', (P',Q") a dominating pair of M' o) for all auxiliary imputs IRD Then, the product measures (P Pl, Q x Q') supported on TRD RD are dominating pair of composed mechanism > M'(x, (x)).
Proof. This result corresponds to Theorem 10 in combination with Footnote 3 from (Zhu et al., 2022) for the special case of real-valued co-domains.
Note that this result also implics that multiple dominating pairs may share the same privacy profile.
32

---

Deep Differentially Private Time Series Forecasting
In the case of DP-SGD, the auxiliary inputs are the model parameters that resulted from the previous update step. This characterization of the composed mechanism's 's privacy in terms of product measures is in fact the tightest possible characterization given dominating pairs of the components (see discussion of Theorem 3.2 in (Dong et al., 2022)).
While Lemma D.13 lets us easily define dominating pairs for composed mechanisms, obtaining privacy parameters (E, 6) by evaluating the privacy profile a + H. (Px x P'||Q x Q') can be challenging. There exists a variety of solutions to this problem, such as moments accounting (Abadi et al., 2016; Mironov, 2017) or central limit theorems of composition (Sommer et al., 2019; Dong et al., 2022).
Privacy loss distribution (PLD) accounting is a family of SOTA approaches that enable tight numeric privacy accounting with arbitrary accuracy using the notion of privacy loss random variables introduced in (Dwork & Rothblum, 2016);
Definition D.14. Consider a pair of distributions (P,Q): The corresponding privacy loss random variable Lr. is the (PP [Q (0)) with
random variable log
P. Similarly, fq.P P is the random variable log (d (o) with Q.
[P
Note that one can easily convert between dominating pairs, privacy profiles, and distributions of privacy loss random variables (see Fig. 2 in (Zhu et al., 2022)). In particular, privacy profiles can be computed from privacy loss distributions as follows:
Lemma D.15. Consider a pair of distributions (P,Q) with corresponding privacy loss random variables LP.Q and LQ.P. Then, Ha (P, Q) = Pr[Cr.q > log(a)] - -a Pr|CQ. < log(a)) for all a 2 O.
Proof. The proof is identical to that of Theorem 5 from (Balle & Wang, 2018), substituting ef with a.
Due to the logarithm in Definition D.14, the privacy loss random variable corresponding to the dominating pair (P P' Q') of our composed mechanism is simply the sum L + Lr of the components' privacy loss random variables. A key insight underlying numeric privacy loss distribution accounting is that the density of the composed PLD density is thus simply a convolution of the components' PLD densitities (Meiser Mohammadi, 2018: Sommer et al., 2019). The composed PLD can thus be efficiently computed using Fast Fourier Transforms, as proposed by Koskela et al. (2020).
A challenge in numerical PLD accounting is that it requires quantizing the distribution of LP.Q while retaining sound privacy guarantees. Doroshenko et al. (2022) show how to optimally perform such a pessimistic quantization.
Lemma D.16. Consider any pair of distributions (P,Q) and finite set of quantization thresholds E -Eo....,EE. with EK E I (+00, - and -o = Eo < < ... < Ex = too. There exists a pair of distributions (PTÔT) such that the distribution of privacy loss & p &r is only supported on E and (PtQ) QT) dominates (P, Q). Furthermore, (PTQ1 is dominated by any other distribution supported on E and is uniquely defined by ((s, H (P, Q)) | E.
Proof. This result is an immediate consequence of Lemma 4.1 from (Doroshenko al., 2022) and the fact that their Algorithm 1 takes only (Her (P,Q) E E { as an input.
Note that the last part of Lemma D.16 means that constructing pessimistic dominating pair for PLD accounting with quantized distributions only requires access to privacy profile a + (P, Q) at some finite set of points, rather than to (P,Q) Q) themselves. This is similar to Lemma 1.12, which showed that constructing a tight dominating pair only requires access to privacy profile a + Ha (P,Q) () at arbitrary a 2 O.
Summary: To summarize, we can perform optimal numeric privacy accounting for composed mechanism by: (1) Determining dominating pairs of the component mechanisms, (2) optimally quantizing the resultant privacy loss distribution using the "connecting the dots" method from (Doroshenko et al., 2022) (3) computing the composed privacy loss distribution using the Fast Fourier method of (Koskela et al., 2020), and (4) determining privacy parameters (c, 8) of the composed mechanism via Lemma D.15 derived by Balle et al. (2018).
As steps 2-4 are standard algorithms implemented in libraries like Google's 's privacy_accoo ing library (Google Differential Privacy Team, 2024), we can focus our analysis on determining dominating pairs for the component mechanisms, ie., the training steps or epochs of DP-SGD for time series forecasting.
33

---

Deep Differentially Private Time Scries Forecasting
E. Proofs from Section 4.1 (Bottom-Level Sampling)
In the following, we derive (tight) pessimistic guarantees, as well as optimistie lower bounds for epoch-level accounting when using top-level deterministic iteration and bottom-level sampling with replacement (Appendix E.1) or bottom-leve Poisson sampling (Appendix E.2). In addition, we prove that there is an optimal choice for number of subsequences e N (Appendix E.3):
Theorem 4.1. Let P" (A), (*) be tight dominating pair of epoch M for bottom-level Poisson sampling or sampling with replacement and X E N (expected) subsequences. Then H. (X), Q). is minimized by X for all 2 0.
Note that all proofs and statements of tightness assume learning without hidden states - juust like other works on privacy accounting for DP-SGD (e.g. (Abadi et al., 2016; Wang et al., 2019; Koskela et al., 2020; Gopi et al., 2021). That is, each epoch length K applied to a model fe with parameters
IR is a mechanism M X + R that does not simply release the final updated model parameters, but the gradient used in each update step. By the post-processing property of differential privacy (Dwork, 2006; Dong et al., 2022), releasing gradients at each step at least as private as relcasing the updated model parameters each step and vice-versa (assuming fixed and known learning rate).
Our privacy guarantees can likely be tightened if we were to assume learning with hidden states (Ye & Shokri, 2022), i.c. only release the final updates model parameter via mechanism M : X - RR However, such analyses based on amplification by iteration (Feldman et al., 2018) generally require some assumptions about convexity and/or smoothness of the loss landscape, which we cannot make in our general treatment of deep time series forecasting.
E.1. Sampling With Replacement
Our main objective for top-level deterministic iteration (see Algorithm 3) and bottom-level sampling with replacement (see Algorithm 4) will be proving the the following tight pessimistic bound:
Theorem 4.2. Consider the number of sampled subsequences
1, and let r Lo+Le be the probability of sampling L-Lo+1
a subsequence containing any specific element. Define P(1) = MoG (1,, P) with means μ = =1 2 and weights
= [-r r]²
Further, define per-epoch privacy profile (a)) = sup m=
Ha Ha (MMMl MM Then,
H(a) (a(P(())IN(O, ifa o)) 30
We shall further prove the following pessimistic and optimistic bounds for X X 1:
Theorem E.1. Consider number of sampled subsequences 2 1, and let r Lot be the probability of sampling a
b-b++I
subsequence containing any specific element. Define P(A) MoGG p. and Q(A) MoG(p, p. o) with means
[0 2 4 2-X) x] and weights p [0, 1]A+1 with p; = Binomial(i - X,r). Further define per-epoch privacy profile (aa) sup gxd Ho (M Mar)). Then,
((a) S H. (a())))
Theorem 4.3. Consider the number of subsequences 2 1, and let r means μ E No+1 and weights p E [0, 1j²+1 with 14 2(í 1) and pe Binomial(i A,r). Further, define per-epoch privacy profile ((a) sup 20 gx Ho Ha (M.llMa..... Then,
Lo+Lp Define P(A) MoG p,o) with L-Let1'
H(a) > (a(P(A))IV(o..)) if Ha(W(O,))(P(())) i
To this end, we will
1. Prove that, under top-level deterministic iteration, the privacy of our epoch-level mechanism can be upper-bounded by analyzing a training step for single batch,
upper-bounded 2. prove that the privacy this training step can be upper- bounded by analyzing sampling with replacement under group substitution.
34

---

Deep Differentially Private Time Series Forecasting
3. derive pessimistic upper bounds for sampling with replacement under group substitution,
4. determine optimistic lower bounds that coincide with the upper bound for X by constructing worst-case time series datasets,
5. determine dominating pairs corresponding to our pessimistic upper bounds.
E. REDUCTION FROM EPOCH- TO STEP-LEVEL PRIVACY
Consider two sets of sequences r {I1,.... :NN and = f.' .'y) with x Sg, i.e., # x' for exactly one n. If we partition these sets into subsets of size N' = [A / λ] in data-independent manner and use each subset for exactly one training step, we know that only one of these steps will access the modified sequence Vi, and potentially leak its sensitive information.
The following statement formalizes this idea, which essentially corresponds to an adaptive form of the parallel composition property of differential privacy (McSherry, 2009), expressed in the language of dominating pairs.
Lemma E.2 (Adaptive parallel composition.). Consider some data space & and a dataset space X for E P(A) |a| = = with N = K N' for some K, N' E N. Further consider sequence of K adaptive mechanisms M(), M(K) with M AN x (R(11)xD + RD, Define the adaptively composed mechanism
M(x)= M(K) (IIN-N+1...... .N M(KK ((EN-2N'41 (I... .. IN-N M ( ()..)))
that lets the component mechanisms only access disjoint subsets of input dataset x. Let ~ be the substitution relation. Let p(k), Q(h be dominating pair of ( (,,2) under = for all size-N' subsets of A. Then, for all 0.
sup Ha (M, (M S max Ha (P( A
(3)
Proof. With slight abuse of notation, let in the following write M (y/ 2) for the output distribution M, of any component mechanism (k) given input y and auxiliary imput instead of its output random variable. Consider any pair of datasets = x'. Assume w.l.o.g. that the single pair of elements In and z with Tn + z', is accessed by the kth mechanisms. Since p(k), ((()) is dominating pair under substitution for all size-N' auxiliary inputs we know that
max H, (Ha(P(
( (
-
Since all component mechanisms access disjoint subsets, further know for any 1 + k that
max Ha (AX IN -N- (1 (K - 10 - -max sH,(N(O.o),NN0,00)
for some R.
Define P = p(k) x (N) x... x N o)) and Q = p()) x (0, x.- (O) From the above two inequali- ties and the composition theorem for dominating pairs (see Lemma 13, and see proof of Theorem 27 (Zhu et al., 2022) for intermediate steps), we know that H. H,,,, M S (P, Q). Thus, by definition of hockey stick divergence Ha,
H. (M, MMa.))
dP
(0) a ) dQ(()
max
0. dQ
BRXD
dp(k)
(Os) a 1 dQ(O)
max
0. dQw
JRKXD
dp(k)
(Oe) 1
max
0.
dQw)
(Q(()
JRKXD
(H(t)(()
35

---

Deep Differentially Private Time Series Forecasting
where the second-to-lan equality follows from marginalizing the output of all mechanisms M0 with o k. Our result from Eq. (3) then follows immediately from taking the supremum over all pairs of datasets = x' and the maximum over all steps k in which the substituted elements nn A znn can appear.
E.1.2. REDUCTION TO SUBSAMPLED GROUP PRIVACY
Let us assume g.l.o.g. that x1 * x for our two datasets x 2 x/. That is, the single modified time series contributes to the first pair of top-level batches (1) {æ1, .,2....,,NN' and x²(1) 22, with N' LA/ Al.
Let ( be the mechanism that yields bottom-level subsampled. clipped, summed. and noised gradients for the kth top-level batch. Since all top-level batches are disjoint, we can apply the parallel composition lemma from Lemma E.2. Since all top-level batches (x(6,, (x(k) are identical for k > 1, we already know that the kth step is perfectly private, i.e. max a, 0). Thus, the maximum in Eq. (3) will be attained by M(1) and we focus on analyzing the privacy of the first gradient step.
vk > 1 : H., H, (M [|
For the following proof, let R + P(R be the bottom-level subsampling function described by Algorithm 4 that takes a single sequence and yields multiple subsequences of length I-c + Lr. Let G P(R - TR be the function that yields clipped and summed per-subsequence gradients for a set of subsequences, i.e., Algorithm 2 without adding Gaussian noise.
The next result shows that we only need analyze the privacy of the gradients for modified time series 21 and x/1, rather than the entire top-level batch 20();
Lemma E.3. Let M(); PP(R+) P) be the mechanism that yields bottom-level subsampled, clipped, summed, and noised gradients for the first top-level batch. Let M : RR- - R with M(aa) = Z + (G o ())) and Z = NO, T be the mechanism that yields bottom-level subsampled, clipped, summed, and noised gradients for single sequence. Consider an arbitrary pair of top-level batches (1)) x01) with xn & a4 where xn E (1) and x' E x(11), Then, for all
x((1)
a 120 O,
Ha Ha Marx:))
sup H (M,, s.t. (x1) = (zi}.
Proof. Consider a pair of top-level batches x(1 {2,, 12, "2,.,,, and z((1 {z/. 22 ..... IN.
Since addition of Gaussian gradient noise commutes with summing over per-sequence gradients, we can write ( (x(1) via
N (x = z+}} Σ (G (Go)) = 2 (Go + ()) = M(xx) + [G. ()(z). 1=1
N'
N'
n=2
n=2
By the post-processing property of differential privacy (Dwork, 2006; Dong et al., 2022), this sum over per-sequence gradients, in which only the first one is randomly perturbed, is at least as private as releasing the per-sequence gradients individually. That is, the following mechanism attains greater or equal hockey stick divergence:
(M))), (G ()22), .... (G ()x.))
This is (nda-iad parallel composition, i.c.. we can apply Lemma E.2. Since In = x¹, for all n > 1, we already know that all outputs except the first one are perfectly private, i.e. have privacy profile a + max a, 0}. Thus, the maximum in Eq. (3) must be attained by Ha (M2,1 [Ma)) for some worst-case choice of sequences 11, 24 that differ in one element, ie.. {21} 2 {a1}.
Finally, recall from Algorithm 4 that R ((R samples À subsequences of length Le + LF with replacement from the T- T. - Lr + available subsequences. Furthermore, exactly Le + T.p such subsequences differ between sequence I1 and x/j. Abstracting away from our time series context, this is equivalent to privacy under group substitution: Definition E.4. Consider a dataset space X P(A) with underlying set A. Two datasets x, x' E X of size T are s-group-substiiuution neighboring (x A x') if there are groups S x and g' C x' with [g| = Ig'| = & and x g = x g
Furthermore, abstracting away from our machine learning context, our gradient mechanism G(-)+Z Z with ~ NO, 12 simply calibrated Gaussian mechanism with an underlying function of bounded sensitivity A₂ = C (Song et al., 2013):
36

---

Deep Differentially Private Time Scries Forecasting
Definition E.S. Consider batch space Y P(A) Y P Pmulu(A) where Pmulti (A) is the set of all multisets that can be constructed from underlying set A. A function f V RD has fz-sensitivity A2 under insertion/removal (= if Vy.y' E Y y = v' = llf(v) f(y')l < 22.
Based on our results from this and the previous section, we can focus analyzing the privacy of such mechanisms under group substitution.
1.3. SAMPLING WITH REPLACEMENT UNDER GROUP SUBSTITUTION
In the following, we apply the conditional coupling approach from (Schuchardt et al., 2024) (recall Lemma D.4). That is, we partition the support of our subsampling distributions into events and define a joint coupling between the corresponding subsampling distributions.
Lemma E.6. Consider a dataset space (A) with undertying set A. and batch space Y = Pmmulu (A). Let S: : + be subsampling with replacement with batch size X. Let base mechanism B - TR. be Gaussian mechanism Byy) = f Z with Z (0, A2o²I), where 22 is the lz-sensitivity of underlying function f Y + IR under insertion/removall (= Define subsampled mechanism M =BoS S and consider k- k-group-subssitution neighboring datasets k. x' of size T. Then, for all 2 0,
H (M M & max H. (PII)),
(4)
PQQ
where Q is of all pairs of multivariate Gaussian mixtures (P, with P E wi -N , and Q (2) Σjz Wy NN I²2) satisfying
l (1) u1 112 -i
Vi,j w.j:
|| 11 12
Vi.j w.J:
(5)
[|m (1) 14j 1l2 2 max(i.
w.j:1sisA+LIIssAHHI
with Vi: : pi (1)
E D and wi Binomial(i - A, and r
Proof. Since =A x', there must be two groups g {aı, {ai,...,aa)10 axjig' {al...., de} with [g| [g'| k and r\gg- = x z''g' whose elements we assign an arbitrary ordering. Let A, = (v S yΠg it and E, (v S x' yng' = j be the events that and j group elements are sampled from x and x', respectively. Note that S refers to sub-multisets, where a single element can be sampled multiple times. As can be easily verified, (A,) = Binomial(i A, and S. Binomial(j r)
Let 8x V 10, 1] and 8 W [0, 1] be the densitities of subsampling distributions S2 and Sz., Since any batch that contains j group elements under condition A; or Aj is equally likely we have
s Ax) 1 ly A.), s E.) x 1 Iy E Es].
We can thus define joint coupling I of Sz(.) Ap)....,S((( Ax). (- Eo). "......,,.f S. function y 122(A+1) + [0, 1]:
Sx(-1
Ex) via the following mass
1) x (2 |
Aa)
II
7 10
II
7w,
yi (1
(=0
1=0
with
(1)
(2) 3a of ,' eg: = y4 (1) {a)
( y
(2)
(1) yi (2) g'
= vi 1 No | (isiska ( = of E
In short, we sample uniformly at random with replacement multiset that does not contain any elements from group g to (I)
obtain y0
Then, we iteratively construct 1441 from (1) by replacing a non-group element uniformly random with a
37

---

Deep Differentially Private Time Series Forecasting
(1)
group element. Finally, we construct yi from yi by replacing all elements from group 9 with their counterpart from g' By construction, all marginals are uniformly supported on the support of their corresponding distributions, i.c., we have valid coupling.
Now, let d(v. y²) be the induced distance under insertion/removal between multiset-hatches y and y', i.e., the number of insertions or removals needed to construct one from the other. By definition, we have for the entire support of the coupling:
d(y 1/ / 2-
Vi.j : Aal:isisAAs
d yj
(2) (2)
" 22-
W.j:IgisAisus
d(y, (1) / max
Vi,j Aib:liisAlsie Suss. susss
This is because (1) with j 2 i iteratively constructed from y1 (1) j - substitutions, i.e., 2 2/ - -il insertions/removals. y/
(2) with j 2 is constructed from yi, 122 by substituting elements from group i, inserting their counterparts
Furthermore, y
from group g', and then substituting an additional j i elements for total of (j - i) + = j substitutions. The case j S is analogous.
The result then immediately follows from considering worst-case datasets (recall Lemma D.6) fulfilling these distance constraints, and the fact that base mechanism B Y + IP is a Gaussian mechanism with covariance σ²AzI whose underlying function f + RD has l2 sensitivity A₂ under insertion/removal.
Maybe somewhat surprisingly, the bound is identical to sampling with replacement under a single substition (see Theorem L.3 in (Schuchardt et al., 2024)), except for a change of Binomial distribution parameter from + to +.
Next, we can solve a relaxed form of the optimization problem in Lemma E.6 obtain our pessimistic upper bound for arbitrary X.
Theorem E.1. Consider number of sampled subsequences À 2 1, and let r t be the probability of sampling a
subsequence containing any specific element. Define P(A) = MoG p.p.o) and Q(A) = MoG p. σ) with means
== 10 2 4 2 x] and weights p [o, 1] with p; = Binomial(i X, r). Further define per-epoch privacy profile H(a) = ssup 2 gal H. (Mal Then,
H(a) S (P(A)))((
Proof. As discussed in the previous two, the privacy of M can be upper-bounded by analyzing group privacy under substitution using sampling with replacement. Specifically, we can instantiate Lemma E.6 with sensitivity A equal to clipping constant C, group size k = Le + LF and dataset size T = L LE + 1. Due to translation equivariance of hockey stick divergences between Gaussians, we can assume w.l.o.g. that μ (1) p 0. We can further discard (2) ||2 < 2- max [i.j) to obtain a relaxed optimization problem.
|| (1) - 14j
The optimal solution to the relaxed optimization problem is known from (Schuchardt et al., 2024) (see Lemma D.7) and corresponds exactly to our result.
For the special case of 1, we can solve the optimization problem exactly to obtain a tight upper bound (we will later prove tightness, i.e., the 2 part of Theorem 4.2, by constructing a pessimistic lower bound in the next section):
LotLe be the probability of sampling Lemma E.7. Consider number of sampled subsequences À 1, and let r L-LF+1
a subsequence containing any specific element. Define P(1) MO p.o) σ) with means μ [o 21" and weights p p= [1-r r|" Further define per-epoch privacy profile H(a) sup Ann Ha (M.)) Then,
H(a) < (a((()))NN(0OO) ifa (N a
Proof. We begin with the case a 2 1. As before, we can instantiate Lemma E.6 with sensitvity A₂ equal clipping constant C. group size k = Le + LF and dataset size T = L LF + 1. Due to translation equivariance of hockey stick divergences between Gaussians, we can assume w.l.o.g. that μ1
(1) 0.
38

---

Deep Differentially Private Time Series Forecasting
Thus, optimization problem becomes
Ha (11- -N .N( (1 ,01) +r. +rr-Nuu of r) R (4(2)
+r
, o21)
subject to u22 O. Mi (1) u |m 11 2, and |1
0 12 (2) 2.
Since the first two mixture components are identical and have identical weights, we can apply the advanced joint convexity property of hockey stick divergences (Balle al. (2018), see Lemma D.2) to eliminate p1 and rewrite our objective
(2) o² B(a) (i max r Har (N(uf), o I) 3(o)) N(1
with some a' 2 and (aa) E [0, 1]. Since we eliminated one variable, we are left with constraints μ42 (1) = 0, 1| (2)
u2 2 S and || u42 S 2. Since we now have only distance constraints to the origin, we can apply Lemma D.7 to
(2)
arrive at the optimal value
Ho (N10, (I -N2)))))))))) + ((a) (2(,
=H, ((1r)
- (V(2,) +roo))+--(00 ((0
where the equality follows from reverse application of the advanced joint convexity property, and the fact that the two components of the second distribution are identical. The result for a 2 1 then follows from rotating and translating the coordinate system such that the second distribution has mean at the origin.
For the case 0 < I, we can use the following fact: If P. Q is dominating for under symmetric neighboring relation, then Q, is dominating for 0 S < (Zhu al. (2022), see Lemma D.10).
E.1.4. OPTIMISTIC LOWER BOUNDS
Next, construct optimistic lower bounds by constructing worst-case gradient function and a pair of datasets for each 0.
Theorem 4.3. Consider the number of subsequences X 1, and let Lo+LF Define P(A) MoG p, with 1.-1.1+1-
means μ E No and weights p E [0, 1] with μ4 = =2( - 1) and p; = Binomial(i X,r). Further, define per-epoch privacy profile H(a) = sup x2 gad Ha (M Then,
H(a)² > (a(((())IN(O.o) if (II(() a
Proof. Since our model fo is an arbitrary parametric function, we can assume that it the anti-derivative of any desired gradient function g Bl + R.D. We choose the following function:
{Co 10.en if E (1...., + Lr) 1,
s(a) - -c eotherrise.
where ej is the indicator vector that is non-zero in its first component, and C' is the clipping constant (i.e., our per-sequence gradients will never be affected by clipping).
and 2 0 0 that differ in their first element. Note that the first element can appear in Le LF different subsequences in different positions because Algorithm 4 zero-pads the sequence before sampling with replacement. Further consider sequences ..,.... &N R \ {1} such that Vm > n >> 1 Xm # In A + In # oí (so that our dataset is proper set, i.c., does not have duplicates). Define datasets r = {I1, I2..... NN) and x' = {ar, T2.... I2,...,NNll
Case 1 (a 1): Consider sequences F1, E RR with 2ı [1 0
By construction, x 2 x'_ For every sequence in a top-level batch, we sample subsequences with replacement, there are L- LF + 1 subsequences in total, and there are exactly Le + LF subsequences 21 that contain These Le + LF subsequences will add C' to our summed gradient when sampled, while all other gradients subtract C. Due to translation
39

---

Deep Differentially Private Time Scries Forecasting
invariance of hockey stick divergences between Gaussian mixtures (i.e., we can translate C À into the origin) and after marginalizing out all but the first dimension, exactly attain our desired bound. The subsequent training steps operate on identical data and will thus not contribute to the hockey stick divergence attained by the epoch-level mechanism (same argument as in Lemma E.2).
Case 2 (0 S a < 1): For this case, we define x = f2i, .xy and x' = T2, RN ), i.e., interchange the first sequence between æ and x'. The remaining proof is symmetric to the previous case.
Note that, for 1, Theorem 4.3 coincides with Lemma E.7, ie.. our pessimistic bound is tight. Thus, this also concludes our proof of Theorem 4.2.
E.1.5. DOMINATING PAIRS.
Next, let us discuss how to construct dominating pairs corresponding to our bounds.
In the case of our generic pessimistic bound for À 2 1 (see Theorem E.1), we simply have sup a Ha Ha(MellMpr) < H. ((())))((())) where P(X) and (A) are univariate mixtures of Gaussians. Evidently, these two mixtures are dominating pair.
In the case of our tight bound for X 2 1, we have
Ha(P(O))N(O)O)) if
sup Ha(M)))M))
Ha(W(O,))IP(L)) if a
gar
Due to equality, the r.h.s. term is valid privacy profile by definition (ef. Lemma D.11). For the purpose of further analysis, one can construct dominating pair via convex conjugation (Zhu et al., 2022):
Lemma D.12. Let H R, + R a privacy profile. Then there exists a pair of univariate distributions (P, Q) with (a)) Ha(P, Q). Specifically, distribution supported on [0, 1) and has CDF + H (x - 1), where H is the convex conjugate of privacy profile H. Distribution Q is Uniform([0. 1)).
For the purpose of numerical privacy accounting, we need to construct a quantized dominating pair. As is known from (Doroshenko et al., 2022), the best possible quantized dominating pair only requires access to privacy profile:
Lemma D.16. Consider any pair of distributions (P,Q) and finite set of quantization thresholds & = {Eo..... {Eo....,EK] EK) with EK E R (+o, ] and -oo = Eo < E\ < .... < Ek = +oo. There exists a pair of distributions (PtQt) such that the distribution of privacy loss pp .r only supported on & and (P*Qt) dominates (P,Q). Furthermore, (P*Q1) is dominated by any other distribution supported on & and is uniquely defined by {(s, Hes (P, Q)) E
Thus, algorithmically generate a dominating pair using the "comnect-the-dots" (Doroshenko et al., 2022) method without explicitly needing to construct a non-quantized dominating pair. We use the latter approach for all our experiments.
E.2. Poisson Sampling
Algorithm Bottom-Level Poisson Sampling
Input: Sequence 2n, context length Lc, forecast length LF, expected subsequences À z/ prepend.zeros(r,, zeros(z,, Lc)
[padding] (maximum start index) {Rate sample À in expectation.
T L LF +1 r mmin for - to T do
if UniformmO. (0, 1] < r then yield x/ : + Le + LF -1
(cropping]
Our main objective for top-level deterministic iteration (see Algorithm 3) and bottom-level Poisson sampling (see Algo- rithm 6) will be proving the the following tight pessimistic bound for arbitrary À E N:
40

---

1. Prove that, under top-level deterministic iteration, the privacy of our epoch-level mechanism can be upper-bounded by analyzing a training step for single batch, Deep Differentially Private Time Series Forecasting
Theorem E.8. Consider an expected number of subsequences À E N and let min sampling rate from Algoritim 6. Then P(X) MoG(-1 p.p,o and Q())= MoG P, d) with means ji (i (111) 1) and weights ps Binomial(i - Lo + Lp,r) are tight dominating pair of epoch M under Eg.
A/ (L. Lp 1)} be the resultant
To this end, we can
2. prove that the privacy of this training step can be upper-bounded by analyzing Poisson sampling under group substitu- tion,
3. derive pessimistic upper bounds for sampling with replacement under group substitution,
4. determine optimistic lower bounds that coincide with the upper bound for all À E N by constructing worst-case time series datasets,
5. determine tight dominating pairs corresponding to our tight pessimistic bounds.
The first two steps identical to the pervious section, since they do not depend on the distribution of the bottom-level subsampling procedure (see Appendices 1.1.1 and 1.1. For the third step, we can use the following known result from (Schuchardt et al., 2024) for group insertion/removal.
Definition E.9. Consider dataset space X = PAA) with underlying set A. Two datasets x, x' E X of size T are (k+,, group-inssertionrrrmvaal neighboring (æ: =b, , , x') if there are groups g- S and g+ S x' with 1-_| = k_ and g-1 = k+ such that r' = x 1- Ug-.
Lemma E.10 (Schuchardt et al., 2024)). Consider a dataset space X = P(A) with undertying set h. and batch space Y P(A). Let S : X - Y be Poisson sampling with rate Let base mechanism B Y - R be Gaussian mechanism B(y) [+ Z with Z ~ N(0, 12, where 22 is the Ez-sensitivity of underlying function f Y - RRD under insertion/removal
(~+). Define subsampled mechanism M- = - o S. Further define mixture distributions P(k) = MMGG-11 p-, o) and
Q(k)= = Mo ( pt,0) with means μa- = [0
k-]" and μ.+ = [0 1 2
k_]". as well a weights
weights p- [0, 11 with p-, = Binomial(i 1 k), and p+ E [0, 1] +1 with p-, = Binomial(i k4, r).
Then, for all a 2 0.
sup k
Ha Ha & (a(())))Q())).
(6)
From our derivations in Appendices E.1.1 and E.1.2, the following result immediately follows via a seemingly naive reduction from group substitution to group insertion/remmoall:::
Lemma E.11. Consider an expected number of subsequences E N and let r m1n(1, (T.
I.F+ (I be the resultant
sampling rate from Algorithm Then P(A) MoG(-1- p.....).)) and Q()) = MoG O) with means μt (i 1)
and weights ps Binomial(i Le + Lp,r) are a dominating pair of epoch M under 2g i..., all a 2 0:
sup H. H. S (PA()I))Q((A)..
2 gxx
Proof. Any group-substitution with group size k is equivalent to a group insertion of size k, followed by a group removal of size k. Due to this observation and Lemmas E.2 and E.3, we can instantiate Lemma E. 10 with with sensitivity Ag equal to clipping constant C, and number of insertions/removals k4 = k_ = Lo + Ly.
Perhaps somewhat surprisingly, our next step will show that this naive reduction does in fact yield a tight dominating pair for our epoch-level mechanism.
1. OPTIMISTIC LOWER BOUNDS
As with sampling with replacement, we construct optimistic lower bounds by constructing a worst-case gradient function and pair of datasets for each a 2 0.
Lemma E. Consider an expected number of subsequences À E N and let r = min(1, (L-LF (L be the resultant sampling rate from Algorithm Then P(X) MoG(-1 11:11...) p, p..))) o) and Q()) = MoG(u, p, 0) with means μt = (i -
41

---

Deep Differentially Private Time Series Forecasting
and weights ps Binomial(i Le L), fulfill for all a 2
sup Ha Ha 2 H. (a(
(8)
a grggg
Proof. Since our model fo is an arbitrary parametric function, we can assume that it is the anti-derivative of any desired gradient function g RLO+LF + R.D. We choose the following function:
C.eer
if (1, ( Lo + Ir) a 1,
((a) = -- else if 31 E (1..... Lc + LF) : a = -1, otherwise.
where ej is the indicator vector that is non-zero in its first component, and C' is the clipping constant (i.e., our per-sequence gradients will never be affected by clipping).
[1 0 ... and σ = [-1 0 0] that differ in their first element. Note that the first element can appear in Lp different subsequences in different positions because Algorithm zero-pads the sequence before Poisson sampling. Further consider sequences In A 11 A In # z (so that our dataset a proper set, i.e., does not have duplicates) and Vn $ In -1 nn (so that the gradients for all subsequences are always zero). Define datasets x { ; 22, .N NN and x' { 22 , NNN.
Next, consider sequences 21, #1 E R² with =
such that Vm > n > Jm of
By construction, x n x'. For every sequence in top-level batch, we Poisson sample up L LF subsequences, there are L - LF + subsequences in total. There are exactly Lc + LE subsequences in 21 that contain 1 and Lc + LE subsequences in 2 that contain -1. These Le + Lp subsequences will, respectively, add +C and -C' to our summed gradient when sampled, while all other gradients are 0. Thus, we exactly attain our desired bound in the first training step. The subsequent training steps operate on identical data and will thus not contribute to the hockey stick divergence attained by the epoch-level mechanism (same argument as Lemma E.2).
From the fact that our upper bound (Lemma E, 1) and our lower bound (Lemma E.12) coincide, the tightness of our dominating pairs (Theorem E.8) immediately follows.
Other contributions. The fact that we have been able to derive tight guarantees for what is essentially group substitution using the sensitivity of the base mechanism w.r.t. insertion/removal showcases the benefit of analyzing hybrid neighboring relations (Balle et al., 2018). Furthermore, it showcases that certain subsampling schemes are more compatible with certain neighboring relations (Lebeda et al., 2024) even in the group privacy setting.
E.3. Optimal Number of Subsequences
Finally, we can prove that x = 1 minimizes the privacy profile for all under both sampling with replacement and Poisson sampling. To this end, recall the following fact about stochastic dominance between Binomial distributions (see, e.g.. Example 4.2.4. from (Roch, 2024)):
Lemma E.13. Consider distributions Dn.p = Binomial(N, p) and DM.q = Binomial(m, q) with N 2 M and p 2 q. Then D N.p stochastically dominates Da ie, there exists a monotonic coupling II of DN.; and DM.gg with mass f function
No [0, 1] such that Tkk, + 2
In other words, we construct D from Das.q by shifting probability mass towards larger values.
In addition to stochastic dominance, we will make use of the following monotonicity result for hockey stick divergences between pairs of Gaussian mixtures (special case of Theorem O.6 from (Schuchardt et al., 2024) for univariate mixtures): Lemma E.14. Consider any pair of Gaussian mixtures P = MoG(-u, p, o) and Q = Mo σ) with non-negative means E RNN v E R. and weights p E [0, 1 q E [o. 1 Then, the sur-ivvvrivative of (P Q) w.r.t any pr or V non-negative.
In other words: Moving mixture components farther from the origin (integrating over the non-negative (sub-) )ebb--vdiivat only ever increases divergence.
Trying to use sensitivity w.r.t. substitution would induce much more complicated distance constraints after coupling.
42

---

Deep Differentially Private Time Scries Forecasting
Let us now begin with proving optimality for Poisson sampling:
Lemma E.15. Let P* (A), (x) be a tight dominating pair of epoch M for bottom-level Poisson sampling and À E expected subsequences. Then Ha(P"*)) (A))Q((( (X)) is minimized by X 1 for all O.
Proof. By definition, all tight dominating pairs exactly match the privacy profile of mechanism M. i.e. attain identical hockey stick divergence for all 2 0. We can thus focus our discussion the tight dominating pairs from Theorem E.8, which are mixtures of Gaussians.
Consider an arbitrary À > and let P(A) MoG(-1 P. p. and Q(A) = MoG p. with means μa = (i - 1) and weights = Binomial(i - 1 Lc + LF, r()) and sampling rate r()) min (L LF + 1)}.
Since r()) is increasing X, we know from Lemma E.13 that (nnomial(Lc LF, r())) stochastically dominates Binomial [.c + r(1). We can thus use a monotonic coupling of the two weight distributions with coupling mass function क. No + [0, to restate P(1), Q(1) as follows:
L. LL+
Lo+L Ly LotLe
P(1) = Σ ==
ik, N(-1-,,,o2),
Q(1)
Σ
T(k,)) Ni 02),
i.e. we split up the ith (with zero-based indexing) mixture component into Le + LF + mixture components with identical means. Similarly, we can restate P(A), Q(A) as
Le+Ls Le+Lr
Lo+Lr Le+Lr
P(A) = E
Q(A) = Σ Σ i(k,))-
Since =(k 20 = 2 (Lemma E313), and divergence increases when increasing the norm of the mixture means (Lemma E.1 we know that H. (P(()))))) 2 Ha(P()))(Q()).
Next, let us consider sampling with replacement. The proof is slightly more involved, since we only have optimistic lower bounds for À > as opposed to an exact characterization of the privacy profile.
Lemma E.16. Let P* (A), (A) be a tight dominating pair of epoch M for bottom-level sampling with replacement and expected subsequences. Then Ha (A), (X)) is minimized by X = for all a 2
Proof. Case (ax 2 1): Consider any tight dominating pair (*(A), (*(A) for À 2 as well as a tight dominating pair P*(1), (1) for 1. We know from Theorem 4.3 and the definition of tight dominating pairs that
Ha (AIII()) H. (0))))
while we know from Theorem 4.2 that
H. H.(((L))N(O) o)) = H..(P"
P, a), l E No+1 and weights p E [o, 1j0+1 with = 2(i - and p; = Binomial(i X, r), where r constant in
with P()) =
We can thus prove Ha (P" (P (A)) 2 (IP((I))))) by proving H. (.)())))((..) 2 (O)
To this end, recall from Lemma E. that (nnomial(A,r) stochastically dominates Binomial(1,r). We thus apply exactly the same monotonic-coupling-
proof as with Lemma E.
Case 2 (0 < a < 1): This case is fully analogous, except that we need to use monotonic couplings to prove 2 (a(N((,0)))(())
Ha
43

---

Deep Differentially Private Time Scries Forecasting
F. Proofs from Section 4.2 (Bi-Level Sampling)
The main purpose of this section is to prove the following tight pessimistic guarantee for top-level sampling without replacement and nottom-leve sampling with replacement:
Theorem 4.4. Consider the number of subsequences X x= 1 and batch size A. Let Lo+Le and let /// I.-L.tI
be the probability of sampling any specific sequence. Define P(1) MoG (M. A,, with jt [0 2 and p
[11 p) + p. (1-1)) p.r]". Then, per-step privacy profile (ax) sup puge Ha Ha
(a)) (L((()))N((00))) if oL( f
We further want to prove the following (not necessarily tight) pessimistic guarantees:
Theorem F.1. Consider bottom-level sampling with replacement, number of subsequences X 1 and batch size A. Let
Lo+LE L,- and let p = [A / To / N be the probability of sampling any specific sequence. Like in Theorem E.
define P(A) MoG(-1-- μ. p. o) and Q()) MoG(u, o. with means f [0 2 4
2 x)" and weights
E [0, 1|]+1 with ps = Binomial(; (i- - X, r). Then, per-step privacy profile H sup z=ne'
Ho (M))) fulfills
(a) (1 p) ma a) + Ho H. (P(A)II(())))
Theorem F.2. Consider bottom-level Poisson sampling, number of subsequences À = 1 and batch size A. Letr = m // (I- + 1)} be the resulting Poisson sampling rate, and let [A λ} N be the probability of sampling any specific sequence. Like in Theorem E.8, define P(A) = MoG(-1- μa, p. σ) and Q()) = MoG(u,,, p, with means μt: = -) and weights p; Binomialli - 1 Le + LF,r). Then, per-step privacy profile il (a) = sup 2igar Ho MMMMl|MMa fulfills
((a)= s (1 - p) ma 1- - a} + (P(()III))))
We further want to determine pessimistic lower bounds to serve as baselines for = our numerical experiments. To derive these results, we proceed similar to Appendix E. Specifically, we:
1. Prove that, the privacy of our bi-level mechanism can be bounded by considering fixed set of top-level batches,
2. from this result, derive pessimistic upper bounds via joint convexity.
3. derive tighter upper bounds for À = 1 and bottom-level sampling with replacement by focusing on our analysis on a single per-subsequence gradient via the parallel composition property,
4. determine optimistic lower bounds that coincide with the upper bound for À = and bottom-level sampling with replacement by constructing worst-case time series datasets,
5. determine dominating pairs corresponding our pessimistic upper bounds.
F.1. Reduction to Fixed Set of Top-Level Batches
In the following, we use conditional couplings to eliminate the randomness inherent to top-level sampling from our analysis. The proof is largely identical that for sampling without replacement and substitution in (e.g., Theorem 11.2 in (Zhu al., 2022)) except that sometimes only substitute with sequences that differ in single element (1-event-level privacy).
Lemma F.3. Consider the space & = R of all length-L sequences. Let X C P(A) be the space of all size-N datasets of sequences. Further consider batch size A and bottom-level number of instances with resultant top-level butch size N' [A] / A). Let = P(A) be the space of all size-N' top-level batches. Let S X " be top-level sampling without replacement, as defined in Algorithm and p = [A X] / be the probability of sampling any specific sequence. Finally, let B: Y + R be an arbitrary mechanism that maps top-leve! batches to gradients and define M - S. Then, for all 2 0.
sup H. Ha(Mall (M))) v.y EEY
H. (11 (11-)) + p. By - p)- BB, + Byy) pp)
sup
22 g.
subject to y ~ L. a 3 of E y² where A indicates arbitrary substitution of single sequence, while mE indicates substitution while only changing a single element of the sequence.
44

---

Deep Differentially Private Time Scries Forecasting
Proof. Consider arbitrary a: gg x'. By definition, there must be some In E and xn E x' such that x: \ fa/m) = x' (2/} and sequences differ in exactly one sequence.
Define events An = fy C nn $ a) fv SI In E x}. Define events En = {v S n & x') Ei = {y S o E o'}.
We naturally have 52 (Ao) Sz. (
= - and (Ai) = (Ei) =
We then define coupling I of Sz( S.( A1), (- Eo), S: Eo) via the following mass function:
701 (1) 91 No vi )
888 (v))) Ao)
3rm E M/ 1/1 y0 ( U
II
1
(2) vith {an u
1=0
By construction, the entire support of our couplings fulfills (1)
00
(2) 30
د vi vo0 = v/ 2 and y) (1) Eg v1²)
(1)
yo
The result then immediately follows from considering worst-case datasets given these constraints (Lemma D.6).
The distinction between the two different types of substitution is critically important for our later analysis of amplification by-augmentation, as we may otherwise drastically underestimate the difference of specific Gaussian distributions.
F22 Pessimistic Upper Bounds via Joint Convexity
Via the next lemma, we can immediately prove our (not necessarily tight) pessimistic upper bounds for top-level sampling without replacement and bottom-level Poisson sampling.
Lemma F.4. Consider the space A RR of all length-L sequences. Let X C P(A) be the space of all size-N datasets of sequences. Further consider batch size A and bottom-level number of instances À with resultant top-level batch size N' = / A|. Let Y = P(A) be the space of all size-N' top-level batches. Let $ : X + Y be top-level sampling without replacement, as defined in Algorithm 5, and p = [A X) / N be the probability of sampling any specific sequence. Finally, lei B + P be an arbitrary mechanism that maps top-level batches to grudients and define M o S. Then, for all 0,
sup Ha (M& s (1 (1-p) p)- max - at + sup Ha (Byl(B,r))
v'
ard gxx
subject to yf 2 v"
Proof. The result immediately follows from Lemma F.3 and joint convexity of hockey stick divergences ((Balle et al., 2020)), i.c.,
Ha (1 p). By + p- 1111(11p)) BB, - Byy)
<(1 pp) Ha B, (B,) p. Ha (Byl11
=(1 p) max 1 - a} p. Ha (ByllBy')
Analyzing the privacy of bottom-level subsampling when two top-level batches differ in one element of one sequence, i.e., bounding su Ha, BByl || Byy is exactly what we have already done in Appendix E. Specifically Theorem F. follows directly from Lemma E.4 and Theorem E.I, while Theorem F.2 follows directly from Lemma F.4 and Theorem E.8.
E.3. Tighter Upper Bounds for Sampling With Replacement
Instead of directly applying joint convexity, can derive tighter bounds on the following optimization problem from Lemma F.3 via conditional coupling:
sup Ha (1 (1- By + BB - pp) -B, + p. Byy)
(9)
v.ar EY
45

---

Deep Differentially Private Time Series Forecasting
Due to permutation invariance of bottom-level subsampling and gradient computation, we can define arbitrary ordering within the top-level batches such that y (v1, U2.-.. YN' ). y' = {v' U2.---.. yN' ). 5² {vl's 32,.... :.....:.''' :/N') differ in their first sequence, and 1/1 and 2/" only differ in single element. We observe that the distribution over gradients for y2..... MN are identical under both mixture mechanisms in Eq. (9) and are computed (before summation) completely independently of yı, v " We can thus make precisely the same post-processing and parallel composition argument as in Lemma E.3 from Appendix E.1.2 to show that
sup Ha ((1 (1- By + p. By p)) Bg + p. Myy) ve E
(10)
sup W.W
Ha ((1 - p) My + p. My |1(1 - (p) My. + p. M₁²))
(11)
with [21} ~ {ví {81 ~ W and {vi} ~ {ur' Again, note the distinction between arbitrary substitution of the sequence and substitution of a single element. In the above inequality, M _ + DR with M (31) = Z + (G o (v1) == (B (11) and = (V o²C² I) is the mechanism that yields bottom- subsampled, clipped. summed, and noised gradients for a single sequence. We can further upper-bound Eq. (11) via conditional coupling to prove the following result for bottom-level sampling with replacement and number of instances À
Lemma F.5. Consider arbitrary sequences y1, vhs sf E RL such that {vi} D (11). {41) =a (vr)) {vi) ZE (VI),, ie,
all sequences are different, but s/ and yi only differ in a single element. Let S 12_ -L be bottom-level sampling with replacement and number of subsequences À = as defined in Algorithm 4. Let LetLr be the probability L-Lp+1
of sampling a subsequence containing any specific element. Further define forecast-to-contl ratio @ LetLE Let B BLotte + R be an arbitrary mechanism that maps single subsequence to a gradient and define bottom-level subsampled mechanism M-
B S. Then,
He ((1 p) My + p- MMi [[[1 p) MM,, + p- Mor) s Ho (PIIQ)
with
P (1 p) Ba + p. (1-11)) + p r. 6. BB, +p. r. (1 (1- Bag
Q == (1 p) Ba + p. r1 + +p. 6. Bay + +p.r. (1 (1- Ba)
for some worst-case tuple of subsequences a, d', dp. de E Blotte where {d'zt de (a%). {d'ot de {de), subsequences ap,d'p only differ in their last Lp elements (forecast window), subsequences ac, d'c only differ in their first Le elements (context window), and the second mixture components are identical.
Proof. For the following proof, we define an ordering on the support of our subsampling distributions S,, Sy Sog with mass functions Ky, 8 8yg such that the earliest subsequence comes first, i.e.
supp(Š,.) = {a1. ................................ 4L-L. supp(S,;) = {a1, 02 aL-Lo+1h
supp(S,;; = {aal, ab,.... o4 oI
We further partition supp($,;) and supp(Š,;) based on whether and where the single modified element appears in the subsequence, i.e.,
A' {a E supp($, ( 1d df}
A/ {at e supp($,,) d,[1 : Lol #1 Lc]]
A'P {a e supp($; ) 14/Le +1 Al af + }
A" {a supp (32g | =
A = {a" e supp(S,)) |4111: Lol # d" Lc]]
A {aj" supp($,)) aa|Le 1 # Lee 11
46

---

Deep Differentially Private Time Series Forecasting
By definition of the bottom-level subsampled mechanism M, we have for the the components of the first mixture distribution:
Mgi = Σ
Ba (a)
nEsupp($>)
Myj (A')
Σ
Bi vi (d' A') + Syj 11 (A')
Σ
BubBy (d' Ac)
Σ d/EEA
BugBer By AAp)
d'EA'
d'EA''
Analogously, we have for the components of the second mixture distribution:
My Σ
Basgr (a)
nEsupp(SM1)
Map- = 3
E
Ba |A")+ + (A%) EEAA'
Σ
Bay BeyBrr(C (o6 I 146), +5,(())))
Σ aGEA%
Bay B (0% A
a"EA"
Here, the probability of not sampling, sampling in the context window, and sampling in the forecast window are Syj (1) (4") (1 -r), Sy (A') S (A") = r- (1 x), and S (A') S.y (A") = r Φ. respectively. with forecast-to- context-ratio & = Le ".F
We can now define coupling I' of conditional subsampling distributions (), (- A'), S S- Ap)) as well as their counterpart from the second mixture Sy, (-), Su (- ( (- S A7))) Specifically, the coupling will match any subsequence from v with its counterpart from of that covers the same time range:
a aa, d'c) (a d' d' dec (2)
= (a), ( 3 (dp App)- (d6 (d6) (2(al)|al) aw)) >(a"| la) 770% dp)) 7(d6 de))
with intra-distribution components
2(a 1a = 1aa = 1
r(a" d') = L[a' = aa],
ra% d'p) 1aar d
= ar. = ]
ral d'c) =1(d' dl
= d/ d.)-
By construction of the coupling, all (a(2), a', a'p, o'c, ((2), a" ",,, a²))"") with non-zero measure fulfill the following con-
straints: We have {a'r] Le {a%) {a') 2g {a"}, subsequences op, d'p only differ in their last Lp elements (forecast window), subsequences ac; de only differ in their first Le elements (context window). Furthermore, we have (1)) = (2)) and a' = a'.
The result then follows from rewriting the two mixtures as marginals of the coupling and moving the coupling outside the hockey stick divergence using joint convexity, i.e., the usual conditional coupling procedure from Lemma D.4.
Finally, we can determine worst-case mixture components given worst-case subsequences to obtain a bound in terms of Gaussian mixtures:
Lemma F.6. Consider the number of subsequences and batch size A. Letr Lothe and let p [A AJ / N be T-bbtt the probability of sampling any specific sequence. Let B RLC+LF + RD be Gaussian mechanism B(a) g(a) + 7 with Z ~ o0 () and underlying function with maximum norm C that maps a single subsequence to gradient. Consider arbitrary subsequences a, a', d'p, d',, a",, db E Lor where {a'r} 2g {a4)), {a'o} ~g {a"), subsequences a,, d'p only differ in their last Lp elements (forecast window), subsequences ac, d'c only differ in their first Le elements (context window). Define corresponding output distributions
P (1 - p) Ba + p. p0(1 (1-1) p1 + p.p. r. G. Ba, + +p.r. (1- Bag)
Q = (1 pp) B. + p. (1- B). + Bag + p.r. (1 -d))
47

---

Deep Differentially Private Time Series Forecasting
Further define P(1) = Mp p. 0) with ji = 2] and = [(1 - p) + (p...111) (1-r) p.r p-r|². Then, for all a 2 0,
Ha ( (.((()))((000)))) ifa2l,
(a((((,,))I((I)) f
Proof. Case (a 2 1): Since the hockey stick divergence jointly convex, it is also jointly quasi-convex. That is, the value attained by any interpolated argument is l.e.q. one of the arguments it interpolating between. In the context of mixture distributions, this means that
(a(P))Q) max ((1 ((1-p) Ba + p. (1-r)BB + -p. Ba, |1(1 p) Ba + p. (1 (1-r) +. r. Bay) Ha ((1- p) Ba + -1-r] (1-r)B,' + - Bag |I(1 pp) B. + + (1 r. + p.r Bug))
Since the bound we shall derive shortly will lead to identical results for both terms, let us focus w.l.o.g. g. on bounding the first one, i.c.
Ha ((1 p) p) Ba + (1 (1-r) B.r + p-r Bag - p) B. p. (I-r)Baa + ppr BBy)
Since the inputs and a' to mechanism in the first two mixture components are identical between both distributions, can use advanced joint convexity (Lemma D.2) to restate our mixture divergence via
Ha ((1- (1-p) p) Ba p. - Be + - Ba, , [1(1 p) + (1 Ba +p. Bay)) 3(a)) ((1 -p.r- Ho' (Ba; (B1-
p) Bo + p (1 (1- (I-r)Bw)) 3(a) p. Boy))
with some a' a and some B(a) 10.
Recall that B is a Gaussian mechanism. Since underlying function has maximum norm C, we know that the maximum & distance of any two means is 2- C. Due to translation equivariance of hockey stick divergences between Gaussian mixtures, we can assume w.l.o.g. that B.; = . (0,,0(22 We can thus define a constrained optimization problem over Gaussian mixture means to upper-bound our divergence:
p-r. Hol (Bo II(1 - -((a)) ((1- p) p) B. + (1 (l.r) + B(a) p-r Bag) < max P p.. r. Ha (11 ((1- -N( ()) + -1- (1-r))((()))) + B(a)) p. p-r-N( (1(1),,((1,,,1 (1(3)
subject to Vi (1) R and | S C, where omitted the covariance matrix C for brevity. As is known from (Schuchardt et al., 2024) (see Lemma D.7), the maximum is attained (1 , (2) (3) 2C E1, where e₁ has in the first component and O everywhere else. In other words, all components in the second mixture are identical. Finally, we can apply advanced joint convexity in reverse order (note that it is an equality, not an inequality) to conclude that
Ha ((1 p) B, + p (1 - B. + p. Bag [1 - p) B. + p. (1 - r) p Bay)) p. 2--(1 (1-r) r)) N2C e1, o + -2 D) - e2,
<Ha
Marginalizing out all but the first dimension, and scaling and rotating the coordinate system appropriately, concludes our proof for this case.
Case 2 (0 < a < 1): For the case S a < 1, we can use the following fact: If P.Q is dominating for a 2 1 under a symmetric neighboring relation, then Q, P is dominating for 0 I a (Zhu et al. (2022), see Lemma D.10).
In conjunction with the previous steps and lemmata, this concludes our proof of the "= part of Theorem 4.4. Next, let us show that this bound coincides with an optimistic upper bound, i.e., tight.
F.4. Optimistic Lower Bounds
Next, we can again construct worst-case datasets and gradient functions. As we shall see, we can conveniently use the same worst-case construction as for our bottom-level analysis from Appendix E.
48

---

Deep Differentially Private Time Series Forecasting
Theorem E.7. Consider top-level sampling without replacement and bottom-level sampling with replacement. Further consider any number of subsequences À E B and batch size A. Letr= Le+LE and let p [A XJ N be the probabilit of sampling any specific sequence. Define P(X) MoG(u, P. σ) with means je E N and weights
I.-L+11
10,1 with
14i = 2(i 1) and pi Binomial(i X, r). Further define per-step privacy profile H(a) = sup x2 Then,
Ha (
Ha((11 (N(()))))-(()))) P(.J)I fa
H(a) 2
o) -V(0,)) + P(A) fo
Proof. Exactly like our proof of Theorem 4.3, we can construct the following gradient function
g(a) [cc C.e if {1, Lc + Lr) =1
e otherwiie.
where e1 is the indicator vector that is non-zero in its first component, and C' is the clipping constant.
Case (a 2 1): In this case, we can construct sequences æ1,2| 24 Rh with . [0
[1 0 0 and x/ 0] that differ in their first element. We can further construct sequences I2,
ZN E R {1} such that v' > > 1 Im # In A xı # In # o' (so that our dataset is proper set, i.e., does not have duplicates). Finally, we can define datasets x = {01, 222 INJ and x' = {01, .IN
Due to top-level subsampling, the chance of aj appearing in any sampled subsequence reduces by a factor of 1 Case (a 2 1): Here, we can interchange datasets x and x'. The proof is analogous otherwise.
Note that the lower bound coincides with the bound from Theorem 4.4 for X 1, which concludes our proof of tightness.
Theorem F88 Consider top-level sampling without replacement, bottom-level Poisson sampling, number of subsequences
==1 and butch size A. Letr = min(1, (1, x - +F 1)} the resulting Poisson sampling rate, and let p = [A/ X) N be the probability of sampling any specific sequence. Like in Theorem E.8, define P(X) MMG(-11 p. p, σ)) and Q()) MoG P. o) with means 14 (i and weights p; Binomial(i - Lc r),r). Then, per-step privacy profile H (a) = sup x2gx'
Ha(M, M) fulfills
ff
H(a)²
P(A) a
Proof. The proof is, again, fully analogous for our optimistic lower bound for bottom-level subsampling, i.c., Lemma E. Top-level sampling reduces the chance of sampling a non-zero element by a factor (1 p).
F.5. Dominating Pairs
In this section, we have derived multiple bounds of the form
p) (0, -a) + pH,,()
Since this is a weighted sum of two valid privacy profiles, it naturally fulfills all necessary and sufficient conditions for privacy profiles (Zhu et al., 2022), i.c.,
Lemma D.11. A function H 14 + IR is a privacy profile if and only if H is convex, H is decreasing, H(0) = 1, and (x) > max(1= - 0,
Thus, we can use the same toolset for constructing corresponding dominating pairs as discussed in Appendix E. i.e., con- vex conjugation (ZZuu et al., 2022), see Lemma 1.1 or "connect-the-doss" ((Dorshenkoo et al., 2022), see Lemma D.16).
49

---

Deep Differentially Private Time Scries Forecasting
G. Proofs from Section 4.3 (Context-Forecast Split)
For this section, we focus exclusively on top-level sampling without replacement and bottom-level sampling with replacement. Our goal prove the following statement for (1, e--eentt-level privacy, where single element can change its value by most V:
Theorem G.I. Consider top-level sampling without replacement and bottom-level sampling with replacement with 1, batch size A, as well as context and forecast standard deviations FF. E (see Eq. (1)). Let r Le+LE and 1.-L++1
p |A / / N. Further define forecast-to-contes ratio
LF LotLs*
Define P(1) Mo.(u. with means
0 2] and weights p E [0, 1]2 with p1 P2 and
1-p2
P2 = p.r.
+ +p. (1- (VD
Then, the augmented per-step privacy profile 11 (a) sup
Ha HaMMlllMM fulfill
== Be
(a)a) - (() fa () a
The following special case from Section 4.3 immediately follows from setting oc Or:
Theorem 4.5. Consider X 1, batch size A, as well as context and forecast standard deviations ac, OF E RR with
=op. Let r Le+LE and LA / XJ N. Define P(1) MoG P) with means fa [o 2]² and weights L-L++I
p [0, 113. with P1 = P2 and
P2 p.r- TVD TVD (V(0,)))))
Lo with total variation distance TVD(P. Q) (P(Q))) Then. (aa) sup
Ha (MMllMM)) fulfills
x s2
Ha (a(PP))IN(OOO)) lf (a((().0)))(())) f
(()) -
To prove these results, let us
1. Bound the privacy profile of M via constructing conditional coupling between mixture decompositions of maximal couplings, leading yet another divergence maximization problem involving multivariate Gaussian mixtures,
2. and solve the resultant optimization problem using joint quasi-convexity of the hockey stick divergence.
G.1. Bound via Conditional Coupling and Maximal Couplings
For this section, we will use the following properties of maximal couplings, taken from (Balle et al., 2018) and Section 2.5 of (Den Hollander, 2012):
Proposition G.2. Consider arbitrary distributions P, P.Q. There exists coupling IT* of P. Q, referred to as maximal coupling, such that
1. II is an optimum of SuPne4(P..)) Pr(X,Y) ~ II[X = Y), where 4(P, Q) is the space of all couplings of P,Q,
2. II has marginals that decompose P (1 (())) + and Q (1 p(0)) +1))) with TVD(P, (P,QQ).. Q)-
As such, maximal coupling exactly correspond to our intuition of trying to determine the probability that we sample the same context and ground-truth forecast when a single sequence element changes its value by v.
Lemma G.3, Consider top-level sampling without replacement and bottom-level sampling with replacement with 1, batch size A, as well as context and forecast standard deviations o F T (see Eq. (1)). Let r -1-L+41
Lo+Lp and
50

---

Deep Differentially Private Time Series Forecasting
0 LA / / N. Further define forecast-to-context ratio Φ Lothp
Then, the augmented per-step privacy profile
H (a) = sup b2 Ha (MMMllMMa
fulfills
H(a) S max (PlQ))
(12)
P.QE
where Q is set of all pairs of multivariate Gaussian mixtures (P. Q) with P Eiz wy " 02-1) and Q
Σj= Wjr NN .2²1) satisfying
11 Mi
1
11 2
vi,j E f........ 67
l1 (2) Mi 1212222 22
vi,j {1, , 6}
(13)
l1 (2) M4 1011222 22
Vi,j [l.....
M: Ma
(2)
Vi 4).
with Vi: 44 E TR. and
W1 = (1 p)
W2 = P (1 r)
u3 P p. (1 (I-T
W4 P. r. (1 (1 (1 ((..
W5 /- p... T (W
Wg p. r..r. (.- (WV)
Proof. Let B. RLLotLe - R be the mechanism that adds isotropic Gaussian noise pair of context and forecast windows, computes the resultant gradient, and adds isotropic Gaussian noise to the elements of the output gradient. Note that this mechanism is just another subsampled mechanism, where the subsampling distribution happens to be continuous. We can thus apply the usual approach based on joint couplings of conditional subsampling distributions. To this end, let us decompose the mechanism via B- = B o S, where
S(a) [[a[] Lc] Zz) (alLe +1:]+2))'7
with Zp oZ 22 12
ZF NOO, oz u² I).
We know from our derivations Appendix F and specifically Lemma F.5 that fi s (PllQ)
P= (1-p) Ba + p. (1-11) p.r. 6. Bo, +p- (1- (1 Bac
Q = (1 p) Ba +
p. p. (1- B.r + p.r. r.r.g 6. Ba, + +p. (1 Bag.
1. for some worst-case tuple of subsequences a, a', a'',''p a'p,'' E Lo where (a'p) =E (ak)), (d') = (a"), subse- quences ap, d'p only differ in their last LE elements (forecast window), subsequences ac, de only differ in their first Lo elements (context window), and the first mixture components are identical between the two mixture distributions.
We know that ||a'r- al S e and that they only differ in one element in the forecast window. Thus, TVD ||S.g) S TVD(N (1), (F). For brevity, let define TF TVD(V ( Using maximal couplings, we restate Bag and Bag as sums of two mixtures where the first summand is identical, i.e.,
/ Sptcter [(z)) d S (z) T
Boq TF)
B(2) d (2),
2hotzp
[ 3lotth
Bag = (1-TF):
|glotte B(2) d
S
1 (2) TTF
B(2) (2).
Similarly, we know that |ldc- - d''ll < v and that they only differ in one element in the context window. Thus, TVD(S 11Sag) I To with TC (VD Using maximal couplings, we can thus also restate
51

---

Deep Differentially Private Time Series Forecasting
Bogg and Boy sums of two mixtures where the first summand is identical, i.e.,
(00) Bag = (1-Tc): 1 Sglotie B(z) d
Sale (2)+ Te
/ Jhiethic
B(z) d (x),
Bug = (1 - TC) (1-Tc) Spectte B(z) d
50
(z) To de
{ B (z).
RRoete
Using the usual coupling toolkit, we can now define a continuous coupling between the six subsampling dis- 5(1) from the first mixture distribution and the six subsampling distributions L
tributions S. Sa s(0) s(0) s(1)
Since the first to fourth mixture component are identical, we can trivially construct a coupling I such that the first to fourth element are identical for all pairs of tuples of subsequences in the support of T.
S. Sep aa Lup -
((0) (1) s(1)
We can then rewrite all subsampling distributions as marginals of the coupling and move the coupling outside the hockey stick divergence using joint convexity (i.e., the approach from (Schuchardt et al., 2024)). Finally, we can conclude our proof by recalling that the gradient function g : Rhotle R underlying (2) is clipped norm of C' and yields identical results for identical inputs.
G.2. Worst-Case Mixture Components
Next, we can solve the optimization problem in Lemma G.3 for a 2
Lemma G.4. For a 2 1, an optimal solution to the optimization problem in Lemma G.3 is given by pá pi
(1)
(1) = 2e1
L1 $1si54:00 (1) 0, and S sisa 4: n 0, where e₁ the first canonical unit vector.
(1) 0221 and Q EE= W. Proof. Consider any feasible solution our optimization problem P= Ei- w. NN4
N N(u,
(2) 0,221 that fulfills
1 (1) 2
Vi,j E (1.....0) 6}
l| (2)
2 (2) 1
Vi,j E 6
(14)
[1 Mij 1 Pll522 2
Vi,j E 61.....6}
u: (1) = μ.
(2)
vi 41.
(1) with Vi : pi 11, ER..
Since P and Q are identical in their first four components, have via the advanced joint convexity property (Lemma D.2):
(all))Q) = (ws + ws) H. (P'))
with some a' 2 a and some mixture weights W/ W6 w
(11) (1) (2)
..... w
12)
and
p' p'= u N(,
(1) (1) 0²1) + w
11)
N(u 11)
(2) Q' w N( 2 ,
Since hockey stick divergences are jointly convex, they are also jointly quasi-convex and thus (ws + w6) Ho. (P')
<(ws + w6) max max H ( o2)) jE(
<(w; + w6) H., o2
The last inequality follows from our distance constraints and the fact that the hockey stick divergence between two Gaussians monotonically increasing with the distance of their means (see Lemma D.7 for formal statement).
52

---

Deep Differentially Private Time Series Forecasting
The result finally follows from applying advanced joint convexity in reverse order, i.e.,
(ws + w6) Ho' o2
6
=(ws + w6) Ha. Σ
N2e1, 2
r)ll
Σ
m
12)
N
=Ha
wf
(1)
N
Σ
w
(1)
N2e1, 2 1)
Σ
w
(2)
j=1
Our main result Theorem G.1 then follows immediately from marginalization and the following lemma ((Zhu et al., 2022)):
Lemma D.10. Let be symmetric neighboring relation dataset space X. It then holds that au Ha (M (M (Ma)) = (P,,, Q) for all a 2 1 if and only if sup Ha (Ma s Ha(Q, P) for all O < a S 1.
53

---

Deep Differentially Private Time Series Forecasting
H. Inference Privacy
As discussed in Appendix H. our work and other works on DP-SGD (e.g. (Abadi et al., 2016)) focus on ensuring privacy of parameters to guarantee that information from any training sample zn (here: sequences) does not leak when releasing model fe or making predictions fIm (here: forecasts) for other data Im- However, as our data evolves over time, there may also be scenarios where one wants to release forecast fo (z while simultaneossly ensuring that no sensitive information from Zi is leaked. Of course, the context window Le for generating this forecast will be much smaller than the size of an entire training set, i.c., it will be harder to obfuscate any individual element with noise while retaining high utility,
direct approach to the problem, which has already been explored in (Li et al., 2019; Arcolezi et al., 2022) is adding calibrated Gaussian noise to time series Zip to ensure (ur, -eventt- or (w, v) -user-elel privacy when releasing So (āa) with noised time series Znn
In the following, explore whether For this purpose, we apply Theorem 3.2 from (Koga et al., 2022), i.c., privacy amplification for time series release via Poisson subsampling. Rather than using this mechanism for downstream analysis, we use their mechanism to subsample our time series, and then impute the missing values with the remaining average, and then apply our model fe to the subsampled, noised, and reconstructed time series.
improve the
trade-off of random input perturbations using
Experimental Setup. We use the same hyperparameters as in Appendix B, except for two changes: First, we omit DP-SGD training since already enforce privacy at inference time. Second, since our privacy now independent of context length and batch size, for solar -1 Sominuutes... which we found to lead to much better CRPS for non-private training during hyperparameter search on the validation set.
we use Lc 8, A 64 for traffic, Lc 2, A = 64 for elect Electricity and Le = 2, A 128
Tables 11 to 13 show the resultant test CRPS with varying Poisson subsampling rate r and Gaussian noise calibrated such that we attain the desired e, On traffic and solar.10.minut subsampling with r = 0.3 or r 0.75 yields better CRPS for small E, while there is no improvement on electricity. This confirms that subsampling at inference time can in some circumstances improve utility while enforcing inference-time privacy for sequence V.n when releasing forecast fo(x,). Of course, there are various opportunities for further improving utility, c.g., via neural denoising imputation.
Again, this is not the primary of our work (or any other work on DP-SGD), and we only included this discussion for completeness.
Table 11: CRPS for t traffic when enforcing inference-time privacy with 0.1, 6 1e-,, Bold font indicates the best Poisson subsampling rate r' per model (collection of three rows).
MODEL
0.5
1
4
SIMPLEFF (r 1.0)
7.611 11.714
2.630
10.311
1.030
10.029
0.543
10.017
0.348
10.006
SIMPLEFF 0.75)
6.367 +1.398
2.164
20.244
0.880
#0.022
0.502
#0.011
0.352
20.004
SIMPLEFF (r (-= 0.5)
5.521 +1.430
1.799
20.260
0.748
20.020
0.479 #0.005
0.381 #0.002
DEEPAR (r -1.0)
1.754 10.268
1.026
10.091
0,685
1:0.887
0.522
100035
0.425 1:0034
DEEPAR (r == -0.75)
1.376 10.178
0.856
20.055
0.622 20.033
0.512 20.040
0.445 20.042
DEEPAR (r = 0.5)
1.019 40.095
0.709
20.035
0.575
20.032
0.510 20.043
0.463 20.047
DLINEAR (r- = -1.0)
4.262 #0.061
2.251
#0.031
1,221
40.017
0.707
4-0.099
0.442 #0.005
DLINEAR (r = 0.75)
3.473 10.046
1.863
025
1.044
10.014
0.637
20.008
0.430 20.005
DLINEAR (r 0.5)
2.650 10.037
1.463
20.020
0.870 10.011
0.580 10.007
0.438 =0 004
SEASONAL (r 1.0)
7.871 10.010
4.273 =0 008
2.358 10.003
1.350 10.002
0.827 10.001
54

---

Deep Differentially Private Time Series Forecasting
Table 12: CRPS for e electricity when enforcing inference-time privacy with v == 10, 6 = 1 1e-4 Bold font indicates the best Poisson subsampling rate r per model (collection of three rows).
MODEL
0.5
= 1
=
4
SIMPLEFF (r = 1.0)
0.060 40.000
0.058
#0.058
0.057
#0.057
0.056
#0.056
0.056
#0.056
SIMPLEFF (r -0.75)
0.118 40.118
0.117 #0.117
0.116
40.116
0.116
10.116
0.116
#0.116
SIMPLEFF 0.5)
0.179
0.178 #0.178
0.178
40.178
0.178 +0.178
0.177 #0.177
DEEPAR (r =1.0)
0.055 10.055
0.053
20.053
0.052
20.052
0.051 10:051
0.051
20.051
DEEPAR (r 0.75)
0.112
0.111 #0.111
0.111
0.110
+0.110
0.110 #0.110
DEEPAR (r 0.5)
0.169 10.169
0.168 #0.188
0.168
#0.108
0.168 +0.
0.168 #0.168
DLINEAR -1.0)
0.063 10.063
0.059
20.059
0.058 10 058
0.057
10.057
0.057
#0.057
DLINEAR (r 0.75)
0.125 126
0.122
#0.122
0.122
10.122
0.121
10.121
0.121
#0.121
DLINEAR (T 0.5)
0.186 180
0.184 #0.184
0.184
18.184
0.183 10.188
0.183 #0.183
SEASONAL (r 1.0)
0.079 10.000
0.074 2: 000
0.071 1:00000
0.070 10.000
0.070 10.000
Table 13: CRPS for solar_10 minutes when enforcing inference-time privacy with = 1,8 = 1e 14-4, Bold font indicates the best Poisson subsampling rate per model (collection of three rows).
MODEL
= 0.5
== 1
=
= 4
SIMPLEFF (r = 1.0)
3.999 +2.246
1.791
$0.088
1.102
10.103
0.897 40.076
0.836 #0.079
SIMPLEFF (r 0.75)
3.280 11.701
1.457
#0.401
0.971
#0.093
0.868
+0.009
0.850
#0.073
SIMPLEFF 0.5)
3.022 11.723
1.441
10.386
1.032
10.097
0.936
10.045
0.921 10.034
DEEPAR (r =1.0)
2.483 #1.071
1.361
20.290
0.892
20.078
0.712
#0:024 0.873
0.641
#0.020
DEEPAR (r -0.75)
2.257
1.405
#0.321
1,021 40.146
0.804 #0.087
DEEPAR (r 0.5)
2.123 10.081
1.565
40.00 400.403
1.304
10.2777
1.206 4:0.28
1.167 :00212
DLINEAR -1.0)
2.792
10.154
1.783
050.
1. 1.289
.2.022
1.043
#0.017
0.918
20.021
DLINEAR (r 0.75)
2,443 40.157
1.663
#0.008
1.305
4.0.061
1.150
40.049
1,088
#0.041
DLINEAR (r 0.5)
2.187 423
1.640
+.0.89
1.419 4-0.733
1.340
+0.002
1.315 40.057
SEASONAL (r 1.0)
9.461
10.1
5.485 20 20.059 059
3.433 400029
2.371
10.014
1.816 20.008
55

---

Deep Differentially Private Time Scries Forecasting
I. Generalizations
For the sake of exposition, and to spare our readers from even further complicating the already involved notation in some of our later proofs, we made certain simplifying assumptions about the shape of the time series, and focused on analyzing 1-event and (1, -event level privacy,
In the following, we discuss how these restrictions can (except for one case involving ampiification.yy-aggmeennt with ac + aP) be easily lifted.
L1. Shape of Time Series
Lc + LF, which means that the first element x.. [1] of time series In appears (after zero-padding with length Lc) in Le + LF different time series at different positions. If L - LF + 1 < Lc + LF, then all context windows will always contain some of the padding elements. Thus, the maximum number subsequences an element can contribute to is max(0, min + Lp, L - Lp + 1}}. Since all our proofs are only dependent on number of subsequences that contain a specific sensitive element, and the fact that there are no duplicate appearances in a subsequence, one can replace Le LF with max (0, min Lc + Lr, L LF + 13} in all our guarantees cover this edge case.
Minimum Length. The first simplifying assumption we made was that
Variable length. Using the same stochastic dominance argument as in our proof of Appendix E.3, one can show that all our upper- and lower bounds for bottom-level sampling with replacement are monotonically increasing in maac(0, (Lc (Lottr,L--tttt)) Thus, given dataset composed of variable-lengte sequences, one evaluate our bounds L-L5+1 using whatever length maximizes the above two functions. The tight bounds will remain tight, since we have to make the worst-case assumption that exactly this optimal-length sequence is changed under our neighboring relation.
Dimensionality. None of our proofs use the fact that our dataset space is X = P(IR)) as opposed to X = P(RLXD.)) - except for our amplification--by
antiiattioo-b---uummmttttttonnnn augmentation proof from Lemma G.3 for (1, u)-event privacy. If we interpret v as implying that Vn, Vt ||>,, it] z,, [3]l22 S u, then the proof are identical. we interpret e as implying that Vn, Vt, Vd [en(l, d] xn [t, d]], then the maximum total variation distance between two subsequences that differ in the same element increases to TVD (O) (V o)) and we need to adjust the bound accordingly. Thus, methods can in principle also be applied to highly-dimensionss time series such videos.
1.2. Neighboring Relations
Finally, we can generalize our bounds to (w, evvent and (w, uuer privacy with U
Bottom- and Top-Level Subsampling. Our proofs for bottom- and top-level sampling only depend on the number of subsequences that contain at least one element of any specific individual (see, e.g., Appendix E.1.2 where we abstract our analysis k-group-subsee substitutions). Under the (w, eevntt neighboring relation, all elements are adjacent and thus this number is given by max(0, min Lc + LF + w - 1, L - LF + 1}}. Under the (w, e--user neighboring relation, all elements can be placed arbitrarily far from each other. One can thus place them such that every subsequence only ever contains a single element, i.e., max(0, minsw- (Lc LF), L Lr + 1}}.
Amplification by Data Augmentation. In the case of oc OF (Theorem 4.5), our guarantee is only dependent on the maximum magnitude of change between two time series that differ in the same indices. We can thus adjust our bound by using TVD (N,
o)). Only our guarantee for a. * aF cannot be easily generalized, because our proof of Lemma F.5 explicitly makes a case distinction based on whether an element appears in the context window or the forecast window. Future work would need to generalize our proof make a fine-grained case distinction over the number of elements that appear in the context window and in the forecast window.
56


Reviews:
[{"review_id": "S48XyhjDkX", "reviewer": "Reviewer_r1DZ", "summary": "This paper studies privacy amplification under subsampling when working with forecasting models on time series data. In these cases, the dataset usually consists of sequences, and subsampling occurs on multiple levels: top-level sampling chooses a subset of sequences, bottom-level sampling chooses a subsequence from each of these layers, and then the subsequences are split into context and forecast (after which a model is trained on this data via Noisy SGD w Gaussian noise). The paper studies thoroughly how these various sampling choices impact privacy amplification by subsampling both analytically and empirically, making the following observations (among some others):\n\na) They show that as one would expect, when the top-level sampling scheme is deterministic, and the bottom-level sampling is sampling $\\lambda$ sequences without replacement, for a fixed batch size, $\\lambda=1$ corresponds to the most per-epoch privacy. They also tightly characterize the privacy profile in this case. Next, they consider that when $\\lambda > 1$, fewer epochs are needed for the same number of training steps, and hence ask whether $\\lambda=1$ is still an optimal choice when you hold the number of training steps fixed (as opposed to a per epoch type guarantee). They numerically show that this is the case, by showing a lower bound on the per epoch privacy profile for $\\lambda > 1$ and compare that to the tight profile for $\\lambda=1$. Applying composition, they show that in many ranges of $\\epsilon$ (and for various settings of other parameters), $\\lambda=1$ continues to be an optimal choice.\n\nb)  Next, they consider the effect of using sampling wor for top-level sampling and bottom-level sampling. In this case, they analytically show that per-step privacy profile is indeed additionally amplified roughly by the probability of sampling a sequence in the top-level. They also numerically show that this scheme gives amplification over deterministic top-level sampling at a per-epoch level (by applying composition on their per-step guarantee).\n\nc) Finally, in cases where the values in neighboring datasets can change in bounded ways ($+v$ or $-v$) they consider randomizing the context and forecast by adding Gaussian noise (in addition to top and bottom level sampling wor), and show that this further amplifies the privacy (the quantitative guarantee depends on the variance of the noise added). \n\nThey also carry out some experiments to measure whether utility can be maintained while training on common benchmarks using many models of interest. They use tools built in prior work on privacy amplification by subsampling (couplings and dominating pairs) in their theoretical analyses.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and great questions!\nPlease note that we cannot update the manuscript during the current rebuttal phase, but will integrate your feedback as soon as possible.\n\n### Sampling choices/parameters for model training\nThank you for pointing out this ommission. **We will of course specify these additional parameters** in Section 5.2.\n\nOur 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)$.\nThe remaining parameters are already specified in Appendix B.2.\n\n### Effect of Sampling Choices on Utility\nBased 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.\nDue to the character limit on rebuttals, please see our response to Reviewer 3 for details.\n\n### Prior Work on Graph DP\nThank you for pointing us to the work by Kasivishwanathan et al (2015).\nWe will reference their work - as well as Nissim et al. (2007), who first studied edge privacy - in Section 1.\n\n### 1 - Dominating Pairs for Substitution\nYou 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.\n\nPlease 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.\nOur 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.\n\n**We will update ll. 264-266 of the \"Other Guarantees\" paragraph to**:  \n\"Thus far, dominating pairs for *sampling with replacement* have only been known for individual substitutions. Thus, these guarantees are of interest beyond forecasting\".\n\n### 3 - Why a Single Subsequence is Preferable Under Composition\nYou 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.\n\nHowever, 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.\nUnlike pointwise addition, this is a non-linear functional operating on entire privacy profiles and may thus change their ordering.\n\nWe 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).\n\nWe 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.\n\n**To make this clearer to readers, we will update Section 4.5 as follows**:  \n\"[...], 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.\"\n\n### 2 - Why Top-Level Sampling is Preferable\nAs 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.\n\n### 4 - Relative Improvement under Composition\nThank you for pointing out this inconsistency. **We will use the following formulation instead**:  \n\"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.\"\n\nWe 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:\nhttps://figshare.com/s/4292ea34e216427a0ded\n\n\n### 5 - Interpolation on Page 20\nWe agree that interpolation makes the figures on p. 20 somewhat hard to read, and will remove it:\nhttps://figshare.com/s/9a3282037c6d268cd37a\n\n---\n\nThank you again for your review!\nPlease let us know if you have any additional questions during the discussion period.\n\n---\n\nNissim et al. Smooth sensitivity and sampling in private data analysis. STOC 2007.", "claims_and_evidence": "Most of the claims (described in the summary) are supported with convincing evidence. The claim about utility (CPRS) not being significantly compromised when training models with privacy was confusing to me- I wasn't able to find in the section a detailed overview of the sampling choices that were made when training these models.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria make sense for the problem at hand- one additional evaluation critera that would have been useful when comparing the sampling schemes is not just the privacy level but the utility obtained for the same privacy parameters with different sampling schemes (for e.g. when using sampling wor at the top level, you'd expect to see the same data point more frequently, which may result in worse utility than the deterministic scheme for the same number of epochs, even though you have better privacy).", "theoretical_claims": "I skimmed the proofs of the theoretical claims in the supplementary material and they seemed reasonable. I did not check all the proofs in detail.", "experimental_designs_or_analyses": "Yes, I checked the soundness of all the experimental designs for the claims described in the summary. One question I had was re the sampling scheme used in the utility experiments (see methods and evaluation criteria), but the experimental design seemed largely reasonable.", "relation_to_broader_scientific_literature": "This paper studies privacy amplification via subsampling for more complex multi-level subsampling schemes frequently used in forecasting models with time series data. It fits into a long line of work on privacy amplification via subsampling, but most prior work has been on subsampling for static datasets. The relatively sparse literature on bi-level sampling schemes for private deep-learning has not considered the interplay of privacy amplification effects of applying sampling to multiple levels.", "essential_references_not_discussed": "Most essential references are discussed. In the intro, when referencing graph data, a number of key early citations on privatizing graph properties are missed and other citations are given instead (see the full version of 'Analyzing Graphs With node Differential Privacy' by Kasivishwanathan Nissim Raskhhodnikova Smith in 2015 and the citations therein). However, this is a relatively tangential set of citations and not as relevant to the paper so I don't think it a big omission.", "other_strengths_and_weaknesses": "The main strength of the paper is its thoroughness; the privacy profiles of many combinations of top-level and bottom-level sampling schemes are explored in detail, both analytically and experimentally and natural choices there-in and how to make them are discussed.\n\nI don't see any major weaknesses to discuss other than clarifications about the utility experiments that would be useful. I do think comparing the utilities of the various sampling choices (as opposed to purely the privacy amplification obtained) would have made the paper even more impactful, but that's a natural point for future work.", "other_comments_or_suggestions": "1) In the 'other guarantees' section on page 5 I was confused about the point regarding dominating pairs for substitution relations- shouldn't dominating pairs for addition/removal yield ones for substitution (since substitution corresponds to a removal as well as an addition)?\n\n2) On page 6, some more reasoning about why the epoch-level guarantees are better when using subsampling at both the top and bottom levels would be useful (since on the epoch level one might expect that the benefits of top-level subsampling without replacement vanish).\n\n3) I did not understand the explanation on page 7 for why composing many $\\lambda>1$ steps  results in larger privacy loss than $\\lambda =1$ for a wider range of $\\epsilon$ than for a single step, shouldn't the individual $\\delta(\\epsilon)$ for each step add resulting in similar effects in the many-step case? More explanation here would be very helpful.\n\n4) On page 16 the authors say \"In all cases, we observe that λ = 1 improves its privacy relative to other λ > 1 after 100 training steps\"- but this claim seems untrue in figure 5 so a more nuanced claim needs to be made (however, it is true in figures 6 and 7).\n\n5) On page 20, the interpolation of the graphs makes them a lot more confusing, for a while I thought $\\lambda=16$ was the best in figure 10a until I read the text in detail. Might be worth presenting without interpolation.", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uaEtq31QVU", "reviewer": "Reviewer_GCw3", "summary": "This paper investigates the problem of training forecasting models (specifically those that leverage the temporal structure directly in their architecture) on both univariate and multivariate time series data. As is present most prior work on DP-SGD, amplificaton is a key result necessary for achieving realistic privacy-utility tradeoffs on deep learning tasks. The authors focus their work in this paper on deriving a structured subsampling procedure that provides similar amplificaton guarantees for these forecasting models. Finally, they demonstrate the new privacy utility tradeoffs when using this subsampling procedure.\n\n### Update after rebuttal ###\n\nThe authors have addressed my concerns and provided sufficient detail about how the accounting was implemented. Thus I feel confident about this utility of this new subsampling mechanism for practice. Thus, I have maintained my score at Accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\nPlease note that we cannot update the manuscript during the current rebuttal phase, but will integrate your feedback as soon as possible.\n\n### Motivation for Section 5.2\nUpon 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.\n\n**Based on your feedback, we will replace the first paragraph of Section 5.2 with the following**:  \n\"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.\"\n\nPlease let us know if there are other parts of Section 5.2 that you think should be improved.\n\n### Implementation of Bounds\nFor reference, the bounds for $\\lambda=1$ in Theorems 4.2, 4.4, and 4.5 are of the form\n$\\begin{cases}\nH_\\alpha((1-q) \\cdot N(0, \\sigma) + q \\cdot N(2, \\sigma)|| N(0,\\sigma) ) & \\text{if } \\alpha \\geq 1\\\\\\\\\nH_\\alpha(N(0,\\sigma) || (1-q) \\cdot N(0, \\sigma) + q \\cdot N(2, \\sigma) ) & \\text{if } \\alpha < 1\n\\end{cases}$\nwhere $q$ depends on the neighboring relation, top-level scheme, bottom-level scheme, and amount of Gaussian data augmentation.\n\nThe 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).\n\nFor $\\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`. \n\nFor $\\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)\n\n### Motivation for Bi-Level Subsampling (LLMs?)\nThe 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.\n\nInstead, 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](https://ts.gluon.ai/stable/api/gluonts/gluonts.dataset.loader.html) and bottom-level sampling is implemented by an [InstanceSampler](https://ts.gluon.ai/stable/api/gluonts/gluonts.transform.sampler.html).\n\n**Based on your feedback, we will replace the first sentence of Section 4.2 with the following**:  \n\"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\".\n\n### Application to LLMs\nThere is in fact nothing that would prevent the direct application to token/sentence-level private self-supervised training with teacher forcing.\n\nJust 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.\n\n\nBased 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.\n\n---\n\nWe hope that we addressed all your comments to your satisfaction.\nPlease let us know if you have any additional questions during the discussion period.", "claims_and_evidence": "The claims in the submission are supported with theoretical analysis, which is necessary for amplifcation results. Their empirical results are less focused on the main claim of the paper and an investigation of the impact of the main contribution of the paper.", "methods_and_evaluation_criteria": "The proposed methods are well motivated for the forecasting problem, especially compared to assumptions placed by prior work that would lead to worse privacy-utility tradeoffs. Structured subsampling of the time sequences in a novel way that results in new amplification results is directly applicable to the forecastijng domain.", "theoretical_claims": "I checked the correctness of the proofs in Section 4. While it is possible I may have missed minor details, from my current understanding these proofs are sound.", "experimental_designs_or_analyses": "Yes, I checked the soundness and validity of the experimental designs. I have no issues for the choices made.", "relation_to_broader_scientific_literature": "This paper combines existing techniques in randomization to achieve privacy amplification in a new way for time series data. This builds upon a recent set of work by Li et al. and Kogi et al. to provide amplifcation results in the time series domain. Additionally, it provides a new way to train deep learning time series models with differential privacy. This is especially important for privacy-sensitive domains such as healthcare and finance where time series data is abundant.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n\n- Novel amplification theory for time series data\n- Well-written theoretical section\n- Widely applicable result to enable better DP learning of time series data\n\nWeaknesses:\n\n- Section 5.2 could benefit from improved writing and detail for clarity and motivation", "other_comments_or_suggestions": "None.", "questions_for_authors": "1. In the appendix the authors state that they use the `dp_accounting` library in their experiments. I'd like to understand how the amplification result presented in the paper was implemented with that library. Since it doesn't support this new result how was it incorporated? (i.e. how should I think about this result as an analogy to the q parameter that represents the sampling probability of batch)\n2. The bi-level sampling seemed primarily motivated by LLMs but there are no natural language results? What do you see as the obstacles for adapting the method for that original motivation?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qYL2wpRFVB", "reviewer": "Reviewer_gQDa", "summary": "This paper studies privacy amplification with structured subsampling, for applications in DP-SGD training on forecasting models. The sampling considered works by first selecting a subset of time series (top-level sample), then one or more contiguous subsequences per sample (bottom-level sample), and finally splitting each subsequence into a context window and ground-truth forecast. The authors derive event- and user-level privacy guarantees for sampling contiguous subsequences. They also study the tradeoffs between the choice of parameters for the top or bottom level sampling, and show that composing batches of many top-level sequences is optimal for the privacy guarantees. To handle the privacy of the context/forecast windows, the authors propose data augmentation with Gaussian noise.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and great suggestions for further expanding our experimental evaluation!  \nPlease note that we cannot update the manuscript during this phase, but will integrate your suggestions as soon as possible.\n\n## Additional experiments/baselines\n\n### Effect of subsampling parameters on utility, independent of privacy\nThere are three key parameters: How we select sequences (\"top-level\"), how many subsequences $\\lambda$ we sample per sequence, and batch size $\\Lambda$.\n\nIn the following, we first let $\\lambda=1$ (like in our other experiments), and vary the top-level scheme and $\\Lambda$:  \nhttps://figshare.com/s/490812bd1b089d5c1dc5  \nLarger 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.  \nBased on this observation, we choose large batch sizes $\\Lambda=128$ and vary $\\lambda$:  \nhttps://figshare.com/s/c4068a78b2d4f06aee25  \nThere is no significant difference between $\\lambda=1$ and $\\lambda=16$, and no top-level scheme consistently outperforms any other.\n\nWe will add these results to Appendix C.2 and reference them from 5.2 to motivate our parameter choices for DP training.\n\n### Black-Box DP-SGD Baseline\nThank you for this suggestion, which will let us better explain to readers why structured subsampling is preferable to standard DP-SGD.\n\nWith 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.\nFor $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$)**\n\nLike 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 \n$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.\n\nThe 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$:  \nhttps://figshare.com/s/c061340645d5132c4a7e  \n**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.\n\nWe 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), [...]\".\n\n### Wider range of $\\varepsilon$ in Table 1\nThank you! We expanded the set of $\\varepsilon$:\nhttps://figshare.com/s/bbef7e6e8ad6ce500bf1\n\n---\n\n## Novelty of Techniques\nSince 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).\n\nPlease 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).\n\nFurthermore, applying couplings still requires non-trivial efforts (defining partitionings, proving validity of couplings, identifying distance constraints, deriving worst-case components given constraints,...)\n\n## Applications Beyond Forecasting\nWhile we focus on forecasting, the underlying approach generalizes to multiple domains:\n\n1. 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).\n2. 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).\n3. 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).\n\nBased 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.\n\n---\n\nThank you again for your efforts!\nPlease let us know if you have any additional questions during the discussion period.\n\n---\n\nZhu et al. Optimal Accounting of Differential Privacy via Characteristic Function. AISTATS 2022", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "- It might be good to include results on a wider range of epsilon in Table 1, or to include a plot.", "theoretical_claims": "I did not check the proofs in the appendix.", "experimental_designs_or_analyses": "- The authors mainly study the theoretical privacy guarantees of the different subsampling parameters. However, it would also be informative to empirically compare how the subsampling affects the utility of the model, independent of the privacy guarantees, so that we can know whether improvements are due to the privacy analysis or the choice of subsampling parameters. This would be a useful baseline to know how much the new privacy analysis improves on the results.\n- It might be good to compare against a baseline using DP-SGD in a black-box manner, to better demonstrate the improvements from the new analysis.", "relation_to_broader_scientific_literature": "The authors are the first to study the privacy analysis for this particular type of structured subsampling used in forecasting, though the techniques used are not new.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n- Privacy analysis is thorough and the tradeoffs between the subsampling parameters are studied in detail.\n\nWeaknesses:\n- The analysis seems very specific to the application in forecasting models, and it is unclear whether their results will be useful in other applications.\n- The techniques used are not novel, and the main novelty is applying existing techniques to a new application.\n- It would be good to have more experimental baselines to determine the impact of the new analysis.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- How do the subsampling parameters affect the model utility, independent of the privacy analysis?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a theoretical and empirical study of privacy amplification in differentially private training of models on time series data. It analyzes how structured subsampling affects differential privacy guarantees. Understanding this is particularly important since existing privacy amplifications mostly hold for unstructured (random) sampling from unstructured/unordered data, which is not true for time series data. The authors derive new amplification results tailored to this sequential data structure.  Empirical results demonstrate that these new techniques enable training forecasting models under strong privacy guarantees without substantially degrading utility.


Reviewers found the paper’s theoretical contributions to be thorough and well-motivated. The reviewers also found the analysis thorough with sound proofs. Multiple reviewers praised the work for extending privacy amplification techniques into a new domain, relevant for sensitive applications (e.g. analyzing time series data in healthcare and finance). The reviewers also raised several concerns. For example, multiple reviewers mentioned that the empirical evaluation could have better isolated the impact of the new privacy analysis on model utility, independent of the subsampling choices. 
Also, there was a concern about the breadth of the experimental comparisons. However, the authors response addressed most of the reviewers concerns, and the reviewers agreed on the overall significance of the contributions of the paper.
Decision: Accept (spotlight poster)