The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD

Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-23 22:14:43

Abstract: We propose a simple heuristic privacy analysis of noisy clipped stochastic gradient descent (DP-SGD) in the setting where only the last iterate is released and the intermediate iterates remain hidden. Namely, our heuristic assumes a linear structure for the model.

We show experimentally that our heuristic is predictive of the outcome of privacy auditing applied to various training procedures. Thus it can be used prior to training as a rough estimate of the final privacy leakage. We also probe the limitations of our heuristic by providing some artificial counterexamples where it underestimates the privacy leakage.

The standard composition-based privacy analysis of DP-SGD effectively assumes that the adversary has access to all intermediate iterates, which is often unrealistic.
However, this analysis remains the state of the art in practice. 
While our heuristic does not replace a rigorous privacy analysis, it illustrates the large gap between the best theoretical upper bounds and the privacy auditing lower bounds and sets a target for further work to improve the theoretical privacy analyses.

Main paper: 
 introduction: 
 Differential privacy (DP) [DMNS06] defines a measure of how much private information from the training data leaks through the output of an algorithm. The standard differentially private algorithm for deep learning is DP-SGD [BST14; ACGMMTZ16], which differs from ordinary stochastic gradient descent in two ways: the gradient of each example is clipped to bound its norm and then Gaussian noise is added at each iteration.The standard privacy analysis of DP-SGD is based on composition [BST14; ACGMMTZ16; Mir17; Ste22; KJH20]. In particular, it applies to the setting where the privacy adversary has access to all intermediate iterates of the training procedure. In this setting, the analysis is known to be tight [NSTPC21; NHSBTJCT23] . However, in practice, potential adversaries rarely have access to the intermediate iterates of the training procedure, rather they only have access to the final model. Access to the final model can either be through queries to an API or via the raw model weights. The key question motivating our work is the following.Is it possible to obtain sharper privacy guarantees for DP-SGD when the adversary only has access to the final model, rather than all intermediate iterates?The question above has been studied from two angles: Theoretical upper bounds, and privacy auditing lower bounds. Our goal is to shed light on this question from a third angle via principled heuristics.Submitted to 38th Conference on Neural Information Processing Systems (NeurIPS 2024). Do not distribute.A handful of theoretical analyses [FMTT18; CYS21; YS22; AT22; BSA24] have shown that asymptotically the privacy guarantee of the last iterate of DP-SGD can be far better than the standard composition-based analysis that applies to releasing all iterates. In particular, as the number of iterations increases, these analyses give a privacy guarantee that converges to a constant (depending on the loss function and the scale of the noise), whereas the standard composition-based analysis would give a privacy guarantee that increases forever. Unfortunately, these theoretical analyses are only applicable under strong assumptions on the loss function, such as (strong) convexity and smoothness. We lack an understanding of how well they reflect the "real" privacy leakage.Privacy auditing [JUO20; DWWZK18; BGDCTV18; SNJ23; TTSSJC22; ZBWTSRPNK22] complements theoretical analysis by giving empirical lower bounds on the privacy leakage. Privacy auditing works by performing a membership inference attack [SSSS17; HSRDTMPSNC08; SOJH09; DSSUV15]. That is, it constructs neighbouring inputs and demonstrates that the corresponding output distributions can be distinguished well enough to imply a lower bound on the differential privacy parameters. In practice, the theoretical privacy analysis may give uncomfortably large values for the privacy leakage (e.g., ε > 10); in this case, privacy auditing may be used as evidence that the "real" privacy leakage is lower. There are settings where the theoretical analysis is matched by auditing, such as when all intermediate results are released [NSTPC21; NHSBTJCT23] . However, despite significant work on privacy auditing and membership inference [CCNSTT22; BTRKMW24; WBKBGGG23; LF20; SDSOJ19; ZLS23], a large gap remains between the theoretical upper bounds and the auditing lower bounds [AKOOMS23; NHSBTJCT23] when only the final parameters are released. This observed gap is the starting point for our work.We propose a heuristic privacy analysis of DP-SGD in the setting where only the final iterate is released. Our experiments demonstrate that this heuristic analysis consistently provides an upper bound on the privacy leakage measured by privacy auditing tools in realistic deep learning settings.Our heuristic analysis corresponds to a worst-case theoretical analysis under the assumption that the loss functions are linear. This case is simple enough to allow for an exact privacy analysis whose parameters are can be computed numerically (Theorem 1). Our consideration of linear losses is built on the observation that current auditing techniques achieve the highest ε values when the gradients of the canaries -that is, the examples that are included or excluded to test the privacy leakage -are fixed and independent from the gradients of the other examples. This is definitely the case for linear losses; the linear assumption thus allows us to capture the setting where current attacks are most effective. Linear loss functions are also known to be the worst case for the non-subsampled (i.e., full batch) case; see Appendix B. Assuming linearity is unnatural from an optimization perspective, as there is no minimizer. But, from a privacy perspective, we show that it captures the state of the art.We also probe the limitations of our heuristic and give some artificial counterexamples where it underestimates empirical privacy leakage. One class of counterexamples exploits the presence of a regularizer. Roughly, the regularizer partially zeros out the noise that is added for privacy. However, the regularizer also partially zeros out the signal of the canary gradient. These two effects are almost balanced, which makes the counterexample very delicate. In a second class of counterexamples, the data is carefully engineered so that the final iterate effectively encodes the entire trajectory, in which case there is no difference between releasing the last iterate and all iterates.Implications: Heuristics cannot replace rigorous theoretical analyses. However, our heuristic can serve as a target for future improvements to both privacy auditing as well as theoretical analysis. For privacy auditing, matching or exceeding our heuristic is a more reachable goal than matching the theoretical upper bounds, although our experimental results show that even this would require new attacks. When theoretical analyses fail to match our heuristic, we should identify why there is a gap, which builds intuition and could point towards further improvements.Given that privacy auditing is computationally intensive and difficult to perform correctly [AZT24] ,we believe that our heuristic can also be valuable in practice. In particular, our heuristic can be used prior to training (e.g., during hyperparameter selection) to predict the outcome of privacy auditing when applied to the final model. (This is a similar use case to scaling laws.) 
linearized heuristic privacy analysis: 
 Algorithm 1 Noisy Clipped Stochastic Gradient De- scent (DP-SGD) [BST14; ACGMMTZ16] function DP-SGD(x ∈ X n , T ∈ N, q ∈ [0, 1], η ∈ (0, ∞), σ ∈ (0, ∞), : R d × X → R, r : R d → R) Initialize model m 0 ∈ R d . for t = 1 • • • T do Sample minibatch B t ⊆ [n]including each element independently with probability q.Compute gradients of the loss ∇ mt-1 (m t-1 , x i ) for all i ∈ B t and of the regularizer∇ mt-1 r(m t-1 ). Clip loss gradients: clip ∇ mt-1 (m t-1 , x i ) := ∇m t-1 (mt-1,xi) max{1, ∇m t-1 (mt-1,xi) 2} . Sample noise ξ t ← N (0, σ 2 I d ). Update m t = m t-1 -η • i∈Bt clip ∇ mt-1 (m t-1 , x i ) +∇ mt-1 r(m t-1 )+ξ t . end for if last_iterate_only then return m T else if intermediate_iterates then return m 0 , m 1 , • • • , m T -1 , m T end if end functionTheorem 1 presents our heuristic differential privacy analysis of DP-SGD (which we present in Algorithm 1 for completeness; note that we include a regularizer r whose gradient is not clipped, because it does not depend on the private data x). We consider Poisson subsampled minibatches and add/remove neighbours, as is standard in the differential privacy literature.Our analysis takes the form of a conditional privacy guarantee. Namely, under the assumption that the loss and regularizer are linear, we obtain a fully rigorous differential privacy guarantee. The heuristic is to apply this guarantee to loss functions that are not linear (such as those that arise in deep learning applications). Our thesis is that, in most cases, the conclusion of the theorem is still a good approximation, even when the assumption does not hold.: R d → R is linear if there exist α ∈ R d and β ∈ R such that (m) = α, m + β for all m.Theorem 1 (Privacy of DP-SGD for linear losses). Let x, T, q, η, σ, , r be as in Algorithm 1. Assume r and (•, x), for every x ∈ X , are linear.LettingEQUATIONDP-SGD with last_iterate_only satisfies (ε, δ)-differential privacy with ε ≥ 0 arbitrary and δ = δ T,q,σ (ε) := max{H e ε (P, Q), H e ε (Q, P )}.(2)Here, H e ε denotes the e ε -hockey-stick-divergence H e ε (P, Q) := sup S P (S) -e ε Q(S).Equation 1 gives us a value of the privacy failure probability parameter δ. But it is more natural to work with the privacy loss bound parameter ε, which can be computed by inverting the formula:EQUATIONBoth δ T,q,σ (ε) and ε T,q,σ (δ) can be computed using existing open-source DP accounting libraries [Goo20] . We also provide a self-contained & efficient method for computing them in Appendix A.The proof of Theorem 1 is deferred to Appendix A, but we sketch the main ideas: Under the linearity assumption, the output of DP-SGD is just a sum of the gradients and noises. We can reduce to dimension d = 1, since the only relevant direction is that of the gradient of the canary 1 (which is constant). We can also ignore the gradients of the other examples. Thus, by rescaling, the worst case pair of output distributions can be represented as in Equation 1. Namely, Q = T t=1 ξ t is simply the noise ξ t ← N (0, σ 2 ) summed over T iterations; this corresponds to the case where the canary is excluded. When the canary is included, it is sampled with probability q in each iteration and thus the total number of times it is sampled over T iterations is Binomial(T, q). Thus P is the sum of the contributions of the canary and the noise. Finally the definition of differential privacy lets us compute ε and δ from this pair of distributions. Tightness follows from the fact that there exists a loss function and pair of inputs such that the corresponding outputs of DP-SGD matches the pair P and Q.1 The canary refers to the individual datapoint that is added or removed between neighbouring datasets. This terminology is used in the privacy auditing/attacks literature inspired on the expression "canary in a coalmine." Figure 1 : Comparison of our heuristic to baselines in various parameter regimes. Horizontal axis is number of iterations T and vertical axis is ε such that we have (ε, 10 -6 )-DP.In addition to privacy auditing, we compare our heuristic to two different baselines in Figure 1 .The first is the standard, composition-based analysis. We use the open-source library from Google [Goo20] , which computes a tight DP guarantee for DP-SGD with intermediate_iterates. Because DP-SGD with intermediate_iterates gives the adversary more information than with last_iterate_only, this will always give at least as large an estimate for ε as our heuristic.We also consider approximating DP-SGD by full batch DP-GD. That is, set q = 1 and rescale the learning rate η and noise multiplier σ to keep the expected step and privacy noise variance constant: DP-SGD(x, T, q, η, σ, , r) batch size ≈nq, T iterations, T q epochs ≈ DP-SGD(x, T, 1, η • q, σ/q, , r) batch size n, T iterations, T epochs .(4)The latter algorithm is full batch DP-GD since at each step it includes each data point in the batch with probability 1. Since full batch DP-GD does not rely on privacy amplification by subsampling, it is much easier to analyze its privacy guarantees. Interestingly, there is no difference between full batch DP-GD with last_iterate_only and with intermediate_iterates; see Appendix B.Full batch DP-GD generally has better privacy guarantees than the corresponding minibatch DP-SGD and so this baseline usually (but not always) gives smaller values for the privacy leakage ε than our heuristic. In practice, full batch DP-GD is too computationally expensive to run. But we can use it as an idealized comparison point for the privacy analysis. Figure 3 : For gradient space attacks with adversarial datasets, the empirical epsilon (ε) closely tracks the final epsilon except for at small step counts, where distinguishing is more challenging. This is evident at both subsampling probability values we study (q = 0.01 and q = 0.1). Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Section 4 discusses the limitations. 
experimental results: 
 We implement state-of-the-art attacks from prior work [NSTPC21; NHSBTJCT23] . These attacks heavily rely on the intermediate steps and, as a result, do not achieve tight results. In the next section, we design specific attacks for our heuristic privacy analysis approach to further understand its limitations and potential vulnerabilities. We used Google Cloud A2-megagpu-16g machines with 16 Nvidia A100 40GB GPUs. Overall, we use roughly 33,000 GPU hours for our experiments. where the other data points are designed to have very small gradients (≈ 0). This last setting wasshown by [NSTPC21] to result in tighter auditing. In all attacks, we assume the distinguisher has access to all adversarial gradient vectors. For malicious gradients, we use Dirac gradient canaries, where gradient vectors consist of zeros in all but a single index. In both cases, the distinguishing test measures the dot product of the final model checkpoint and the gradient canary. Indeed, auditing with this strong attack results even in much lower values than the heuristic outputs.Our other setting assumes the other data points are maliciously chosen. We construct an adversarial "dataset" of m + 1 gradients, m of which are zero, and one gradient is constant (with norm equal to the clipping norm), applying gradients directly rather than using any examples. As this experiment does not require computing gradients, it is very cheap to run more trials, so we run this procedure N = 100, 000 times with the gradient canary, and N times without it, and compute an empirical estimate for ε with these values. We plot the results of this experiment in Figure 3 together with the ε output by the theoretical analysis and the heuristic, fixing the subsampling probability and varying the number of update steps. We adjust the noise parameter to ensure the standard theoretical analysis produces a fixed ε bound. The empirical measured ε is close to the heuristic ε except for when training with very small step counts: we expect this looseness to be the result of statistical effects, as lower step counts have higher relative variance at a fixed number of trials.Input Space Attack: In practice, adversaries typically cannot insert malicious gradients freely in training steps. Therefore, we also study cases where the adversary is limited to inserting malicious inputs into the training set. Label flip attacks are one of the most successful approaches used to audit DP machine learning models in prior work [NHSBTJCT23; SNJ23] . For input space attacks, we use the loss of the malicious input as a distinguisher. Similar to our gradient space attacks, we consider two settings for input space attacks: one where other data points are correctly sampled from the dataset, and another where the other data points are blank images.Figure 4 summarizes the results for this setting. Comparing to Figure 2 , input space attacks achieve tighter results than gradient space attacks. This finding is in stark contrast to prior work. The reason is that input space attacks do not rely on intermediate iterates, so they transfer well to our setting.In all the cases discussed so far, the empirical results for both gradient and input attacks fall below the heuristic analysis and do not violate the upper bounds based on the underlying assumptions. This suggests that the heuristic might serve as a good indicator for assessing potential vulnerabilities.However, in the next section, we delve into specific attack scenarios that exploit the assumptions used in the heuristic analysis to create edge cases where the heuristic bounds are indeed violated.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Answer: [No] Justification: We intend to release the code eventually, but we are not able to do so at the moment; we refrain from providing a detailed reason, as this could violate anonymity. 
counterexamples: 
 We now test the limits of our heuristic by constructing some artificial counterexamples. That is, we construct inputs to DP-SGD with last_iterate_only such that the true privacy loss exceeds the bound given by our heuristic. While we do not expect the contrived structures of these examples to manifest in realistic learning settings, they highlight the difficulties of formalizing settings where the heuristic gives a provable upper bound on the privacy loss.We begin by noting the counterintuitive fact that our heuristic ε T,q,σ (δ) is not always monotone in the number of steps T when the other parameters σ, q, δ are kept constant. This is shown in Figure 1c .More steps means there is both more noise and more signal from the gradients; these effects partially cancel out, but the net effect can be non-monotone.We can use a regularizer r(m) = m 2 2 /2η so that η • ∇ m r(m) = m. This regularizer zeros out the model from the previous step, i.e., the update of DP-SGD becomesEQUATIONThis means that the last iterate m T is effectively the result of only a single iteration of DP-SGD. In particular, it will have a privacy guarantee corresponding to one iteration. Combining this regularizer with a linear loss and a setting of the parameters T, q, σ, δ such that the privacy loss is non-monotone -i.e., ε T,q,σ (δ) < ε 1,q,σ (δ) -yields a counterexample.In light of this counterexample, in the next subsection, we benchmark our counterexample against sweeping over smaller values of T . I.e., we consider max t≤T ε t,q,σ (δ) instead of simply ε T,q,σ (δ).Consider running DP-SGD in one dimension (i.e., d = 1) with a linear loss (m, x) = mx for the canary and a quadratic regularizer r(m) = 1 2 αm 2 , where α ∈ [0, 1] and x ∈ [-1, 1] and we use learning rate η = 1. With sampling probability q, after T iterations the privacy guarantee is equivalent to distinguishing Q := N (0, σ 2 ) andP := N ( i∈[T ] (1 -α) i-1 Bernoulli(q), σ 2 ),whereσ 2 := σ 2 i∈[T ] (1 -α) 2(i-1). When α = 0, this retrieves linear losses. When α = 1, this corresponds to distinguishing N (0, σ 2 ) and N (Bernoulli(q), σ 2 ) or, equivalently, to distinguishing linear losses after T = 1 iteration. If we maximize our heuristic over the number of iterations ≤ T , then our heuristic is tight for the extremes α ∈ {0, 1}.A natural question is whether the worst-case privacy guarantee on this quadratic is always given by α ∈ {0, 1}. Perhaps surprisingly, the answer is no: we found that for T = 3, q = 0.1, σ = 1, α = 0, DP-SGD is (2.222, 10 -6 )-DP. For α = 1 instead DP-SGD is (2.182, 10 -6 )-DP. However, for α = 0.5 instead the quadratic loss does not satisfy (ε, 10 -6 )-DP for ε < 2.274.However, this violation is small, which suggests our heuristic is still a reasonable for this class of examples. To validate this, we consider a set of values for the tuple (T, q, σ). For each setting of T, q, σ, we compute max t≤T ε t,q,σ (δ) at δ = 10 -6 . We then compute ε for the linear loss with quadratic regularizer example with α = 1/2 in the same setting. Since the support of the random variable i∈[T ] (1 -α) i-1 Bernoulli(q) has size 2 T for α = 1/2, computing exact ε for even moderate T is computationally intensive. Instead, let X be the random variable equal toi∈[T ] (1 -α) i-1Bernoulli(q), except we round up values in the support which are less than .0005 up to .0005, and then round each value in the support up to the nearest integer power of 1.05. We then compute an exact ε for distingushing N (0, σ 2 ) vs N (X, σ 2 ). By Lemma 4.5 of Choquette-Choo, Ganesh, Steinke, and Thakurta [CCGST24] , we know that distinguishing N (0, σ 2 ) vs.N ( i∈[T ] (1- α) i-1 Bernoulli(q), σ 2) is no harder than distingushing N (0, σ 2 ) vs N (X, σ 2 ), and since we increase the values in the support by no more than 1.05 multiplicatively, we expect that our rounding does not increase ε by more than 1.05 multiplicatively.In Figure 5 , we plot the ratio of ε at δ = 10 -6 for distingushing between N (0, σ 2 ) and N (X, σ 2 ) divided by the maximum over i ∈ [T ] of ε at δ = 10 -6 for distinguishing between N (0, iσ 2 ) and N (Binomial(i, q), iσ 2 ). We sweep over T and q, and for each q In Figure 5a (resp. Figure 5b ) we set σ such that distinguishing N (0, σ 2 ) from N (Bernoulli(q), σ 2 ) satisfies (1, 10 -6 )-DP Figure 5 : Ratio of upper bound on ε for quadratic loss with α = 0.5 divided by maximum ε of i iterations on a linear loss. In Figure 5a (resp. Figure 5b ), for each choice of q, σ is set so 1 iteration of DP-SGD satisfies (1, 10 -6 )-DP (resp (2, 10 -6 )-DP).(resp. (2, 10 -6 )-DP). In the majority of settings, the linear loss heuristic provides a larger ε than the quadratic with α = 1/2, and even when the quadratic provides a larger ε, the violation is small (≤ 3%). This is evidence that our heuristic is still a good approximation for many convex losses.If we allow the regularizer r to be arbitrary -in particular, not even requiring continuity -then the gradient can also be arbitrary. This flexibility allows us to construct a counterexample such that the standard composition-based analysis of DP-SGD with intermediate_iterates is close to tight.Specifically, choose the regularizer so that the update m = m -η∇ m r(m) does the following:m 1 = 0 and, for i ∈ [d -1], m i+1 = v • m i .Here v > 1 is a large constant. We chose the loss so that, for our canary x 1 , we have ∇ m (m, x 1 ) = (1, 0, 0, • • • , 0) and, for all other examples x i(i ∈ {2, 3, • • • , n}), we have ∇ m (m, x i ) = 0.Then the last iterate isEQUATIONwhere A t ← Bernoulli(p) indicates whether or not the canary was sampled in the t-th iteration and ξ t,i denotes the i-th coordinate of the noise ξ t added in the t-th step. Essentially, the last iterate m T contains the history of all the iterates in its coordinates. Namely, the i-th coordinate of m T gives a scaled noisy approximation to A T -i :EQUATION)As v → ∞, the variance converges to σ 2 . In other words, if v is large, from the final iterate, we can obtain N (A i , σ 2 ) for all i. This makes the standard composition-based analysis of DP-SGD tight.The examples above rely on the regularizer having large unclipped gradients. We now construct a counterexample without a regularizer, instead using other examples to amplify the canary signal.Our heuristic assumes the adversary does not have access to the intermediate iterations and that the model is linear. However, we can design a nonlinear model and specific training data to directly challenge this assumption. The attack strategy is to use the model's parameters as a sort of noisy storage, saving all iterations within them. Then with access only to the final model, an adversary  
discussion & conclusion: 
 Both theoretical analysis and privacy auditing are valuable for understanding privacy leakage in machine learning, but each has limitations. Theoretical analysis is inherently conservative, while auditing procedures evaluate only specific attacks, and may thus underrepresent the privacy leakage.Our work introduces a novel heuristic analysis for DP-SGD that focuses on the privacy implications of releasing only the final model iterate. This approach is based in the empirical observation that linear loss functions accurately model the effectiveness of state of the art membership inference attacks. Our heuristic offers a practical and computationally efficient way to estimate privacy leakage to complement privacy auditing and the standard composition-based analysis of DP-SGD. As shown in Table 1 , we trained a series of CIFAR10 models with varying batch sizes that all achieved the similar level of heuristic epsilon, albeit with different standard epsilon values. Remarkably, these models exhibited similar performance and similar empirical epsilon values.We also acknowledge the limitations of our heuristic by identifying specific counterexamples where the heuristic underestimates the true privacy leakage. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The setup is described for each experiment we conduct and we reference prior work that these build on. We use the standard CIFAR10 dataset for deep learning experiments. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: The auditing results present a lower bound which can be viewed as a one-sided confidence interval. For the other results the numbers are computed non-statistically (i.e. by numerically evaluating a formula); the only potential error here is due to numerical precision. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We used A2-megagpu-16g machines from Google cloud which have 16 Nvidia A100 40GB GPUs to run the experiments in this paper. Overall we used around 33,000 hours of GPU to run all of the experiments in the paper. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: This work is primarily theoretical. While it is possible that downstream uses of our work could be societally impactful, the precise consequences are difficult to foresee.The considerations are similar to any other paper on private machine learning. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper uses standard datasets (CIFAR10) and standard models (WideRes-Net).Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.• Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We use CIFAR10 [Ale09] and a WideResNet [ZK16] .Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.• For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Proof. Let x i * be the canary, let D be the dataset with the canary and D be the dataset without the canary. Since and r are linear, wlog we can assume r = 0 and ∇ mt-1 (m t-1 , x i ) = v i for some set of vectors {v i }, such that v i 2 ≤ 1. We can also assume wlogv i * = 1 since, if v i * < 1,the final privacy guarantee we show only improves.We have the following recursion for m t :m t = m t-1 -η i∈Bt v i + ξ t , ξ t i.i.d ∼ N (0, σ 2 I d ).Unrolling the recursion:m t = m 0 -η   t∈[T ] i∈Bt v i + ξ   , ξ ∼ N (0, T σ 2 I d ).By the post-processing property of DP, we can assume that in addition to the final model m T , we release m 0 and {B t \ {x i * }} t∈[T ] , that is we release all examples that were sampled in each batch except for the canary. The following f is a bijection, computable by an adversary using the released information: Finally, the distribution of f (m T ), v i * is exactly P for D and exactly Q for D . By post-processing, this gives the theorem.f (m T ) := -   m T -m 0 η - t∈[T ] i∈Bt\{x i * } v i .We can also see that the function δ T,q,σ is tight (i.e., even if we do not release B t \ {x i * }), by considering the 1-dimensional setting, where v i = 0 for i = i * and v i * = -1, η = 1, m 0 = 0. Then, the distribution of m T given D is exactly P , and given D is exactly Q.Here, we give an efficiently computable expression for the function δ T,q,σ (ε). Using P, Q as in Theorem 1, let f (y) be the privacy loss for the output y:f (y) = log P (y) Q(y) = log T k=0 T k q k (1 -q) n-k exp(-(y -k) 2 /2T σ 2 ) exp(-y 2 /2T σ 2 ) = log T k=0 T k q k (1 -q) k exp 2ky -k 2 2T σ 2 .Then for any ε, using the fact that S = {y : f (y) ≥ ε} maximizes P (S) -e ε Q(S), we have:H e ε (P, Q) = P ({y : f (y) ≥ ε}) -e ε Q({y : f (y) ≥ ε}) = P ({y : y ≥ f -1 (ε)}) -e ε Q({y : y ≥ f -1 (ε)}) = T k=0 T k q k (1 -q) k Pr[N (k, T σ 2 ) ≥ f -1 (ε)] -e ε Pr[N (0, T σ 2 ) ≥ f -1 (ε)].Similarly, S = {y : f (y) ≤ -ε} maximizes Q(S) -e ε P (S) so we have:H e ε (Q, P ) = Q({y : f (y) ≤ -ε}) -e ε P ({y : f (y) ≤ -ε}) = Q({y : y ≤ f -1 (-ε)}) -e ε P ({y : y ≤ f -1 (-ε)}) = Pr[N (0, T σ 2 ) ≤ f -1 (-ε)] -e ε T k=0 T k q k (1 -q) k Pr[N (k, T σ 2 ) ≤ f -1 (-ε)].These expressions can be evaluated efficiently. Since f is monotone, it can be inverted via binary search. We can also use binary search to evaluate ε as a function of δ.It turns out that in the full-batch setting, the worst-case analyses of DP-GD with intermediate_iterates and with last_iterate_only are the same. This phenomenon arises because there is no subsampling (because q = 1 in Algorithm 1) and thus the algorithm is "just" the Gaussian mechanism. Intuitively, DP-GD with intermediate_iterates corresponds to T calls to the Gaussian mechanism with noise multiplier σ, while DP-GD with last_iterate_only corresponds to one call to the Gaussian mechanism with noise multiplier σ/ √ T ; these are equivalent by the properties of the Gaussian distribution.We can formalize this using the language of Gaussian DP [DRS19] : DP-GD (Algorithm 1 with q = 1) satisfies √ T /σ-GDP. (Each iteration satisfies 1/σ-GDP and adaptive composition implies the overall guarantee.) This means that the privacy loss is exactly dominated by that of the Gaussian mechanism with noise multiplier σ/ √ T . Linear losses give an example such that DP-GD with last_iterate_only has exactly this privacy loss, since the final iterate reveals the sum of all the noisy gradient estimates. The worst-case privacy of DP-GD with intermediate_iterates is no worse than that of DP-GD with last_iterate_only. The reverse is also true (by postprocessing).In more detail: For T iterations of (full-batch) DP-GD on a linear losses, if the losses are (wlog)1-Lipschitz and we add noise N (0, σ 2 n 2 • I) to the gradient in every round, distinguishing the last iterate of DP-SGD on adjacent databases is equivalent to distinguishing N (0, T σ 2 ) and N (T, T σ 2 ).This can be seen as a special case of Theorem 1 for p = 1, so we do not a give a detailed argument here.If instead we are given every iteration m t , for any 1-Lipschitz loss, distinguishing the joint distributions of m t given m t-1 on adjacent databases is equivalent to distinguishing N (0, σ 2 ) and N (1, σ 2 ).In turn, distinguishing the distribution of all iterates on adjacent databases is equivalent to distinguishing N (0 T , σ 2 I T ) and N (1 T , σ 2 I T ), where 0 T and 1 T are the all-zeros and all-ones vectors in R T . Because the Gaussian distribution is isotropic, distinguishing N (0 T , σ 2 I T ) and N (1 T , σ 2 I T ) is equivalent to distinguishing x, 1 T where x ∼ N (0 T , σ 2 I T ) and x, 1 T where x ∼ N (1 T , σ 2 I T ).These distributions are N (0, T σ 2 ) and N (T, T σ 2 ), the exact pair of distributions we reduced to for last-iterate analysis of linear losses. All other data points, the "repeaters", are present in both datasets (D and D ), and have three tasks:• Cancel out any noise added to the model parameters at an index larger than the current iteration. At iteration i, their gradients for parameters from index i onward will be the same as the current value of the model parameter, scaled by the batch size and the learning rate to ensure this parameter value will be 0 after the update.• Evaluate whether the canary point was present in the previous iteration by comparing the model parameter at index i -1 with a threshold, and rewrite the value of that model parameter to a large value if the canary was present.• Ensure that all previous decisions are not overwritten by noise by continuing to rewrite them with a large value based on their previous value.To achieve all of these goals simultaneously, we require that the batch size is large enough that the repeaters' updates are not clipped.Finally Algorithm 4 runs DP-SGD, with repeater points computing gradients with Algorithm 3 and the canary point, sampled with probability p, computing its gradient using Algorithm 2. In our experiments we run Algorithm 4 100,000 times. And to evaluate if the model parameters was from dataset D or D we run a hypothesis test on the values of the model parameters. All constants are chosen to ensure all objectives of the repeaters are satisfied.Algorithm 2 Canary data point1: function ADV(x, i) 2:Initialize a as a zero vector of the same dimension as x 3:Set a i ← 1 Set the i-th component to 1 4:return -a 5: end function Algorithm 3 Additional data points Require: model parameters x, iteration number i, batch size N , learning rate η, previous history threshold t past , last iteration threshold t last , history amplification value BIG_VAL 1: function REPEATERS(x, i, N , η, t past , t last , BIG_VAL) 2: h ← x 0:iParameter "history" up to iteration i, not inclusive 3:f ← x i:end Future and current parameters, starting from iteration i 4:f ← -f /(η • N )Remove noise from last iteration 5:base_history ← -x 0:i /(η • N ) By default, zero out entire history 6:if length(h) > 1 then 7:h 0:i-1 ← BIG_VAL/(η • N ) • (21[h 0:i-1 ≥ t past ] -1)If an old iteration is large enough, it was a canary iteration, so amplify it 8: if p ≤ q and add-diff then Guidelines:end if 9: if length(h) > 0 then 10: h i-1 ← BIG_VAL/(η • N ) • (21[h i ≥ t last ] -1)• The answer NA means that the abstract and introduction do not include the claims made in the paper.• The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.• The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.• It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.• The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.• The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.• The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.• If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).• The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) for more details.• The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.• The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.• At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).• Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.• The full details can be provided either with the code, in appendix, or as supplemental material.• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean.• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.• For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).• If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.• The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.• The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.• The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 


Decision: The paper presents a heuristic approach for evaluating the privacy of DP-SGD when only the last model iteration is released. While the reviewers saw merit to the paper, no reviewer stood up to be a proponent of the paper. It is therefore out recommendation that the authors continue working on the heuristic and see if they could provide any rigorous bounds to their approach which should merit publication in a different venue.

Reviews: review: paper_summary: paper_summary: The authors provide exact DP guarantees for cases where only the last iterate of DP-SGD is shared with the malicious clients, and linear models with linear loss functions are used. They propose their DP bound to be used as a heuristic that approximates the true DP guarantees for cases where more complex models are used. They show that for normal DP-SGD training, the predictions of their heuristic fall between the standard DP bound computed under the assumption that all intermediate iterations of DP-SGD are shared with the attacker, which is a strict upper bound of the true DP guarantee when only the last iterate is shared and DP-SGD with full batches and only last iterate sharing. They also compare their method against SoTA DP attacks and show that under most circumstances, their heuristic value for the DP is higher. They suggest that this is the result of the attacks not being good enough at precisely estimating the true DP guarantees. Finally, the authors demonstrate that their heuristic under unrealistic circumstances can underestimate the true DP guarantee but argue this only happens under hand-crafted losses and gradient updates, which do not happen in practical circumstances.
strength_weakness: strength_weakness: - I am confused by L234. The authors propose to maximize their heuristic over all $t\leq T$, while beforehand (e.g. in Figure 1/Section 2) they advocated to computing the heuristic for a single $T$. Which one is the exact proposed heuristic by the paper?
- In Figure 2, I am not sure how we adapt existing techniques to the last-iterate-only setting? Can the authors explain in more details?
- Can the authors explain in Figure 1, what network and dataset were used?
- The authors do not provide code. I am not sure about the reason, but I will give them the benefit of the doubt that the reason is indeed related to anonymity 

**Nits:**  
- Eq. 8. I assume you do indexing from i = 1. In that case, $A_{T-i}$ should be $A_{T-i+1}$ instead. If you do 0-based indexing, even more fixes to the equation are needed.
- I believe Eq. 7 should be multiplied by $\eta$ on the right-hand side
- Equation at L442, left-hand side should be $m_T$ not $m_t$
- I believe the last equation at L459 should have $(1-q)^{n-k}$ instead of $(1-q)^{k}$. I also believe $n$ is $T$ in this equation
- The definition of $l(m)$ in L109 is confusing as $m$ is considered input to the function, while in the rest of the paper $m$ is used as a parameter. Consider putting $x$ instead.
- Consider defining the hockey-stick divergence in terms of both its pdf and cdf in the appendix to ease unfamiliar readers. I had to read quite a bit on my own to understand it. 
- Consider adding some information in the appendix as to how to deal with the mixed discrete-continuous probability for $P$. I assume many readers will be unfamiliar. 
- Consider deriving the formulas for $P$ and $Q$ in Section 4.2 in the appendix. They are not obvious. 
- Consider having an appendix section that quickly recaps how [NSTPC21] and [NHSBTJCT23] work. Their operation is critical for understanding Section 3. I ended up reading them to get an idea of what was going on there.
questions: questions: (See Weaknesses Above)


While I am familiar with DP and DP guarantees, I am not a DP expert. Still, I was able to follow the math in the paper, and I am mostly confident in it. What I am not as confident in is if the heuristic, which by authors' own admission does not provide rigorous upper or lower bounds, will be useful in practice. In addition, there is few experimental results that require explanation (see above). In particular, I am concerned about why, in the counter-examples in Section 4, the authors propose maximizing the heuristic across $T$, while in the experiments in Figure 1, the heuristic is proposed to be used for a particular $T$. I am, thus, not sure which of the two versions of the heuristic should be used in practical settings as the true heuristic. Further, I am not sure if the structure of the proposed DP counterexamples in Section 4 is novel, but if it is, I think it might have uses outside of this paper.
limitations: limitations: The authors acknowledge the limitations of using the heuristic to compute the DP bounds
paper_summary: paper_summary: The paper proposes a heuristic privacy analysis for DP-SGD that focuses on releasing only the last iterate, as opposed to all intermediate iterates. The authors argue that this approach is more realistic and provides sharper privacy guarantees in practical scenarios. The heuristic is based on a linear structure assumption for the model and is validated experimentally through attacks/privacy auditing.
strength_weakness: strength_weakness: To my understanding, this paper offers a tighter privacy accounting analysis specifically for linear loss functions. However, I find its applicability limited since it cannot be extended to general ML tasks where the loss functions are not linear. Additionally, the fact that the privacy adversary has access to all intermediate iterates of the training process makes DP-SGD overly conservative is quite well-known. The main challenge remains in developing tight privacy accounting analyses for iterative algorithms like SGD.
questions: questions: Why does the example provided in Section 4.2 show linear loss is a good approximation of many convex losses? Could you please provide some more insights?
limitations: limitations: The limitations are adequately addressed.
paper_summary: paper_summary: This paper proposes a heuristic privacy analysis of releasing only the final model iterate of differentailly private gradient descent (DP-SGD). The analysis is based off of the worst-case differential privacy guarantee of DP-SGD with linear losses, under the assumption that the heuristic can be applied to more general loss functions in order to approximate the privacy loss.
strength_weakness: strength_weakness: * I don’t know how useful the heuristic analysis would be in practice — beyond a lightweight sanity check — since ultimately it is just a heuristic and not a rigorous upper or lower bound on the privacy loss.

* The empirical study of the heuristic looks to be very thorough, but sparse on interpretation. I would have appreciated more discussion on the figures, and didn’t really feel like there was a strong take-home message from the paper.

* Algorithm 1 is DP-SGD with a regularizer, but in practice it is somewhat rare to use explicit regularization with DP-SGD. So I’m not sure that the heuristic would be widely applicable to the more common implementation of DP-SGD without regularization.
questions: questions: 1. One of the potential use cases of the heuristic (lines 82-85) is to predict the outcome of privacy auditing. So I’m wondering:
   * If one of the advantages of the heuristic is that it’s less computationally expensive than privacy auditing, but you’ll have to do the computationally expensive privacy auditing anyway (in order to compare), then what is the point?
   * One of the disadvantages of privacy auditing is that it’s difficult to perform correctly, but the heuristic doesn’t have rigorous theoretical guarantees. If privacy auditing and the heuristic don’t agree, then how would you know which one was wrong?

2. In Figure 3, why does the heuristic $\epsilon$ scale with the number of iterations $T$? Since the heuristic is a last-iterate analysis, I would have imagined that it would converge to a constant?

3. Would it be possible to extend Theorem 1 to non-regularized DP-SGD?

4. It’s not obvious to me why the privacy guarantee for an arbitrary loss would be similar to the privacy guarantee for a linear loss (and not even a GLM loss, mind you). Maybe I missed this in the paper, but would it be possible to further justify why the heuristic would be a good approximation in cases where the linear loss assumption doesn’t hold?

5. I feel like the proof of Theorem 1 is hard to appreciate without knowing more technical preliminaries, such as how the hockey-stick divergence can be used to show that an algorithm satisfies DP. I wonder if the proof could be re-framed in the language of privacy profiles and dominating pairs? (https://arxiv.org/abs/1807.01647 and https://arxiv.org/abs/2106.08567)
limitations: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_summary: The paper presents a heuristic approach for evaluating the privacy of DP-SGD when only the last model iteration is released. This method contrasts with traditional analyses that consider all intermediate updates, offering a more practical assessment for scenarios where adversaries only access the final model. The proposed heuristic is experimentally shown to provide reliable privacy leakage estimates, making it a valuable tool for pre-audit privacy assessments.
strength_weakness: strength_weakness: I think the proposed method is interesting and new but I still have some questions.

1. I know the linear loss function assumption is common in theoretical analysis but it seems that the proposed method wants to have contributions in the empirical case, so why still make the linear assumption? 

2. While I appreciate the effort to introduce a Heuristic analysis, I remain skeptical about its necessity and effectiveness. The primary benefit of theoretical analysis is its precision and rigor, which often include the flexibility to adjust bounds as needed. If the goal is to find a more relaxed lower bound on privacy risks, this can often be achieved by simply loosening the constraints within the existing theoretical framework. Introducing a separate heuristic analysis seems to complicate matters without providing clear advantages. 

3. I do not think you are using a correct baseline. When you make that only the last iteration model can be seen assumption, it is not fair to use normal DP-SGD analysis. I think it is better to use the theoretical analysis from those hidden state papers you cited. I am curious if you compare your proposed method with those methods, will you still get the same conclusion? 

4. I find Table 1 in the paper somewhat unclear and would appreciate further explanation from the authors regarding its purpose and implications. The table suggests that similar levels of heuristic ε are achieved across varying batch sizes, yet there is a noticeable increase in the standard privacy budget for smaller batches to maintain comparable performance. This observation seems to underscore the well-known impact of batch size rather than demonstrating an advantage of the proposed heuristic method.
Could the authors elaborate on how this data relates to the efficacy of the heuristic analysis?
questions: questions: Please check the weaknesses.
limitations: limitations: Please check the weaknesses.

Comments: comment: Thank you for your response. My score remains unchanged.
Thank you for the comment. We respond below. We hope that we have been able to clarify all the issues before the discussion ends.

> Using the heuristic for hyperparameter selection is an interesting idea. But I’m a little unclear on the exact set-up, and why the hyperparameters would be chosen according to privacy auditing (instead of according to utility).

Hyperparameters would need to be chosen to achieve both high utility and low privacy loss.
The "ideal" is to calibrate the hyperparameters so that the standard analysis of DP-SGD gives a good privacy parameter $\varepsilon$. 

For better or worse, it is becoming accepted practice to set the standard $\varepsilon$ to large-ish values (e.g. $10$ or $20$). One way to justify this practice is to perform privacy auditing on the final model to argue that this large $\varepsilon$ is overly conservative. This is one of the practical motivations for work on privacy auditing.

The use case for hyperparameter tuning that we envisage is that one has dual privacy constraints, say, $\varepsilon_{\text{standard}} \le 10$ but also $\varepsilon_{\text{auditing}} \le 1$. Our heuristic would help evaluate the latter constraint during the hyperparameter selection phase.
This use case is analogous to scaling laws on the utility side. 

That said, we reiterate that we think this work is more about basic science than about immediate applications. Progress on both sides -- provable DP upper bounds for ML and empirical privacy auditing lower bounds -- has been slowing down without converging. The goal of our work is to offer a fresh (if somewhat unorthodox) perspective -- our heuristic is neither a provable upper bound nor a lower bound; it should be somewhere in between.

> if I’ve understood correctly, Theorem 1 implies that the heuristic will always be smaller than the existing 
-DP bound. 

Yes. This is true by the postprocessing property of DP. (The standard analysis assumes all intermediate iterates are revealed. Our result is tight for when only the sum is revealed, which is a postprocessing.)

>  But there doesn’t seem to be a strong connection between privacy auditing and the heuristic apart from the empirical observation that the heuristic is larger than the privacy auditing bound

This is supported by the experimental evidence, plus the observation repeated in the literature that the best privacy auditing results (i.e. worst case for privacy) are when the canary examples have the same gradient in each iteration, which corresponds to linear losses. (I.e., prior work shows that "gradient space attacks" are better than "input space attacks.") The best theoretical justification is the fact that we know that linear losses achieve the worst case in the special case of full batch training (as discussed in Appendix B).

>  I hate to say that 33,000 GPU hours aren’t enough to convince me on this, but I do feel that I would need to see the empirical observation validated across a wider range of problems and datasets (i.e., not just CIFAR10)

That is a fair point. But this limitation is also true of the privacy auditing literature more generally. The vast majority of experimentation is on CIFAR10 and smaller datasets. This is simply because privacy auditing generally requires many training runs, which is prohibitive for anything larger.

It's important to note that the claim that our heuristic upper bounds privacy auditing results for "realistic" models & datasets is falsifiable (at least to the extent that "realistic" is clearly-defined). Our hope is that any future privacy auditing work would compare to our heuristic. If they fail to exceed our heuristic, then the claim gains more weight. If they do exceed our heuristic, then that would represent significant progress on privacy auditing.
Thanks for addressing my points. In hindsight my concerns about the regularizer don’t hold any water, but I do still have some remaining concerns.

Using the heuristic for hyperparameter selection is an interesting idea. But I’m a little unclear on the exact set-up, and why the hyperparameters would be chosen according to privacy auditing (instead of according to utility). I imagine a scenario where for a fixed level of privacy, you try to maximize the utility by selecting the best hyperparameters subject to the privacy constraint, then do privacy auditing on the final hyperparameters. In this case I don’t see why it would be necessary to do privacy auditing on any of the hyperparameter candidates apart from the final ones.

My other question is — if I’ve understood correctly, Theorem 1 implies that the heuristic will always be smaller than the existing $(\epsilon, \delta)$-DP bound. (Informal logic: Theorem 1 is a tight upper bound for linear losses, and extending to a larger class of loss functions can only make the privacy loss larger.) But there doesn’t seem to be a strong connection between privacy auditing and the heuristic apart from the empirical observation that the heuristic is larger than the privacy auditing bound (except for specially constructed pathological cases). I hate to say that 33,000 GPU hours aren’t enough to convince me on this, but I do feel that I would need to see the empirical observation validated across a wider range of problems and datasets (i.e., not just CIFAR10) and ideally at least some theoretical justification before I’d be comfortable agreeing that the heuristic is a valid and reliablbe tool.

I realize that it’s not ideal to bring this up so soon before the end of the reviewer-author discussion period…but if time permits it would be great to receive clarification on these issues.
Thanks authors for the detailed explanations. I have read the rebuttal and comments but not be fully convinced by them. I will keep the same score.
I have updated my grade in accordance with the author's comments
Thank you for the comment.

> I would urge the authors to include the additional info in their next paper iteration.

We will clarify the points that the reviewers have pointed out as insufficiently clear.

> Regarding Figure 1, given the authors' comment about Appendix A1, am I correct the experiment is applied on "linear networks"

Figure 1 can be viewed as comparing the privacy of linear losses ("Heuristic"), general losses ("Standard"), and full batch training ("Full Batch" which is the same for linear losses and general losses) under the correspondence given by Equation 4. We don't refer to it as an experiment as it uses exact analytic formulae.

We hope we have addressed all of the reviewer's questions and concerns about our paper.
Thank you for your comments. I would urge the authors to include the additional info in their next paper iteration.


Regarding Figure 1, given the authors' comment about Appendix A1, am I correct the experiment is applied on "linear networks"?
Thank you for your comment. Some responses:

> Thus, despite the heuristic producing too low $\epsilon$s for many $t$, the authors report that for the “best” $t$ they are close to the counterexamples they find.

That is a fair point. We presented the results in Section 4.2 to show that we are capturing something more than Section 4.1, but we should also compare to the original baseline. This is what Figure 5b looks like if we just use a single $T$: [https://i.sstatic.net/IYnSlZwW.png](https://ibb.co/DpC6crS)
The non-monotonicity issue identified in Section 4.1 has a larger effect than the phenomenon captured in Section 4.2. (This is already evident from Figure 1c.) 

> My question is regarding the Empirical attack in Figure 2. The authors say they adapt the empirical attack to the last-iterate DP setting. My question was if the authors could provide details on how this is done?

The prior literature on privacy auditing considers different types of attacks some of which apply to our last iterate setting and some of which don't. We don't significantly adapt the attacks, we just consider those that are applicable to the last iterate setting.

The basic idea for all the membership inference attacks is to run the training procedure both with and without a given example and then to apply a distinguishing test to the final model. 
For input space attacks (Figure 4), we use the loss of the malicious input as a distinguisher. For gradient space attacks (Figures 2 and 3) the distinguishing test measures the dot product of the final model checkpoint and the gradient canary.
The true positive rate / false positive rate tradeoff curve for this distinguishing test is then used to calculate the $\varepsilon$ values.

The difference between Figures 2 and 3 is that in Figure 3 the gradients of the other examples are zeroed out, while in Figure 2 the other examples' gradients are nonzero and effectively act as additional noise that aids privacy. The reason we included Figure 2 is that in this setting, if the adversary has access to intermediate iterates, then prior auditing work has shown that the standard DP-SGD analysis is tight. But it is obviously very far from tight in the last iterate setting and our heuristic only partially explains the gap.

> Can the authors describe how the plot [Figure 1] and the heuristics themselves are compiled in more detail?

The line labelled "Heuristic" is calculated using the method described in Appendix A.1.
The line marked "Standard" is calculated using an open source DP accounting library [[Goo20](https://github.com/google/differential-privacy/tree/main/python/dp_accounting)].
The "Full Batch" line can be calculated using the same open source library or as a special case of our heuristic (we opted for the latter, since the open source library can be slow).

> That said, they also suggest that they are the same only for very artificial examples that only happen for extremely unrealistic models. Do the authors have any suggestions on how the DP definitions in the last-iteration case can be amended to make their worst case closer to DP-SGD executed on real networks? Maybe something related to progressing the loss during training?

This is the big question and it's something that we are continuing to work on. 

The only prior work in this direction [[FMTT18](https://arxiv.org/abs/1808.06651); [CYS21](https://arxiv.org/abs/2102.05855); [YS22](https://arxiv.org/abs/2203.05363); [AT22](https://arxiv.org/abs/2205.13710); [BSA24](https://arxiv.org/abs/2403.00278)] assumes contractivity -- i.e., if you perturb the model weights at some point, then, in subsequent steps, the effect of this perturbation does not grow or even shrinks. We can prove contractivity for smooth and (strongly) convex loss functions. But, for deep learning, we have seen experimentally that this contractivity assumption is simply not true.

We speculate that it would be fruitful to understand to what extent real deep learning losses are "locally approximately linear" (however you want to precisely define that) and then to exploit that property in the privacy analysis. The value of our submission is that it tell us what is the best we can hope for from such an approach.
**Re:** I am confused by L234.  
**Ans:** My confusion stems from the fact that by maximizing $\epsilon$, the authors take the most sound and least tight (I am using these terms here loosely, referring to their meanings for the empirical and provable DP guarantees cases, respectively) prediction they make across all $t$. Thus, despite the heuristic producing too low $\epsilon$s for many $t$, the authors report that for the “best” $t$ they are close to the counterexamples they find.
 
**Re:** In Figure 2, I am not sure how we adapt existing techniques to the last-iterate-only setting? Can the authors explain in more details?  
**Ans:** My question is regarding the Empirical attack in Figure 2. The authors say they adapt the empirical attack to the last-iterate DP setting. My question was if the authors could provide details on how this is done?


**Re:** Can the authors explain in Figure 1, what network and dataset were used?  
**Ans:** Can the authors describe how the plot and the heuristics themselves are compiled in more detail? 

**Re:** I am not sure if the structure of the proposed DP counterexamples in Section 4 is novel.  
**Ans:** I would also like to ask other reviewers who are more familiar with SOTA DP research to confirm this. Also, I would request that if they also find it novel, to take this into account in their reviews.

**Re:** What I am not as confident in is if the heuristic, which by authors' own admission does not provide rigorous upper or lower bounds, will be useful in practice.  
**Ans:** I find the first part of the author’s answer here very useful. I would suggest that they include it more prominently in the paper. Regarding the second part of the answer --- I think the proposed counterexamples in Section 4 strongly suggest that general last-iterate DP guarantees are likely the same as full DP. That said, they also suggest that they are the same only for very artificial examples that only happen for extremely unrealistic models. Do the authors have any suggestions on how the DP definitions in the last-iteration case can be amended to make their worst case closer to DP-SGD executed on real networks? Maybe something related to progressing the loss during training?
Thank you for the clarification.

>  Is it feasible to apply your proposed method to a non-linear loss like a cross-entropy loss that the community usually uses?

Realistic deep learning losses yield complicated output distributions on the model weights and, unfortunately, it is not possible to give an exact differential privacy analysis.
This is why there is a lot of work on privacy auditing, which aims to empirically approximate an exact DP analysis. Thus we compare our heuristic to state-of-the-art privacy auditing methods.

In Section 4.2 we performed an exact analysis of quadratic losses. This is slightly more general than linear losses. But even here the output distribution becomes a mixture of Gaussians which is nontrivial to analyze.

> I also wonder why you think a technique theoretically justified in the linear case can be representative of real deep learning. 

It is indeed surprising that linear losses yield a good approximation to real deep learning in terms of privacy.
The key observation that inspired this paper is that, in the practice of privacy auditing, the strongest membership inference results are achieved by examples ("canaries") with gradients that are the same in each iteration of SGD. This corresponds exactly to the case of a linear loss function.

So our linear approximation is well-justified empirically. Theoretically, Appendix B shows that *in the full batch setting* our linear approximation is indeed the worst case, although this proof does not extend to the minibatch setting.

> For example, I want to train a Vision transformer model on ImageNet with DP-SGD. Do you think it is possible to only use a linear loss? Or in other words, will your proposed method can be applied in this real deep learning case?

Obviously, training with a linear loss would result in non-convergence of DP-SGD, so we don't recommend doing that. :-) 
 Our thesis is that, in the last iterate setting, for the privacy analysis, we can *pretend* that we have a linear loss to give a heuristic privacy analysis. This heuristic privacy analysis is optimistic, but it may be closer to the "true" privacy loss than the standard pessimistic DP-SGD analysis. We argue that this is a useful/interesting perspective to add to practical private deep learning, although it still leaves open many questions.
Thank you for your response. Let me clarify what I mean for the first question.
Is it feasible to apply your proposed method to a non-linear loss like a cross-entropy loss that the community usually uses? I also wonder why you think a technique theoretically justified in the linear case can be representative of real deep learning. For example, I want to train a Vision transformer model on ImageNet with DP-SGD. Do you think it is possible to only use a linear loss? Or in other words, will your proposed method can be applied in this real deep learning case?