Performative Privacy: When Differential Privacy Maximizes Utility

Preprint.

P ERFORMATIVE P RIVACY: W HEN D IFFERENTIAL P RI VACY M AXIMIZES U TILITY Edwige Cyffers CNRS Dauphine PSL, edwige.cyffers@cnrs.fr

Uddalak Mukherjee Dauphine PSL, uddalakmukherjee49@gmail.com

arXiv:2608.28198v1 [cs.LG] 28 Aug 2026

Yann Chevaleyre Dauphine PSL, yann.chevaleyre@lamsade.dauphine.fr

A BSTRACT Privacy-preserving learning is often motivated by the idea that protecting users’ data can preserve trust and thus participation, improving utility in the long term. However, this claim has not been formalized so far. In parallel, performative learning provides a framework for studying learning systems whose deployment affects the data they later observe. In this work, we bring these two perspectives together and introduce performative privacy, where data leakage reduces future participation. We study a simple model where agents repeatedly contribute data for mean estimation but may leave the system when their data is leaked. Privacy is implemented through differentially private mechanisms, creating a trade-off between estimation noise and future participation. We show, through a theoretical study of the dynamics and numerical experiments, that a finite privacy budget can outperform non-private estimation in the long term when the feedback loop between leakage and participation is sufficiently strong. This provides first evidence that differential privacy can be optimal not only as a protection mechanism, but also from the perspective of long-term utility.

1

I NTRODUCTION

Protecting privacy in machine learning is motivated by moral, ethical, and practical reasons (Solove, 2008). Access to sensitive data, such as health records, is sometimes illegal without adequate protections (European Parliament & Council of the European Union). However, in many scenarios, privacy protection is motivated by users’ willingness to participate in training, based on the risks it entails for their business or their own privacy if their data is leaked (Nissenbaum, 2004; IBM & Ponemon Institute, 2025). Users who generate training data can be seen as agents who decide whether to participate depending on the risk that their data is leaked. A natural feedback loop to consider is thus that, if a user has their data leaked, they may no longer be willing to participate in the future, harming future rounds of training. This is often claimed informally: privacy-preserving machine learning should optimize long-term utility by maintaining users’ trust, and thus their data (Dwork & Roth, 2013). Surprisingly, this claim that private learning can provide optimal long-term utility has, to the best of our knowledge, never been formalized. We propose first results in this direction. The gold standard for protecting data is differential privacy (DP)(Dwork et al., 2006). DP formalizes the following promise: a single data point should not influence the output of the algorithm too much, ensuring that any attacker with access to the output cannot gain significant information about the data point by observing the output. This protection, however, can only be achieved through randomization, often implemented by injecting noise into the algorithm. The level of privacy protection is then summarized by the privacy budget ε: the smaller the privacy budget, the stronger the privacy guarantee, and the larger the noise required, which decreases the accuracy of the model, creating a privacy-utility trade-off. The right value for ε is often debated in the community, based on ad hoc perceptions of data sensitivity and risk (Ponomareva et al., 2023; Cyffers, 2025; Lee & Clifton, 1

Preprint.

2011). Here, we take an orthogonal perspective, considering the optimal privacy budget to be the one that maximizes long-term utility. Taking into account how models change the data over time is the motivation of performative learning (Perdomo et al., 2020), where the data distribution is parametrized by the same parameter as the model, and the goal is to optimize the overall system rather than find the best model for a fixed distribution, as usually done in supervised learning. Performative learning is an increasingly popular framework, motivated by examples where users may game the system by modifying their features to obtain more favorable outcomes, by settings involving generative models where data can be contaminated over time, or by scenarios where sampling can reinforce existing biases, raising long-term fairness concerns (Hardt & Mendler-Dünner, 2023). Feedback loops due to privacy leakage have not been studied so far, but they constitute a natural dynamic to study, as it is well known that data leakage can cause trust issues and reduce participation, or even lead participants to adopt malicious behaviors (IBM & Ponemon Institute, 2025). Relatedly, the term performative privacy was coined by legal scholars (Skinner-Thompson, 2017) to describe the actions agents may take to exercise their right to privacy, by making unavailable information that could otherwise be available by default. In this work, we design and study a simple model that allows us to quantify regimes in which a finite privacy budget maximizes utility in a repeated mean estimation problem. Rather than using the privacy budget directly as a proxy for the decision to participate, we use whether the data point has been leaked in the feedback loop. This makes our setting applicable to non-differentially private mechanisms as well and avoids focusing on a meta-interpretation of the privacy budget, instead focusing on actual algorithm outputs. More precisely, our contributions are the following: • We propose a new object of study, the long-term utility of repeated learning tasks involving privacy-sensitive data, which we call performative privacy. • We first study a simple setting with a set of agents who each hold a private binary value at each round and may withdraw from the learning process if their correct private value is used by the system, and in which additional agents may join at each step. • We extend this setting to the computation of a d-dimensional average over time, with a more realistic definition of data leakage based on membership inference attacks. • We show that a finite privacy budget can be optimal in both scenarios, proving that privacy can maximize utility in the presence of a feedback loop in terms of participation.

2

R ELATED WORK

While a direct link between data leakage and future participation has not yet been formalized, differential privacy originates from Warner (1965), where randomization aims to reduce bias in data collection, and thus improve data quality. Inspirations from sociology, notably through the contextual integrity framework, have also been numerous (Nissenbaum, 2004; Cyffers, 2025; Cummings & Durfee, 2020). Considering data producers as privacy-aware agents is a popular framework, sometimes formalized as a data market (Ghosh & Roth, 2011; Pai & Roth, 2013; Fallah et al., 2022), in particular for deciding participation in surveys (Roth & Schoenebeck, 2012; Ligett & Roth, 2012). The choice of the privacy budget itself has been analyzed through economic and mechanism-design lenses (Hsu et al., 2014; Nissim et al., 2012; Cummings et al., 2015; Ligett et al., 2017), possibly personalizing it across users (Jorgensen et al., 2015). However, privacy awareness is often translated into a supposedly known optimal privacy budget, computed from expected utility and privacy preferences (Cummings et al., 2022; Chaudhuri et al., 2025), rather than modeled as a dynamical system. Participation has also been studied as a strategic decision in collaborative and federated learning (Donahue & Kleinberg, 2021; Blum et al., 2021; Karimireddy et al., 2022), without the link to privacy leakage that we consider. On the empirical side, data breaches measurably affect customer behavior and firm value (IBM & Ponemon Institute, 2025), and the way privacy guarantees are communicated changes users’ willingness to share their data (Xiong et al., 2020; Cummings et al., 2021), supporting the feedback loop we model. Performativity in Trustworthy Machine Learning. Performative learning (Perdomo et al., 2020) is motivated by the social impact of machine learning deployments (Hardt & Mendler-Dünner, 2023; Hardt et al., 2022), with dedicated optimization algorithms (Mendler-Dünner et al., 2020) and regret 2

Preprint.

analyses (Jagadeesan et al., 2022; Zhu et al., 2025), and with links to robustness (Cyffers et al., 2024) and fairness (Somerstep et al., 2024). Closest to our setting are retention dynamics, where user groups shrink after repeatedly receiving poor utility (Hashimoto et al., 2018; Zhang et al., 2019); we study the privacy analogue, where users leave after a leakage event. As the population size depends on the whole history of deployments, our model is an instance of stateful performativity (Brown et al., 2022) rather than of the memoryless distribution map of Perdomo et al. (2020). Selfreinforcing feedback loops have also been documented in predictive policing (Ensign et al., 2018), dataset bias amplification (Taori & Hashimoto, 2023), and generative model collapse (Shumailov et al., 2024). Interestingly, participants can also contribute to steering the model toward desirable properties, as studied in collective action (Hardt et al., 2023). To the best of our knowledge, there is no theoretical work, nor simulated feedback-loop model, tackling privacy concerns from this perspective so far. Membership Inference Attacks. Membership inference attacks (MIAs) were introduced in the context of genomic studies by Homer et al. (2008), who demonstrated that aggregate statistics can reveal an individual’s participation in a dataset. MIAs have played an important role in motivating DP and establishing lower bounds for private data analysis (Bun et al., 2014; Nasr et al., 2021). In machine learning, numerous MIAs have been proposed under different threat models and access assumptions (Shokri et al., 2017; Sablayrolles et al., 2019; Even et al., 2026; Carlini et al., 2021; Yeom et al., 2017; Ye et al., 2022). These attacks are also widely used to empirically audit machine-learning systems and evaluate privacy defenses (Jagielski et al., 2020; Aerni et al., 2024; Jayaraman & Evans, 2019; Thudi et al., 2022). The membership inference game is naturally cast in the hypothesis-testing formulation of DP (Wasserman & Zhou, 2010; Kairouz et al., 2015), culminating in Gaussian DP (Dong et al., 2022), whose privacy-loss random variable is the leakage statistic we analyze in Section 4.4. Beyond measuring average privacy leakage, recent work has shown that privacy risk can vary substantially across individuals (Leemann et al., 2024; Azize & Basu, 2025), motivating per-instance guarantees and individual privacy accounting (Wang, 2019; Feldman & Zrnic, 2021; Yu et al., 2023; Koskela et al., 2023), and that worst-case privacy guarantees may be overly pessimistic in finite-sample regimes (Haghifam et al., 2025). Most closely related to our setting, recent work has studied membership inference under repeated interactions (Michel et al., 2026).

3

WARM - UP : ESTIMATION OF B ERNOULLI PARAMETERS

In this section, we derive the behaviors arising in the estimation of a Bernoulli parameter when the ground truth changes at each time step. The Bernoulli parameter is estimated from independent and identically distributed samples that are locally privatized using randomized response (RR). An answer is considered leaked whenever the true answer is preserved by RR. Learning task We consider a repeated mean estimation problem over T time steps. At each step t, the learner computes an estimate µ̂t of the true parameter µt of an underlying Bernoulli t distribution. The learner has access to possibly privatized responses (Yi,t )N i=1 of the users’ samples Nt Nt (Xi,t )i=1 ∈ {0, 1} , drawn i.i.d. from B(µt ). The learner aims to minimize the mean squared error of the parameter estimation at the final horizon:   E = E (µT − µ̂T )2 Alternatively, another objective, which we develop in the next section, is to minimize the error over the whole trajectory through a regret objective: RT =

T X

E(µt − µ̂t )2

t=1 t Randomized response We consider local differential privacy, where anyone can access (Yi,t )N i=1 , and privacy is ensured at the user level via randomized response (Dwork & Roth, 2013; Ioannidis et al., 2024; Wang et al., 2016). We assume that all users have the same privacy parameter ε and that

3

Preprint.

this budget remains constant over time. We parameterize by β ∈ [0, 12 ] the randomized response:  Xi,t , with prob. 12 + β Yi,t ≜ 1 − Xi,t , with prob. 12 − β With this definition, the learner’s best unbiased estimator is given by ν̂t − 21 + β µ̂t ≜ 2β

N

t 1 X Yi,t . with ν̂t ≜ Nt i=1

Lemma 1. For any given privacy budget ε > 0, setting the perturbation parameter to ε 1 β = tanh 2 2

(1)

(2)

guarantees that the randomized response mechanism satisfies ε-local differential privacy (ε-LDP). The proof of this lemma and the derivation of the estimator formula are deferred to Appendix C. Population evolution The population changes according to two phenomena: new users can join the training, and participating users can leave the training in reaction to data leakage. We define a leakage event as a response remaining unperturbed, i.e., Xi,t−1 = Yi,t−1 . In case of data leakage, a participant leaves the training with a fixed probability q, which we assume is independent of time and of the user. This model has the limitation of having no memory – if a user stays despite a leakage event at a given step, they do not become more likely to leave after the next leakage event – but this allows us to minimize the number of model parameters. For the inclusion of new participants, we assume that each participant whose data is not leaked at a given time can recruit an additional participant with probability r. Another possible update rule is to consider growth directly proportional to the total number of users, regardless of whether their data was leaked.1 Lemma 2. The evolution of the number of participants is given by:      1 1 E[Nt |Nt−1 ] = Nt−1 1 − q +β +r −β 2 2

(3)

We prove this formula in Appendix C. To analyze the long-term evolution of the user population, it is natural to summarize its expected one-step change via a single growth factor, C(β) ≜

E[Nt |Nt−1 ] r−q =1+ − β(q + r). Nt−1 2

(4)

This scalar represents the expected ratio of the population size between two consecutive rounds. The value of C(β) relative to 1 dictates the overall trajectory of the system: C(β) ≥ 1 denotes a stable or growing population, whereas C(β) < 1 indicates decline. By evaluating this one-step expected growth, we can determine the maximum value of β (i.e., the least private the mechanism can be) that the platform can support without seeing the population collapse. Theorem 1 (Critical Threshold for User Population Survival). To prevent demographic collapse (i.e., to have C(β) ≥ 1), β must be smaller than the critical threshold βc , defined as:   r−q (5) βc ≜ max 0, 2(q + r) We prove this theorem formally in Appendix C. From this formula, we can see two regimes: if q > r, the population will always collapse, regardless of the privacy protection. However, when r > q, the population can grow or shrink depending on the choice of β, and thus C(β) ≥ 1 gives a hard operational constraint on the choice of β. 1

We call this the agnostic model and study its behavior in Appendix B.

4

100

10 3

10 1

10 4 0

25

50

75

100 125 150 175 200

10 2

Time step t

(a) Moving-averaged variance (q = 0.6, r = 0.3)

Nt (Averaged across trials)

(log scale)

Variance (Moving Averaged)

100

10 2 10 3

10 1

10 4 0

25

50

75

100 125 150 175 200

10 1

0

25

50

75

100 125 150 175 200

10 2

Time step t

(b) Population evolution (q = 0.6, r = 0.3)

100 10 1

100

10 2

20000 17500 15000 12500 10000 7500 5000 2500 0

Time step t

(c) Moving-averaged variance (q = 0.3, r = 0.6)

100

(log scale)

10 2

400 350 300 250 200 150 100 50 0

(log scale)

Nt (Averaged across trials)

10 1

(log scale)

Variance (Moving Averaged)

Preprint.

10 1

0

25

50

75 100 125 150 175 200

10 2

Time step t

(d) Population evolution (q = 0.3, r = 0.6)

Figure 1: Comparison of moving-averaged variance and population evolution under two parameter settings: the top row corresponds to (q, r) = (0.6, 0.3), while the bottom row corresponds to (q, r) = (0.3, 0.6).

Empirical Simulation We sample binary responses from a Bernoulli distribution with mean µt and estimate it using the unbiased estimator equation 1. Responses are privatized by randomized response with perturbation probability 12 − β, where β is chosen according to equation 2 to satisfy ε-local differential privacy. Utility is measured by the squared estimation error at the final horizon. Throughout, we use a constant privacy budget ε, track the population size Nt (clipped to [1, 20000]) and the moving-averaged variance of µ̂t (window size 15), and average results over 30 independent trials. Figure 1 illustrates two representative regimes corresponding to (r, q) = (0.6, 0.3) and (0.3, 0.6). For both the variance and population plots, 10 values of ϵ were used, with their corresponding values indicated by the intensity bar to the left of each plot. As predicted, we observe population collapse for q > r, whereas for r > q, the population reaches a stable equilibrium or grows to the maximum size, and a finite privacy budget optimally balances privacy noise against user retention. Figure 2 reports the utility-maximizing privacy budget for each (r, q) pair. In the region where a finite optimum exists, the optimal ε decreases monotonically with the leaving rate, confirming that stronger privacy guarantees are required when users are more sensitive to data leakage. Optimal over (q, r)

1.0

0.5 0.8

0.6

0.5

log10 ( * )

Join Probability (r)

0.0

0.4

1.0

0.2

0.0 0.0

1.5

0.2

0.4

0.6

Leave Probability (q)

0.8

1.0

2.0

Figure 2: Global mapping of the optimal privacy budget ε∗ across the (r, q) parameter space. In the bottom-right region of the figure, the optimal privacy parameter evolves continuously.

5

Preprint.

4

M EAN ESTIMATION WITH MEMBERSHIP INFERENCE DETECTION

The previous section examined performative population dynamics under randomized response, where data is binary and leakage is defined as the exact release of the true bit. In that setting, utility and privacy risk are strictly opposed, as the leakage is defined as the single bit of information that is shared. This opposition becomes less pronounced for more complex data. We now generalize our framework to continuous vectors in Rd . This transition decouples a record’s informational utility from its membership detection; for example, in private mean estimation, a record located exactly at the population mean is statistically difficult to detect, but valuable for the estimation of the mean, while an outlier is easy to detect but does not improve utility. Finally, this high-dimensional continuous setting is closer to realistic machine learning deployments, allowing us to formalize user vulnerability through standard Membership Inference Attacks (MIAs) based on an individual’s geometric footprint. 4.1

T HE L EARNING TASK AND M ECHANISM

At any round t, the user population has size Nt . The platform seeks to estimate the true mean µ of the underlying data distribution D over Rd . The dataset at round t is denoted as Zt = {z1 , . . . , zNt }, where each individual’s record zi ∼ D is drawn independently. To ensure bounded each  sensitivity,  R record is clipped to a maximum ℓ2 −norm inside radius R. Thus, z̄i = zi min 1, ∥zi ∥2 denotes the clipped vector zi . The output ot is an empirical mean protected by the Gaussian Mechanism: N

ot = Mγ (Zt ) =

t 1 X z̄i + ηt , Nt i=1

 ηt ∼ N

0,

γ2 Id×d Nt

 (6)

This corresponds to each user adding an independent Gaussian noise N (0, γ 2 Id ) to their clipped record (whose ℓ2 -sensitivity is 2R). To satisfy a given zero-concentrated differential privacy (zCDP) budget ρ (Bun & Steinke, 2016) for each individual contribution, the platform must set the noise 2 parameter to γ 2 = 2R ρ . The utility is measured through the expected squared Mahalanobis distance between the private release and the true population mean µ (Biswas et al., 2020; Azize & Basu, 2025; Leemann et al., 2024), which the platform seeks to minimize (see discussion in Appendix E). The following lemma computes this error explicitly, conditioned on a given population size. Lemma 3 (Conditional Expected Mahalanobis Error). Let Zt be a dataset drawn from a distribution with true mean µ and covariance matrix Σ, and neglect the clipping bias (i.e., assume z̄i = zi ). Since γ2 the noise vector ηt has covariance Cγ = N I, the expected squared Mahalanobis error is: t   γ 2 Tr(Σ−1 ) + d E ∥ot − µ∥2Σ−1 Nt = Nt

(7)

In the next Section 4.2, we define the privacy leakage in this setting, and then derive generic bound in Section 4.3 and an exact expression in the Gaussian case in Section 4.4. 4.2

M EMBERSHIP I NFERENCE AND THE V ULNERABILITY T HRESHOLD

Where Section 3 defined leakage via the discrete event Xi,t = Yi,t , exposure in continuous aggregates (ot ∈ Rd ) is quantified by a record’s statistical influence on ot . By the Neyman-Pearson lemma, the optimal test statistic for the hypothesis z ∈ Zt is the log-likelihood ratio:   Pr[Mγ (Zt ) = ot | z ∈ Zt ] Λ(ot |z) ≜ ln (8) Pr[Mγ (Zt \ {z}) = ot ] where Pr[·] denotes the density of the output. The magnitude of Λ(ot |z) indicates how much skew z exerts on the noisy sample mean ot given we observe the set Zt . 6

Preprint.

Vulnerability Threshold (τ ). Practically, an individual cannot compute Λ(ot |z) without access to Zt . However, it is the quantity approximated by external adversaries and auditing tools in modern Membership Inference Attacks (MIAs) Shokri et al. (2017); Carlini et al. (2021). Conditioning user departure on this mathematical quantity thus provides a worst-case upper bound against any adversary. The privacy tolerance is captured via a constant threshold τ > 0, such that a record is compromised if Λ(ot |z) > τ . From a hypothesis testing perspective, maintaining a fixed false positive rate would require scaling the threshold with the dimension d and the population size Nt over time, but we keep it constant for simplicity. Performative Dynamics. At round t, each participant z ∈ Zt updates their status for the subsequent round: if Λ(ot |z) > τ , the individual departs with probability q; otherwise (Λ(ot |z) ≤ τ ), the individual remains and recruits one additional participant with probability r. as described in Algorithm 1. Algorithm 1 Private Mean Estimation under MIA leaving process 1: Input: Initial size N0 , Dist. D, Mechanism M, Threshold τ , Probs. q, r, Rounds T 2: Output: Sequence (N1 , . . . , NT ) 3: Set N1 = N0 4: for t = 1, . . . , T do 5: if Nt = 0 then 6: break 7: Sample fresh dataset Zt ∼ DNt 8: Sample candidate output ot ∼ M(Zt ) ▷ M performs ℓ2 clipping ∀z ∈ Zt internally 9: Initialize next population size Nt+1 ← Nt 10: for each z ∈ Zt do ▷ Performative Mechanism   Pr[M(Zt )=ot |z∈Zt ] 11: Λ(ot |z) ← ln Pr[M(Zt \{z})=ot ] 12: if Λ(ot |z) > τ then 13: Nt+1 ← Nt+1 − 1 with prob. q 14: else 15: Nt+1 ← Nt+1 + 1 with prob. r 16: Return (N1 , . . . , NT )

4.3

G ENERAL B OUND ON THE L EAKAGE P ROBABILITY

Computing the exact trajectory of the population size requires the knowledge of the marginal leakage (t) probability pτ = Pr(Λ(ot |z) > τ ). For arbitrary data distributions, deriving the exact probability density function of the log-likelihood ratio is intractable. Instead, we provide an upper bound on the leakage probability that involves the Rényi divergence, and thus makes the link with Rényi DP (Mironov, 2017), via Markov’s inequality. Lemma 4 (Tail Bound on the Leakage Probability). Let Zt be the dataset at the beginning of round t and z ∈ Zt be a target record. Let ot ∼ M(Zt ) be the candidate output. Define the factual M and counterfactual output distributions as PinM (·) = Pr[M(Zt ) = · | z ∈ Zt ] and Pout (·) = Pr[M(Zt \ {z}) = ·].  M  P (o ) For the log-likelihood ratio Λ(ot |z) = ln PinM (ott ) evaluated at output ot , and for any threshold out τ > 0 and order α > 1, the tail probability of leakage is bounded by: 
 M Pr (Λ(ot |z) > τ ) ≤ exp − (α − 1) τ − Dα (PinM ∥ Pout ) ot ∼PinM

M where Dα (PinM ∥ Pout ) is the Rényi divergence of order α.

The bound in 4 can easily be applied to any DP mechanism outputs, as it depends explicitly on the Renyi divergence. It also exhibits exponential dependency in τ , demonstrating the threshold carefully. Finally, to make the tightest possible bound, we should optimize over the order α while keeping it strictly greater than 1 to use RDP. To illustrate it, we apply it to the Gaussian mechanism. However, for analytical tractability we condition the leakage probability on observing Zt first. 7

Preprint.

4.4

T HE G AUSSIAN PARTICULAR C ASE

In this subsection, we exploit the fact that the injected algorithmic noise is normally distributed to derive the exact closed-form distribution of the log-likelihood ratio conditioned on the data for any given point. We then derive an exact closed-form expression for the unconditional leakage probability under the additional assumption that the data distribution is Gaussian. This Gaussiandata assumption is required only for the results beginning with lemma 8 and is not needed for the preceding results. For simplicity, we initially assume that M is clipping-free. This assumption will PNt be relaxed in subsequent results. Therefore, let µz ≜ N1t i=1 zi denote the sample mean of zi ’s. Lemma 5 (Upper Bound for the Gaussian Mechanism). Substituting into Lemma 4 the Rényi divergence of the Gaussian mechanism equation 6 between the outputs with and without the record z conditioned on the entire dataset Zt , namely M Dα (PinM (·|Zt ) ∥ Pout (·|Zt )) =

αNt ∥z − µz ∥2 2γ 2 (Nt − 1)2

(see Lemma 11 in Appendix D), the tail bound on the leakage probability for a specific record z specializes to:    αNt ∥z − µz ∥2 Pr (Λ(ot |z) > τ | Zt ) ≤ exp −(α − 1) τ − . (9) 2γ 2 (Nt − 1)2 ot ∼PinM This closed-form bound makes explicit, first, the dependence on ∥z−µz ∥2 : outliers face an exponentially increasing probability of leakage as their deviation from the empirical mean grows. Second, when the population size Nt increases, the divergence decreases, capturing the privacy amplification afforded by aggregation and leading to a virtuous circle: if the system is in a regime private enough to gain users, it becomes more likely to keep growing as the leakage risk decreases. This inequality can be minimized with respect to the Rényi order α, yielding the optimal order α∗ =

1 τ γ 2 (Nt − 1)2 + 2 Nt ∥z − µz ∥2

subject to α∗ > 1.

Thus the optimized bound is valid and non-vacuous only when τ>

Nt ∥z − µz ∥2 , 2γ 2 (Nt − 1)2

i.e., only when the individual’s baseline privacy tolerance strictly exceeds their deviation from the empirical mean rescaled by the current parameters. This condition fails precisely for extreme spatial outliers and in low-noise regimes (γ → 0), where α∗ ≤ 1 either invalidates the divergence or trivializes the bound (i.e., it collapses to 1). Writing a≜

Nt ∥z − µz ∥2 , 2γ 2 (Nt − 1)2

substituting α∗ back into equation 9 yields, for τ > a, the optimized bound   (τ − a)2 . Pr (Λ(ot |z) > τ | Zt ) ≤ exp − 4a ot ∼PinM

(10)

As Lemma 6 below shows that Λ(ot |z) | Zt ∼ N (a, 2a)

√ 2 exactly, the standard Gaussian tail bound 1 − Φ(u) ≤ e−u /2 applied at u = (τ − a)/ 2a gives the same exponent: the optimized Rényi bound is tight up to the Φ-versus-exp gap. In the special case of the Gaussian mechanism, we are however able to provide the exact leakage probability through a direct computation of Λ. Lemma 6. Let a mechanism output ot be perturbed by additive isotropic Gaussian noise ηt ∼ γ2 N (0, N Id×d ), representing the noise. The log-likelihood ratio Λ(ot |z) conditioned on Zt is given t by: Nt ∥z − µz ∥2 Nt ⟨z − µz , ηt ⟩ + Λ(ot |z) | Zt = 2 2 2(Nt − 1) γ (Nt − 1)γ 2 8

Preprint.

And it is distributed as:  Λ(ot |z) | Zt ∼ N

Nt ∥z − µz ∥2 Nt ∥z − µz ∥2 , 2(Nt − 1)2 γ 2 (Nt − 1)2 γ 2



Lemma 7. Given the aggregated empirical mean mechanism, the exact probability that a specific individual data point z is purged (i.e., its log-likelihood ratio breaches the threshold τ ) conditioned on Zt is given in closed form by: √   τ (Nt − 1)γ Nt ∥z − µz ∥ Pr(Λ(ot |z) > τ | Zt ) = 1 − Φ √ − 2(Nt − 1)γ Nt ∥z − µz ∥ where Φ(·) denotes the cumulative distribution function of the standard normal distribution. Unlike the generalized Rényi divergence bound in equation 9, which yields a conservative upper limit subject to rigid parametric constraints, Lemma 7 exactly characterizes the tail probability of leakage. This closed-form expression eliminates the theoretical fragility associated with spatial outliers. √ Remark√ 1 (Connection to Gaussian DP). With µz′ ≜ Nt ∥z − µz ∥/(γ(Nt − 1)) ≈ ∥z − µz ∥/(γ Nt ), Lemma 6 reads Λ(ot |z) | Zt ∼ N (µ2z′ /2, µ2z′ ), which is the privacy loss of a µz′ -Gaussian-DP pair (Dong et al., 2022): for the record z, membership inference is exactly as hard as testing N (0, 1) against N (µz′ , 1). Lemma 7 is then the power of the Neyman–Pearson test at likelihood-ratio threshold eτ — equivalently, of the Bayes-optimal attack with prior odds of membership e−τ . Thus, maintaining a fixed FPR ν corresponds to the record-dependent threshold 2 τ = µz′ Φ−1 (1 − ν) − µ √z′ /2, as discussed in Section 4.2, and since ∥z̄∥2 , ∥µz̄ ∥2 ≤ R, one recovers the worst-case (2R/(γ Nt ))-Gaussian-DP guarantee. We now focus on this setting allowing the clipping of vectors for the rest of our results, under the following assumption. Assumption 1. We assume that the records are drawn independently and identically from a ddimensional multivariate Gaussian distribution, (z ∼ N (µ, Σ)), with probability density function   1 1 fN (z) = p exp − (z − µ)T Σ−1 (z − µ) . 2 (2π)d |Σ| (t−1)

, as Lemma 8 (Expected Population Evolution). We define the marginal leakage probability, pτ the expected fraction of the population that breaches the privacy threshold τ at round t − 1, i.e (t−1) = E(1(Λ(ot−1 |z) > τ ). Letting z̄ denote the record subjected to the clipping and µz̄ denote pτ the sample mean of clipped vectors, the marginal leakage probability evaluates to: " !# Nt−1 p Y s Nt−1 τ (Nt−1 − 1)γ (t−1) p pτ = 1−Φ − fN (zj ) dz1:Nt−1 , (11) 2(Nt−1 − 1)γ s Nt−1 dN j=1

Z

R

t−1

Where s ≜ ∥z̄1 −µz̄ ∥2 and dz1:Nt−1 ≜ dz1 ·. . . dzNt−1 .Under assumption 1, the expected population size at round t in Algorithm 1, is given by:   E[Nt | Nt−1 ] = Nt−1 1 + r − (q + r)p(t−1) (12) τ Lemma 8 gives an exact characterization of the user population evolution. As in Lemma 2, the expected population is the previous population multiplied by a growth factor. However, unlike the previous case, this factor is determined by the marginal leakage probability pτ , whose integral form captures the dependence on several parameters: the dimension d, the threshold τ , the clipping bound R and the noise scale γ, instead of relying only on the privacy parameter β. 4.5

C RITICAL N OISE T HRESHOLD FOR USER POPULATION S URVIVAL

To determine whether the user population survives or collapses, we denote similarly as before Ct (γ) the expected ratio of the population size between consecutive rounds t and t − 1: Ct (γ) ≜

E[Nt | Nt−1 ] = 1 + r − (q + r)p(t−1) (γ) τ Nt−1 9

(13)

Preprint.

(t−1)

The continuous growth factor Ct (γ) = 1+r−(q+r)pτ (γ) mirrors the discrete model of Lemma 2 by substituting the leakage probability 12 + β of randomized response with the marginal leakage (t−1) probability pτ (γ). This substitution preserves the system’s monotonicity: increasing the noise (t−1) (t−1) γ strictly decreases pτ (γ), improving population stability. However, because pτ (γ) requires evaluating a non-linear integral over a multivariate data distribution, the boundary condition Ct (γ) ≥ 1 cannot be inverted analytically in general, but it can easily be computed numerically. Moreover, C is now time-dependent unlike in section 3, introducing an additional layer of performative dynamics into the system.

(a) pτ vs τ

(b) C(γ) vs γ for small q

(c) C(γ) vs γ for large q

Figure 3: Behavior of pτ with τ and C(γ) with γ, comparing theoretical predictions with empirical simulations. (a) N = 100; (b) T = 50; (c) T = 10, with the population clipped at 20,000. Since the marginal leakage probability pτ (γ) is a function of the mechanism’s noise scale, the platform can directly steer the demographic growth by tuning γ. The boundary condition for √ demographic survival is C(γ) ≥ 1. Under the minor assumption that the clipping bound R = Ω( d), the following theorem establishes a critical noise threshold γc that is sufficient to satisfy this condition and prevent a demographic collapse. Theorem 2 (Critical Noise Threshold for Demographic Survival). The condition Ct (γ) ≥ 1 is guaranteed as soon as the mechanism’s noise scale satisfies the explicit lower bound γ ≥ γc . Given √ an ℓ2 clipping bound R = Ω( d), the critical threshold γc is defined as: q p   −1 2 + Φ (Φ−1 q,r ) + 2τ dNt−1 q,r   γc ≜ Ω  (14) Nt−1 − 1 2τ   q −1 ≜ Φ where Φ−1 is the probit function (the inverse of the standard normal cumulative q,r q+r distribution function) evaluated at the performative survival threshold. As before, Ct (γ) < 1 implies a demographic collapse initiated at round t, destroying the platform’s utility over time, which means that a minimum level of privacy is needed for long-term success. Furthermore, p the explicit formulation of γc decouples the geometric requirements of the data distribution (≈ d/Nt−1 ) from the purely behavioral constraints of the population (the Φ−1 q,r and τ terms). Recall that in this setting the utility is measured by the Mahalanobis error; the following theorem provides tight, finite-sample bounds on its expectation. Theorem 3 (Finite-Sample Bounds on the Expected Mahalanobis Error). Assume that the population is floored at one participant (Nt ≥ 1). Conditioned on Nt−1 , the expected squared Mahalanobis error of the private empirical mean ot satisfies:     γ 2 Tr(Σ−1 ) + d γ 2 Tr(Σ−1 ) + d 1 2 ≤ E ∥ot − µ∥Σ−1 Nt−1 ≤ ·O (15) C(γ)Nt−1 C(γ)Nt−1 1−q where the asymptotic notation in the upper bound is particularly useful in the regime q → 1. Proof sketch. Since the estimation error scales as 1/Nt , we bound E[1/Nt | Nt−1 ]. The lower bound follows from Jensen’s inequality, while the upper bound uses the Kantrovich-type inequality for the multiplicative inverse function; see Appendix D. 10

Preprint.

(a) Empirical heatmap

(b) Theoretical heatmap

(c) γ ∗ line plot comparison

(d) Empirical heatmap

(e) Theoretical heatmap

(f) γ line plot comparison

Figure 4: Comparison of the optimal noise scale γ ∗ obtained from theory and simulations. The first row corresponds to τ = 0.02, while the second row corresponds to τ = 0.05. For each value of τ , the left panel shows the empirical heatmap, the middle panel shows the theoretical heatmap, and the right panel compares the theoretical and empirical optimal γ as a function of the join probability. Theorem 3 establishes that the expected unconditional estimation error at round t, i.e., Et (γ) ≜ E[|ot − µ|2Σ−1 ], balances the mechanism variance in the numerator against the expected population size, E[Nt ] = E[E[Nt | Nt−1 ]], in the denominator. Using a mean-field approximation on Nt , we Qt approximate the latter as E[Nt ] ≈ N0 k=1 Ck (γ). Since we keep γ constant throughout the entire experiment, we need to scale γc with the minimum√ population size permissible by the system, say Nmin to ensure Ct (γ) > 1 for all t, i.e., γc ∝ 1/ Nmin . This explicit scaling law allows us to evaluate the system’s asymptotic behavior under extreme noise regimes. Remark 2 (Finite-Horizon Optimization). Corollaries 1 and 2 prove that the zero-noise regime (γ → 0+ ) implies geometric demographic collapse and diverging error. On the other hand, when noise increases (γ → ∞) it enables unbounded exponential growth that eventually dominates the variance injected into the mechanism in our simplified model. Thus, for an infinite time horizon, infinite noise is theoretically optimal: the more private the mechanism is, the faster the growth. As practitioners operate under a finite horizon T where the total population remains strictly bounded, we complement this result with a finite-horizon analysis. Lemma 9 (Upper Bound on Cumulative Expected Error over a Finite Horizon). For a finite operational timeline T and an initial population N0 , let Ct (γ) > 1 denote the strictly positive expected per-round demographic growth factor for all t. Under mean field-approximation of Nt , the cumulaPT tive expected Mahalanobis error aggregated across all T rounds, defined as Etotal (γ) ≜ t=1 Et (γ) is upper bounded by Etotal (γ) ≤ Êtotal (γ), where:   1 γ 2 Tr(Σ−1 ) + d Êtotal (γ) ≜ 1− (16) N0 (C1 (γ) − 1) [C1 (γ)]T Remark 3 (Optimization in the Growth Regime). In the growth regime, where γ ≥ γc and consequently Ct (γ) > 1 for all t, directly optimizing the upper bound Êtotal (γ) rather than the exact cumulative error Etotal (γ) is a principled and practical surrogate objective. Corollary 2 shows that E and Ê share the same convergence rate. Computationally, this substitution is highly advantageous 11

Preprint.

as it depends solely on the initial expected growth factor C1 (γ), bypassing the need to recursively track the dynamic sequence Ct (γ) across all T rounds. Furthermore, empirical evaluations confirm that optimizing this upper bound yields a highly effective configuration in practice. Optimization of the Global Noise Scale (γ ∗ ) This closed-form objective in equation 16 makes explicit the trade-off between providing better utility at a given round and a larger population at the next round. Increasing γ penalizes the numerator via the quadratic variance term (γ 2 ), but simultaneously reduces the error by increasing the growth factor C(γ) in the denominator. We cannot (0) compute a closed form of γ ∗ = arg minγ>γc Êtotal (γ). Indeed, the marginal leakage pτ nested within C1 (γ) is governed by the standard normal cumulative distribution function Φ(·), so setting the derivative of this objective to zero does not yield a closed-form algebraic solution. However, Êtotal (γ) is a smooth, one-dimensional objective function and γ ∗ can easily be computed with numerical solvers. We thus compute the theoretical γ ∗ heatmap over the population’s recruitment rate r and leaving rate q. As reported in Figure 4 (and also in Figure 5 in Appendix A), the theoretical γ ∗ closely aligns with the optimal empirical parameters discovered via grid search.

5

D ISCUSSION AND FUTURE WORK

We showed that private mean estimation can outperform non-private estimation in the long term when participants drop out after their data is leaked. These results demonstrate that utility maximization can align with strong privacy protection when there is a sufficiently strong feedback loop. This paper introduces performative privacy as the study of the long-term interplay between privacy and utility under repeated model deployment, at the intersection of privacy-preserving machine learning and performative learning. We focused on mean estimation, but we plan to extend our results to more complex learning tasks. The feedback loop is also kept as simple as possible, but could be made more realistic using epidemic models and more complex privacy preferences and composition over time. Finally, this could motivate varying the privacy budget over time, in particular to minimize regret over the full trajectory.

ACKNOWLEDGMENTS The authors are supported by the National Research Agency under France 2030, reference “ANR23-IACL-0008”. Preliminary work while Edwige Cyffers was visiting the Simons Institute for the Theory of Computing. Edwige Cyffers thanks Max Cairney-Leeming for the joke which started this line of work. Uddalak Mukherjee would like to acknowledge“Verified Deep Learning: Formal Methods Perspective” project under Ansuman Banerjee of ACMU, Indian Statistical Institute, Kolkata.

R EFERENCES Michael Aerni, Jie Zhang, and Florian Tramèr. Evaluations of machine learning privacy defenses are misleading. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS ’24, pp. 1271–1284, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400706363. doi: 10.1145/3658644.3690194. URL https: //doi.org/10.1145/3658644.3690194. 3 Achraf Azize and Debabrota Basu. Some targets are harder to identify than others: Quantifying the target-dependent membership leakage. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. URL https://openreview.net/forum?id=0ebspjSSXk. 3, 6 Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 33:14475– 14485, 2020. 6 12

Preprint.

Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pp. 1005–1014, 2021. 2 Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pp. 6045–6061, 2022. 3 Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, pp. 635–658. Springer, 2016. 6 Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, pp. 1–10, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327107. doi: 10.1145/2591796.2591877. URL https: //doi.org/10.1145/2591796.2591877. 3 Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, A. Terzis, and Florian Tramèr. Membership inference attacks from first principles. 2022 IEEE Symposium on Security and Privacy (SP), pp. 1897–1914, 2021. URL https://api.semanticscholar.org/CorpusID: 244920593. 3, 7 Syomantak Chaudhuri, Konstantin Miagkov, and Thomas A. Courtade. Mean estimation under heterogeneous privacy demands. IEEE Transactions on Information Theory, 71(2):1362–1375, February 2025. ISSN 1557-9654. doi: 10.1109/tit.2024.3511498. 2 Rachel Cummings and David Durfee. Individual sensitivity preprocessing for data privacy. pp. 528–547, 2020. 2 Rachel Cummings, Katrina Ligett, Aaron Roth, Zhiwei Steven Wu, and Juba Ziani. Accuracy for sale: Aggregating data with a variance constraint. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS), pp. 317–324, 2015. 2 Rachel Cummings, Gabriel Kaptchuk, and Elissa M. Redmiles. “I need a better description”: An investigation into user expectations for differential privacy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 3037–3052, 2021. 2 Rachel Cummings, Hadi Elzayn, Vasilis Gkatzelis, Emmanouil Pountourakis, and Juba Ziani. Optimal data acquisition with privacy-aware agents. 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 210–224, 2022. 2 Edwige Cyffers. Setting epsilon is not the issue in differential privacy. In Proceedings of the 39th International Conference on Neural Information Processing Systems, 2025. 1, 2 Edwige Cyffers, Muni Sreenivas Pydi, Jamal Atif, and Olivier Cappé. Optimal classification under performative distribution shift. In Advances in Neural Information Processing Systems, volume 37, 2024. doi: 10.52202/079017-2175. 3 Kate Donahue and Jon Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 5303–5311, 2021. 2 Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022. 3, 9 Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4), 2013. 1, 3 Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Berlin, Germany, 2006. Springer Berlin Heidelberg. 1 13

Preprint.

Danielle Ensign, Sorelle A. Friedler, Scott Neville, Carlos Scheidegger, and Suresh Venkatasubramanian. Runaway feedback loops in predictive policing. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency (FAT*), volume 81 of Proceedings of Machine Learning Research, pp. 160–171, 2018. 3 European Parliament and Council of the European Union. Regulation (EU) 2016/679 of the European Parliament and of the Council. 1 Mathieu Even, Clément Berenfeld, Linus Bleistein, Tudor Cebere, Julie Josse, and Aurélien Bellet. Causal evaluation of membership inference attacks, 2026. URL https://arxiv.org/abs/ 2602.02819. 3 Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman E. Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. Proceedings of the 23rd ACM Conference on Economics and Computation, 2022. 2 Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a Rényi filter. In Advances in Neural Information Processing Systems, volume 34, pp. 28080–28091, 2021. 3 Arpita Ghosh and Aaron Roth. Selling privacy at auction. In Proceedings of the 12th ACM Conference on Electronic Commerce, EC ’11, pp. 199–208, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450302616. doi: 10.1145/1993574.1993605. 2 Mahdi Haghifam, Adam Smith, and Jonathan Ullman. The sample complexity of membership inference and privacy auditing, 2025. URL https://arxiv.org/abs/2508.19458. 3 Moritz Hardt and Celestine Mendler-Dünner. Performative prediction: Past and future. arXiv preprint arXiv:2310.16608, 2023. 2 Moritz Hardt, Meena Jagadeesan, and Celestine Mendler-Dünner. Performative power. In Advances in Neural Information Processing Systems, volume 35, pp. 22969–22981, 2022. 2 Moritz Hardt, Eric Mazumdar, Celestine Mendler-Dünner, and Tijana Zrnic. Algorithmic collective action in machine learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 12570–12586. PMLR, 23–29 Jul 2023. 3 Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 1929–1938, 2018. 3 Nils Homer, Szabolcs Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V. Pearson, Dietrich A. Stephan, Stanley F. Nelson, and David W. Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLoS Genetics, 4(8):e1000167, August 2008. ISSN 1553-7404. doi: 10.1371/journal.pgen.1000167. URL http://dx.doi.org/10.1371/journal.pgen. 1000167. 3 Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, and Aaron Roth. Differential privacy: An economic method for choosing epsilon. In 2014 IEEE 27th Computer Security Foundations Symposium (CSF), pp. 398–410. IEEE, 2014. 2 IBM and Ponemon Institute. Cost of a Data Breach Report 2025. Technical report, IBM, 2025. Accessed 2026-04-30. 1, 2 Andreas Ioannidis, Antonios Litke, and Nikolaos Papadakis. Randomized response and differential privacy. In Proceedings of the 17th International Conference on PErvasive Technologies Related to Assistive Environments, pp. 600–605, 2024. 3 Meena Jagadeesan, Tijana Zrnic, and Celestine Mendler-Dünner. Regret minimization with performative feedback. In ICML, 2022. 3 14

Preprint.

Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: how private is private sgd? In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546. 3 Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium, pp. 1895–1912, 2019. 3 Zachary Jorgensen, Ting Yu, and Graham Cormode. Conservative or liberal? personalized differential privacy. In IEEE International Conference on Data Engineering (ICDE), pp. 1023–1034, 2015. 2 Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Proceedings of the 32nd International Conference on Machine Learning (ICML), volume 37 of Proceedings of Machine Learning Research, pp. 1376–1385, 2015. 3 Sai Praneeth Karimireddy, Wenshuo Guo, and Michael I. Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.04557, 2022. 2 Antti Koskela, Marlon Tobaben, and Antti Honkela. Individual privacy accounting with Gaussian differential privacy. In The Eleventh International Conference on Learning Representations (ICLR), 2023. 3 Jaewoo Lee and Chris Clifton. How Much Is Enough? Choosing ϵ for Differential Privacy, pp. 325–340. Springer Berlin Heidelberg, 2011. ISBN 9783642248610. doi: 10.1007/ 978-3-642-24861-0 22. 1 Tobias Leemann, Bardh Prenkaj, and Gjergji Kasneci. Is my data safe? predicting instancelevel membership inference success for white-box and black-box attacks. In ICML 2024 Next Generation of AI Safety Workshop, 2024. URL https://openreview.net/forum?id= YfzvhsKymO. 3, 6 Katrina Ligett and Aaron Roth. Take it or leave it: running a survey when privacy comes at a cost. In Proceedings of the 8th International Conference on Internet and Network Economics, WINE’12, pp. 378–391, Berlin, Heidelberg, 2012. Springer-Verlag. ISBN 9783642353109. doi: 10.1007/978-3-642-35311-6 28. 2 Katrina Ligett, Seth Neel, Aaron Roth, Bo Waggoner, and Steven Z. Wu. Accuracy first: Selecting a differential privacy level for accuracy-constrained ERM. In Advances in Neural Information Processing Systems, volume 30, 2017. 2 Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimization for performative prediction. In Advances in Neural Information Processing Systems, volume 33, pp. 4929–4939, 2020. 2 Thomas Michel, Debabrota Basu, and Emilie Kaufmann. Sequential membership inference attacks, 2026. URL https://arxiv.org/abs/2602.16596. 3 Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263–275. IEEE, August 2017. doi: 10.1109/csf.2017.11. URL http: //dx.doi.org/10.1109/CSF.2017.11. 7 Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 866–882. IEEE, May 2021. doi: 10.1109/sp40001.2021.00069. URL http://dx.doi.org/10.1109/SP40001.2021.00069. 3 Helen Nissenbaum. Privacy as contextual integrity. Washington Law Review, 79(1):119–157, 2004. 1, 2 Kobbi Nissim, Claudio Orlandi, and Rann Smorodinsky. Privacy-aware mechanism design. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), pp. 774–789, 2012. 2 15

Preprint.

Mallesh M. Pai and Aaron Roth. Privacy and mechanism design. ACM SIGecom Exchanges, 12(1): 8–29, 2013. ISSN 1551-9031. doi: 10.1145/2509013.2509016. 2 Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. volume 119 of Proceedings of Machine Learning Research. PMLR, 2020. 2, 3 Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113–1201, 2023. ISSN 1076-9757. doi: 10.1613/jair.1.14649. 1 Aaron Roth and Grant Schoenebeck. Conducting truthful surveys, cheaply. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC ’12, pp. 826–843, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450314152. doi: 10.1145/2229012. 2229076. 2 Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Herve Jegou. Whitebox vs black-box: Bayes optimal strategies for membership inference. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5558–5567. PMLR, 09– 15 Jun 2019. URL https://proceedings.mlr.press/v97/sablayrolles19a. html. 3 Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), San Jose, CA, USA, May 2017. URL https://www.ieee-security.org/TC/ SP2017/program-papers.html. 3, 7 Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Nicolas Papernot, Ross Anderson, and Yarin Gal. AI models collapse when trained on recursively generated data. Nature, 631:755–759, 2024. 3 Scott Skinner-Thompson. Performative privacy. UC Davis Law Review, 50(4), 2017. NYU School of Law, Public Law Research Paper No. 17-10; U of Colorado Law Legal Studies Research Paper No. 17-4. 2 Daniel J. Solove. Understanding Privacy. Harvard University Press, Cambridge, MA, 2008. GWU Legal Studies Research Paper No. 420, GWU Law School Public Law Research Paper No. 420. 1 Seamus Somerstep, Ya’acov Ritov, and Yuekai Sun. Algorithmic fairness in performative policy learning: Escaping the impossibility of group fairness. In The 2024 ACM Conference on Fairness Accountability and Transparency, FAccT ’24, pp. 616–630. ACM, 2024. doi: 10.1145/3630106. 3658929. 3 Rohan Taori and Tatsunori Hashimoto. Data feedback loops: Model-driven amplification of dataset biases. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pp. 33883–33920, 2023. 3 Anvith Thudi, Ilia Shumailov, Franziska Boenisch, and Nicolas Papernot. Bounding membership inference. arXiv preprint arXiv:2202.12232, 2022. 3 Yu-Xiang Wang. Per-instance differential privacy. Journal of Privacy and Confidentiality, 9(1), 2019. 3 Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In EDBT/ICDT Workshops, volume 1558, pp. 0090–6778, 2016. 3 Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965. doi: 10.1080/01621459. 1965.10480775. 2 Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375–389, 2010. 3 16

Preprint.

Aiping Xiong, Tianhao Wang, Ninghui Li, and Somesh Jha. Towards effective differential privacy communication for users’ data sharing decision and comprehension. In 2020 IEEE Symposium on Security and Privacy (SP), pp. 392–410, 2020. doi: 10.1109/SP40000.2020.00088. 2 Jiayuan Ye, Aadyaa Maddi, Sasi Kumar Murakonda, Vincent Bindschaedler, and Reza Shokri. Enhanced membership inference attacks against machine learning models. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 3093– 3106, 2022. 3 Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. 2018 IEEE 31st Computer Security Foundations Symposium (CSF), pp. 268–282, 2017. URL https://api.semanticscholar.org/ CorpusID:2656445. 3 Da Yu, Gautam Kamath, Janardhan Kulkarni, Tie-Yan Liu, Jian Yin, and Huishuai Zhang. Individual privacy accounting for differentially private stochastic gradient descent. Transactions on Machine Learning Research, 2023. 3 Xueru Zhang, Mohammad Mahdi Khalili, Cem Tekin, and Mingyan Liu. Group retention when using machine learning in sequential decision making: the interplay between user dynamics and fairness. In Advances in Neural Information Processing Systems, volume 32, 2019. 3 Haiqing Zhu, Tijana Zrnic, and Celestine Mendler-Dünner. Look-ahead reasoning on learning platforms. In Advances in Neural Information Processing Systems, 2025. 3

17

Preprint.

Appendix Table of Contents A More Experiments on Membership Inference Leaving Process

19

B The Agnostic Model

20

C Proofs from Section 3 C.1 Properties of the Estimator . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Population Evolution and Critical Noise Threshold . . . . . . . . . . . . . . . .

21 21 22

D Proofs from Section 4 D.1 Generic Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Results for Gaussian Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . D.3 Population Evolution and Critical Noise Threshold . . . . . . . . . . . . . . . . D.4 Bounds and Asymptotics of the Error . . . . . . . . . . . . . . . . . . . . . . .

23 23 24 26 28

E PAC Guarantee for Mahalanobis Error and Comparison with ℓ2

30

18

Preprint.

A

M ORE E XPERIMENTS ON M EMBERSHIP I NFERENCE L EAVING P ROCESS

(a) Empirical heatmap

(b) Theoritical heatmap

(c) γ line plot comparison

(d) Empirical heatmap

(e) Theory heatmap

(f) γ line plot comparison

(g) Empirical heatmap

(h) Theoritical heatmap

(i) γ line plot comparison

Figure 5: Comparison of the optimal threshold γ obtained from theory and simulations. The first row corresponds to τ = 0.01, the second row corresponds to τ = 0.2 and the third row corresponds to τ = 0.1. For each value of τ , the left panel shows the empirical heatmap, the middle panel shows the theoretical heatmap, and the right panel compares the theoretical and empirical optimal γ as a function of the join probability. Figures 4 and 5 reveal an interesting observation: as (τ ) increases, the empirical noise increasingly underestimates the theoretical prediction because leakage becomes more sensitive to rare, extreme outliers. While the theoretical model assumes an unbounded population, the experimental setup imposes a population cap of 20,000, limiting the occurrence of such extreme samples. Consequently, the discrepancy between theory and experiment becomes more pronounced at larger (τ ).

19

Preprint.

10 3

10 1

10 4 10 5 0

25

50

75

100 125 150 175 200

10 2

100

10 1

0

Time step t

(a) Moving averaged variance for (r, q) = (0.6, 0.3)

25

50

75 100 125 150 175 200

10 2

Time step t

(b) Population evolution (r, q) = (0.6, 0.3)

for

500

(log scale)

100

10 2 10 3

10 1

10 4 0

25

50

75

100 125 150 175 200

10 2

400

100

(log scale)

10 1

Nt (Averaged across trials)

100

Variance (Moving Averaged)

20000 17500 15000 12500 10000 7500 5000 2500 0

(log scale)

Nt (Averaged across trials)

100

10 2

(log scale)

Variance (Moving Averaged)

100 10 1

300 200

10 1

100 0 0

Time step t

(c) Moving averaged variance for (r, q) = (0.3, 0.6)

25

50

75

100 125 150 175 200

10 2

Time step t

(d) Population evolution (r, q) = (0.3, 0.6)

for

Figure 6: In a growing population (r = 0.6, q = 0.3), the system quickly reaches capacity across all privacy budgets, causing variance to stratify based on noise levels and favoring low privacy due to the high growth rate. In contrast, a shrinking population (r = 0.3, q = 0.6) triggers performative collapse; while weak privacy (high ε) initially yields higher utility, it accelerates population decline. This causes variance to spike and eventually converge with stricter privacy regimes as the disappearing user base eliminates any initial advantage.

B

T HE AGNOSTIC M ODEL

This section explores the agnostic model mentioned in Section 3. Under this framework, we assume population growth is directly proportional to the number of participants in the previous iteration, t − 1, regardless of wether or not their data were leaked. Applying a derivation analogous to the proof of Lemma 2, we characterize the evolution of the participant pool as follows:   1 Nt = Nt−1 − Nt−1 q + β + rNt−1 2     1 = Nt−1 1 − q +β +r 2 Under this model, we once again simulate the behavior of the population and variance under the same two regimes of (r, q) = (0.3, 0.6) and (r, q) = (0.6, 0.3) respectively as demonstrated in Figure 6. In the regime (r > q), rapid growth outweighs attrition, driving the population to maximum capacity regardless of the privacy budget. Unlike the previous model — where low privacy could stifle growth or lead to suboptimal stability, this model provides no incentive for privacy, as the highest ε consistently yields the lowest variance. Conversely, when q > r, the variance mirrors the original model’s behavior, yet population decay is notably more gradual, with certain ε values inducing high-variance stochastic collapse across different runs. We also report the utility-maximizing privacy budget ε for each parameter pair in Figure 7. For growing populations (r > q), the models diverge sharply: the original model shows a broad transition favoring intermediate privacy, whereas the agnostic model overwhelmingly favors minimal privacy (highest ε), as rapid growth drives the population to capacity regardless of data use. Maximum privacy is beneficial only within a narrow band just below r = q; outside this regime, strict privacy provides no utility gain. 20

Preprint.

Optimal over (q, r)

1.0

0.50 0.25 0.00 0.6

log10 ( * )

Join Probability (r)

0.8

0.25 0.50

0.4

0.75 0.2

1.00 1.25

0.0 0.0

0.2

0.4

0.6

Leave Probability (q)

0.8

1.0

Figure 7: Global mapping of the optimal privacy budget ε∗ across the (r, q) parameter space for the agnostic model

C

P ROOFS FROM S ECTION 3

C.1

P ROPERTIES OF THE E STIMATOR

Lemma 10. The estimator µ̂t for population Bernoulli mean µt as described in equation 1 is unbiased. Proof. To prove that the estimator µ̂t is unbiased, we first find the expected value of a single privatized response Yi,t . As Xi,t is a Bernoulli variable with mean µt , we have: E[Yi,t ] = P(Xi,t = 1)E[Yi,t | Xi,t = 1] + P(Xi,t = 0)E[Yi,t | Xi,t = 0]     1 1 = µt + β + (1 − µt ) −β 2 2     1 1 1 = µt + β + − β − µt −β 2 2 2   1 1 1 = µt +β− +β + −β 2 2 2 1 = 2βµt + − β 2 Now we evaluate the expected value of the sample mean ν̂t . By linearity of expectation: " # Nt Nt 1 X 1 X E[ν̂t ] = E Yi,t = E[Yi,t ] Nt i=1 Nt i=1   1 1 1 = · Nt 2βµt + − β = 2βµt + − β Nt 2 2 Substituting E[ν̂t ] into the expected value of our estimator µ̂t :   ν̂t − 21 + β E[ν̂t ] − 12 + β E[µ̂t ] = E = 2β 2β
1 1 2βµt + 2 − β − 2 + β = 2β 2βµt = = µt 2β This concludes the proof. Lemma 1. For any given privacy budget ε > 0, setting the perturbation parameter to ε 1 β = tanh 2 2 guarantees that the randomised response mechanism satisfies ε-local differential privacy (ε-LDP). 21

Preprint.

Proof. To satisfy ε-LDP, the maximum ratio of output probabilities (true reporting vs. false reporting) must equal eε : 1 2 +β = eε 1 2 −β

Solving directly for β gives: β=

1 2

 ε  e −1 eε + 1

2z

ε Using the identity tanh(z) = ee2z −1 +1 with z = 2 , this simplifies to: ε 1 β = tanh 2 2

C.2

P OPULATION E VOLUTION AND C RITICAL N OISE T HRESHOLD

Lemma 2. The evolution of the number of participants is given by:     1 1 +β +r − β Nt−1 E[Nt |Nt−1 ] = Nt−1 − Nt−1 q 2 2      1 1 = Nt−1 1 − q +β +r −β 2 2 Proof. Let Dt and At be the number of departures and arrivals at t. The population at time t follows the basic balance equation: Nt = Nt−1 − Dt + At By construction of the model, At and Dt follow Binomial(Nt−1 , r(1/2 − β)) and Binomial(Nt−1 , q(β + 1/2)) respectively. For a sufficiently large population, by the Law of Large Numbers, At and Dt tightly concentrate around their expected values (first-order approximation).

Thus, E[At |Nt−1 ] = r 21 − β Nt−1 and E[Dt |Nt−1 ] = Nt−1 q 12 + β . Substituting these deterministic expectations into the balance equation yields:     1 1 E[Nt |Nt−1 ] = Nt−1 − Nt−1 q +β +r − β Nt−1 2 2      1 1 +β +r −β = Nt−1 1 − q 2 2

Theorem 1. To maintain C(β) ≥ 1, the parameter β must satisfy the explicit upper bound β ≤ βc , where the critical threshold βc is defined as:   r−q βc ≜ max 0, 2(q + r) Proof. Substituting the simplified linear expression for the performative growth factor yields: r−q − β(q + r) ≥ 1 2 r−q =⇒ − β(q + r) ≥ 0 2 Rearranging the inequality to isolate the β term yields: 1+

β(q + r) ≤ 22

r−q 2

Preprint.

Dividing both sides by (q + r), r−q 2(q + r) However, when r ≤ q, the critical point get clipped to zero. Thus,   r−q β ≤ max 0, 2(r + q) β≤

This completes the proof.

D

P ROOFS FROM S ECTION 4

D.1

G ENERIC R ESULTS

Lemma 3. Let Zt be a dataset drawn from a distribution with true mean µ and covariance matrix Σ, and neglect the clipping bias (i.e., assume z̄i = zi ). Assuming the aggregated noise vector ηd has γ2 covariance Cγ = N I, the expected squared Mahalanobis error is: t   γ 2 Tr(Σ−1 ) + d E ∥ot − µ∥2Σ−1 Nt = Nt

(17)

Proof. Since the mechanism’s injected noise ηd is sampled independently from the underlying data distribution D, the expected squared error decouples into two components: the variance introduced by the privacy mechanism and the intrinsic geometric variance of the data sample itself. By applying the linearity of expectation and utilizing the trace trick for quadratic forms (E[xT Ax] = Tr(AΣx ) + µTx Aµx ), we expand the conditional error: " # X 2     1 2 2 (zi − µ) E ∥ot − µ∥Σ−1 Nt = Eηd ∥ηd ∥Σ−1 + 2 ED Nt Σ−1 zi ∈Zt   1 X = Tr(Σ−1 Cγ ) + 2 ED ∥zi − µ∥2Σ−1 Nt zi ∈Zt

γ 2 Tr(Σ−1 ) 1 X = Tr(Σ−1 Σ) + 2 Nt Nt zi ∈Zt

γ 2 Tr(Σ−1 ) + d = Nt where we substitute Cγ = γ 2 I and recognize that Tr(Σ−1 Σ) = Tr(Id ) = d. This bounds the conditional expected error, completing the proof. Lemma 4. Let Zt−1 be the dataset at round t and z ∈ Zt be a target record. Let ot ∼ M(Zt ) be the candidate output. Define the factual and counterfactual output distributions as PinM (·) = M Pr[M(Zt ) = · | z ∈ Zt ] and Pout (·) = Pr[M(Zt \ {z}) = ·].  M  P (o ) For the log-likelihood ratio Λ(ot |z) = ln PinM (ott ) evaluated at output ot , and for any threshold out τ > 0 and order α > 1, the tail probability of structural compromisation is bounded by: 
 M Pr (Λ(ot |z) > τ ) ≤ exp − (α − 1) τ − Dα (PinM ∥ Pout ) ot ∼PinM

M where Dα (PinM ∥ Pout ) is the Rényi divergence of order α.

Proof. We use the Cramer-Chernoff technique to bound the leakage probability of z. By the monotonicity of the exponential function, for any α > 1, the tail event Λ(ot |z) > τ is strictly equivalent to: e(α−1)Λ(ot |z) > e(α−1)τ 23

Preprint.

Applying Markov’s inequality to the non-negative random variable e(α−1)Λ(ot |z) over the factual distribution PinM yields:   Eot ∼PinM e(α−1)Λ(ot |z) Pr (Λ(ot |z) > τ ) ≤ (18) e(α−1)τ ot ∼PinM Expanding the definition of Λ(ot |z) within the expectation, we have:  M # " " α−1 # Pin (ot ) (α−1) ln PinM (ot ) M (o ) Pout t Eot ∼PinM e = Eot ∼PinM M (o ) Pout t 1 M ln EPinM By the definition of Rényi divergence, Dα (PinM ∥ Pout ) = α−1



PinM (ot ) M (o ) Pout t

α−1  . Expo-

nentiating both sides to isolate the expectation yields: " α−1 #   PinM (ot ) M M Eot ∼PinM = exp (α − 1)D (P ∥ P ) α in out M (o ) Pout t Substituting this equivalence back into the numerator of equation 18 gives:   M exp (α − 1)Dα (PinM ∥ Pout )   Pr (Λ(ot |z) > τ ) ≤ ot ∼PinM exp (α − 1)τ Combining the exponents completes the proof: 
 M Pr (Λ(ot |z) > τ ) ≤ exp − (α − 1) τ − Dα (PinM ∥ Pout ) ot ∼PinM

D.2

R ESULTS FOR G AUSSIAN M ECHANISM

Lemma 11. Let M be a Gaussian mechanism for mean estimation over a dataset Zt of size Nt , γ2 which adds noise scaled to the population such that the variance is N I. Let PinM (· | Zt ) and t M Pout (· | Zt ) denote the conditional distributions of the mechanism’s output on adjacent datasets Zt and Zt \ {z}, respectively. For any order α > 1, the Rényi divergence between these distributions is given by: M Dα (PinM (· | Zt )||Pout (· | Zt )) =

αNt ∥z − µz ∥22 2 2γ (Nt − 1)2

Proof. Let the output distributions of the mechanism on the adjacent datasets be defined as PinM (· | γ2 M Zt ) = N (µz , Cγ ) and Pout (· | Zt ) = N (µ−z , Cγ ), with shared covariance matrix Cγ = N Id×d . t Assuming the mechanism computes the mean using the respective dataset sizes, the true, un-noised mean vectors and their difference are: X 1 z − µz 1 X µz = x, µ−z = x, µz − µ−z = Nt Nt − 1 Nt − 1 x∈Zt

x∈Zt \{z}

For two multivariate Gaussian distributions sharing the same covariance matrix Cγ , the Rényi divergence of order α simplifies to the scaled Mahalanobis distance between their means. Substituting 24

Preprint.

t the known difference and the inverse covariance matrix Cγ−1 = N γ 2 I, we obtain: α M Dα (PinM (· | Zt )||Pout (· | Zt )) = (µz − µ−z )⊤ Cγ−1 (µz − µ−z ) 2   ⊤   z − µz Nt α z − µz I = 2 Nt − 1 γ2 Nt − 1 α Nt 1 = · 2 · (z − µz )T I(z − µz ) 2 γ (Nt − 1)2 αNt = 2 ∥z − µz ∥22 2γ (Nt − 1)2

Lemma 6. Let a mechanism output ot be perturbed by additive isotropic Gaussian noise ηt ∼ γ2 Id×d ), representing the noise. The log-likelihood ratio Λ(ot |z) conditioned on the dataset N (0, N t Zt is given by: Nt ∥z − µz ∥2 Nt ⟨z − µz , ηt ⟩ Λ(ot |z) | Zt = + 2 2 2(Nt − 1) γ (Nt − 1)γ 2 And it is distributed as:   Nt ∥z − µz ∥2 Nt ∥z − µz ∥2 Λ(ot |z) | Zt ∼ N , 2(Nt − 1)2 γ 2 (Nt − 1)2 γ 2 Proof. By definition, the log-likelihood ratio compares the probability density of observing the noisy output ot when z is present (with mean µz ) versus when z is absent (with mean µ−z ). Because the γ2 I), the log-likelihood conditioned aggregated additive noise ηt is Gaussian with distribution N (0, N t on Zt evaluates to:     Nt 2 exp − 2γ 2 ∥ot − µz ∥   Λ(ot |z) | Zt = ln  Nt 2 exp − 2γ 2 ∥ot − µ−z ∥  Nt  = 2 ∥ot − µ−z ∥2 − ∥ot − µz ∥2 2γ z−µz Substituting the noisy observation ot = µz + ηt and the shift µ−z = µz − N : t −1 !   2 z − µz Nt 2 µz + ηt − µz − − ∥µz + ηt − µz ∥ Λ(ot |z) | Zt = 2 2γ Nt − 1 ! 2 Nt z − µz 2 = 2 + ηt − ∥ηt ∥ 2γ Nt − 1   Nt ∥z − µz ∥2 2 2 2 = 2 + ⟨z − µz , ηt ⟩ + ∥ηt ∥ − ∥ηt ∥ 2γ (Nt − 1)2 Nt − 1 Nt ∥z − µz ∥2 Nt ⟨z − µz , ηt ⟩ = + 2(Nt − 1)2 γ 2 (Nt − 1)γ 2 2

Nt ∥z−µz ∥ Conditioned on Zt , the term 2(N 2 2 is a deterministic scalar constant. The sole source of rant −1) γ 2

γ domness is the inner product with the aggregated noise vector ηt ∼ N (0, N I). This linear combit nation ⟨z − µz , ηt ⟩ forms a univariate Gaussian with mean 0 and variance

γ2 ∥z − µz ∥2 . Nt t Scaling this by (NtN −1)γ 2 , the conditional variance reduces to: !  2  Nt ⟨z − µz , ηt ⟩ Nt2 γ Nt ∥z − µz ∥2 2 V Z = ∥z − µ ∥ = t z 2 2 4 (Nt − 1)γ (Nt − 1) γ Nt (Nt − 1)2 γ 2

25

Preprint.

Thus,  Λ(ot |z) | Zt ∼ N

Nt ∥z − µz ∥2 Nt ∥z − µz ∥2 , 2(Nt − 1)2 γ 2 (Nt − 1)2 γ 2

 .

This completes the proof. Lemma 7. Given the aggregated empirical mean mechanism, the exact probability that a specific individual data point z is purged (i.e., its log-likelihood ratio breaches the threshold τ ) conditioned on Zt is given in closed form by: √   τ (Nt − 1)γ Nt ∥z − µz ∥ Pr(Λ(ot |z) > τ | Zt ) = 1 − Φ √ − 2(Nt − 1)γ Nt ∥z − µz ∥ where Φ(·) denotes the cumulative distribution function of the standard normal distribution. Proof. From lemma 6, the conditional log-likelihood ratio for a specific data point z and µz strictly follows a Gaussian distribution: √
Nt ∥z − µz ∥2 Nt ∥z − µz ∥ ′ 2 ′ Λ(ot |z) | Zt ∼ N µz , σz where µz = , σz = (19) 2(Nt − 1)2 γ 2 (Nt − 1)γ The probability that Λ(ot |z) exceeds τ is precisely the tail probability of this Gaussian distribution. We evaluate this using the standard normal cumulative distribution function Φ:   Λ(ot |z) − µ′z τ − µ′z Pr(Λ(ot |z) > τ | Zt ) = Pr > Zt σz σz   τ − µ′z =1−Φ σz Substituting the explicit formulae for µ′z and σz from equation 19:   Nt ∥z−µz ∥2 τ − 2(N 2 2 t −1) γ  Pr(Λ(ot |z) > τ | Zt ) = 1 − Φ  √ Nt ∥z−µz ∥ (Nt −1)γ

τ (Nt − 1)γ Nt ∥z − µz ∥2 (Nt − 1)γ √ − =1−Φ √ Nt ∥z − µz ∥ 2(Nt − 1)2 γ 2 Nt ∥z − µz ∥ √   τ (Nt − 1)γ Nt ∥z − µz ∥ =1−Φ √ − 2(Nt − 1)γ Nt ∥z − µz ∥ 



This completes the proof. D.3

P OPULATION E VOLUTION AND C RITICAL N OISE T HRESHOLD

Lemma 8. Given assumption 1 and the performative update rule in mechanism 1, the expected population size at round t, conditioned on the previous population Nt−1 , is given by:   E[Nt | Nt−1 ] = Nt−1 1 + r − (q + r)p(t−1) τ Proof. Let 1(Λ(ot−1 |zi ) > τ ) be the indicator variable denoting whether the i-th data point experiences a privacy leakage exceeding the threshold τ at round t − 1. The exact performative update rule for the population size is defined as:   Nt−1 Nt−1 X X

Nt = Nt−1 − q 1 Λ(ot−1 |zi ) > τ + r Nt−1 − 1 Λ(ot−1 |zi ) > τ  i=1

i=1

Where zi ∈ Zt−1 . Grouping the terms yields: Nt−1

Nt = Nt−1 (1 + r) − (q + r)

X i=1

26

1 Λ(ot−1 |zi ) > τ

Preprint.

Taking the conditional expectation given Nt−1 , we evaluate the joint expectation over the entire dataset Zt−1 = {z1 , . . . , zNt−1 } and the mechanism’s noise ηt−1 :   Nt−1 X
E[Nt | Nt−1 ] = Nt−1 (1 + r) − (q + r)EZt−1 ,ηt−1  1 Λ(ot−1 |zi ) > τ  i=1

By Fubini’s theorem, we distribute the expectation inside the sum. As established, Λ(ot−1 |zi ) for a specific point depends on zi , µz , and the noise ηt−1 . We evaluate the expectation by utilizing the tower property of expectation:   Nt−1 Nt−1 X X

 EZt−1 ,ηt−1  1 Λ(ot−1 |zi ) > τ  = EZt−1 Pr Λ(ot−1 |zi ) > τ | Zt−1 i=1

i=1

From lemma 7, the conditional probability of leakage for any specific data point z is given as: ! p Nt−1 ∥z − µz ∥ τ (Nt−1 − 1)γ Pr(Λ(ot−1 |z) > τ | Zt−1 ) = 1 − Φ p − 2(Nt−1 − 1)γ Nt−1 ∥z − µz ∥ Since all Nt−1 data points are identically distributed, we proceed as follows: E[Nt | Nt−1 ] = Nt−1 (1 + r) " − (q + r)Nt−1 EZt−1 1 − Φ

!# p Nt−1 ∥z − µz ∥ τ (Nt−1 − 1)γ p − 2(Nt−1 − 1)γ Nt−1 ∥z − µz ∥

Since mechanism M in algorithm 1 clips the samples to z̄, we denote the empirical mean on the clipped samples as µz̄ . Thus, the marginal leakage probability for z is !# " p Nt−1 ∥z̄ − µz̄ ∥ τ (Nt−1 − 1)γ (t−1) − . pτ = EZt−1 1 − Φ p 2(Nt−1 − 1)γ Nt−1 ∥z̄ − µz̄ ∥ Which expands as shown in equation 11. Therefore, our final expression is: E[Nt | Nt−1 ] = Nt−1 (1 + r) − (q + r)Nt−1 p(t−1) τ   (t−1) = Nt−1 1 + r − (q + r)pτ This completes the proof. Theorem 2. To prevent demographic collapse and guarantee the expected population survives and continues to grow (maintaining a growth rate C(γ) ≥ 1), the mechanism’s noise scale√γ must strictly satisfy the explicit lower bound γ ≥ γc . Given an ℓ2 clipping bound R = Ω( d), the critical threshold γc is defined as: q p   −1 2 −1 dNt−1 Φq,r + (Φq,r ) + 2τ   γc ≜ Ω  Nt−1 − 1 2τ −1 where Φ−1 q,r ≜ Φ



q q+r



is the Probit function evaluated at the performative survival threshold.

Proof. To ensure the user population survives without decaying, the expected growth rate must be at least 1: C(γ) ≥ 1. Given the definition of the performative growth factor, this restricts the maximum permissible expected marginal leakage probability pτ : r C(γ) ≥ 1 =⇒ 1 + r − (q + r)pτ ≥ 1 =⇒ pτ ≤ q+r Worst-case leakage occurs at the ℓ2 clipping bound R. Thus, ∥z̄ − µz̄ ∥ ≤ 2R. 27

Preprint.

Hence, the worst-case leakage satisfies: ! p R Nt−1 τ (Nt−1 − 1)γ r p − ≤ . (Nt−1 − 1)γ q+r 2R Nt−1

1−Φ

Rearranging to isolate the CDF and applying the Probit function (Φ−1 ) yields: p     R Nt−1 τ (Nt−1 − 1)γ r q −1 −1 p − ≥Φ =Φ ≜ Φ−1 1− q,r . (Nt−1 − 1)γ q+r q+r 2R Nt−1

(20)

Let

(Nt−1 − 1)γ p . 2R Nt−1 Substituting u transforms equation 20 into a standard quadratic equation: u=

τu −

1 2 −1 ≥ Φ−1 q,r =⇒ 2τ u − 2Φq,r u − 1 ≥ 0. 2u

Taking the valid positive root of the quadratic provides the strict lower bound for u: q q −1 2 −1 2 4(Φ ) + 8τ Φ + (Φ−1 2Φ−1 + q,r q,r ) + 2τ q,r q,r = . u≥ 4τ 2τ √ √ −1)γ back into equation 21 and using R = Ω( d), we get: Substituting u = (Nt−1 2R

(21)

Nt−1

q   p −1 2 −1 2R Nt−1 Φq,r + (Φq,r ) + 2τ   ≜ γc γ≥ Nt−1 − 1 2τ q   p −1 2 −1 + Φ (Φ ) + 2τ q,r dNt−1  q,r  = Ω Nt−1 − 1 2τ This establishes the minimum noise necessary to sustain the population explicitly in terms of the dimensionality d, completing the proof. D.4

B OUNDS AND A SYMPTOTICS OF THE E RROR

Theorem 3. Assume that the population is floored at one participant (Nt ≥ 1). Conditioned on Nt−1 , the expected squared Mahalanobis error of the private empirical mean ot is bounded from below and above by:   γ 2 Tr(Σ−1 ) + d γ 2 Tr(Σ−1 ) + d ≤ E ∥ot − µ∥2Σ−1 Nt−1 ≤ κq,r C(γ)Nt−1 C(γ)Nt−1 with

κq,r ≜

(2 + r − q)2 =O 4(1 − q)(1 + r)



1 1−q

(22)

 , since 0 ≤ r, q ≤ 1

where the asymptotic notation in the upper bound is particularly useful in the regime q → 1. Proof. Recall that the exact squared Mahalanobis error, conditioned strictly on a known population size Nt , isolates the population in the denominator:   γ 2 Tr(Σ−1 ) + d E ∥ot − µ∥2Σ−1 Nt = . Nt Taking the conditional expectation given Nt−1 gives   1    2 2 −1 E ∥ot − µ∥Σ−1 Nt−1 = γ Tr(Σ ) + d E Nt 28

 Nt−1 .

Preprint.

Lower Bound.

We apply Jensen’s inequality to the convex function x 7→ 1/x on (0, ∞):   1 1 1 E Nt−1 ≥ = . Nt E[Nt | Nt−1 ] C(γ)Nt−1

Upper Bound. From the performative update rule, the ratio Nt /Nt−1 is a random variable taking values strictly in the interval [1 − q, 1 + r]. By the Kantorovich inequality for the convex function x 7→ 1/x, the expectation of its inverse is bounded by:
2   (1 − q) + (1 + r) Nt−1 1 i. h E Nt−1 ≤ Nt 4(1 − q)(1 + r) E Nt N t−1 Nt−1 Substituting E[Nt | Nt−1 ] = C(γ)Nt−1 and dividing by Nt−1 directly yields:   1 (2 + r − q)2 1 κq,r E Nt−1 ≤ = . Nt 4(1 − q)(1 + r) C(γ)Nt−1 C(γ)Nt−1 CombinedError Bounds.  Multiplying the lower and upper bounds on the expected inverse population by γ 2 Tr(Σ−1 ) + d establishes equation 22. Corollary 1 (Zero-Noise Collapse). For any strictly positive purge rate q > 0, as the algorithmic noise vanishes (γ → 0+ ), the expected estimation error diverges to infinity over time under the mean field approximation of Nt . Proof. As γ → 0+ , the log-likelihood ratio diverges for any z with ∥z − µz ∥ > 0, driving the (t) marginal leakage probability pτ → 1 for all t. The demographic growth factor reduces to Ct (γ) → 1 − q for all t, resulting in an expected population of N0 (1 − q)t . By the lower bound in equation 22, d the expected estimation error is at least of order N0 (1−q) t . For q > 0, the denominator decays to zero, causing the error to diverge as t increases. Lemma 12. Under mean-field approximation, if Ct (γ) > 1 for all t (i.e., the expected population strictly grows), then Ct (γ) is a strictly increasing sequence. Proof. Under the mean-field approximation of Nt , the expected population size at step t is given by Nt = Ct (γ)Nt−1 . Since we are given that Ct (γ) > 1 for all t, the population strictly grows, meaning Nt > Nt−1 (and consequently its inverse shrinks: 1/Nt < 1/Nt−1 ). (t−1)

As Nt grows and 1/Nt shrinks, by the definition of pτ

, it strictly increases. Thus:

p(t−1) > p(t) τ τ To determine the behavior of Ct (γ), we evaluate the difference between consecutive terms: h i h i (t−1) Ct+1 (γ) − Ct (γ) = 1 + r − (q + r)p(t) − 1 + r − (q + r)p τ τ Canceling the 1 + r terms and factoring out (q + r) yields:   Ct+1 (γ) − Ct (γ) = (q + r) p(t−1) − p(t) τ τ (t−1)

(t)

Since q + r > 0 and we established that pτ − pτ > 0, the product of these two positive terms must be positive: Ct+1 (γ) − Ct (γ) > 0 Therefore, Ct (γ) is a strictly increasing sequence. Corollary 2 (Infinite Horizon Asymptotics). For any positive recruitment rate r > 0 and any fixed noise scale γ such that Ct (γ) > 1 for all t, the expected estimation error at round t converges to zero as t → ∞, at the geometric rate O(C1 (γ)−t ) under the mean field approximation of Nt . This rate is fastest in the infinite-noise limit (γ → ∞), where C(γ) → 1 + r. 29

Preprint.

Proof. For a fixed γ with Ct (γ) > 1 for all t, iterating the bounds in equation 22 (under mean-field 2 −1 )+d Qt approximation of Nt ), Et (γ) is at most κq,r Nγ0 Tr(Σ . Due to lemma 12, this quantity is upper C (γ) k=1

k

2 −1 )+d and decays to zero as t → ∞. bounded by κq,r γ NTr(Σ t 0 C1 (γ)

As γ → ∞, the marginal leakage probability vanishes (pτ → 0), maximizing the growth factor to C(γ) → 1 + r and the expected population to N0 (1 + r)t : the exponential expansion of the population eventually dominates the fixed-in-t mechanism variance term γ 2 . This conclusion continues to hold when q is large (even as q → 1) and r > 0 is small but nonzero, provided C(γ) > 1. Although κq,r = O((1 − q)−1 ) may become large as q → 1, it remains independent of t, while C1 (γ)t grows exponentially. Thus, the exponential term eventually dominates the polynomial numerator γ 2 Tr(Σ−1 ) + d and the multiplicative factor κq,r , so the expected estimation error still converges to zero as t → ∞.

Lemma 9. For a finite operational timeline T and an initial population N0 , let Ct (γ) > 1 denote the strictly positive expected per-round demographic growth factor for all t. The cumulative expected PT Mahalanobis error aggregated across all T rounds, defined as Etotal (γ) ≜ t=1 Et (γ) is upper bounded by Etotal (γ) ≤ Êtotal (γ), where:   γ 2 Tr(Σ−1 ) + d 1 Êtotal (γ) ≜ 1− (23) N0 (C1 (γ) − 1) [C1 (γ)]T Proof. To evaluate the true cost of privacy over a finite horizon T , we must aggregate the expected error across all rounds. The cumulative expected Mahalanobis error is the sum of the single-round errors: Etotal (γ) =

T T T X   X γ 2 Tr(Σ−1 ) + d (a) X γ 2 Tr(Σ−1 ) + d ≤ E ∥ot − µ∥2Σ−1 = Qt N0 [C1 (γ)]t k=1 Ck (γ) t=1 t=1 t=1 N0

Where (a) holds due to lemma 12. We apply the formula for sum of a finite geometric series: Êtotal (γ) ≜

T X γ 2 Tr(Σ−1 ) + d t=1

N0 [C1 (γ)]t 1 1 − [C(γ)] T

γ 2 Tr(Σ−1 ) + d = N0 =

γ 2 Tr(Σ−1 ) + d N0 (C(γ) − 1)

!

1 1 − C(γ)

 1−

1 [C(γ)]T

1 C(γ)



This completes the proof.

E

PAC G UARANTEE FOR M AHALANOBIS E RROR AND C OMPARISON WITH ℓ2

To quantify the accuracy of the noisy empirical mean, we use Mahalanobis error, a scale-invariant measure that accounts for covariance structure. For tractability, we first consider the isotropic case, Σ = σ 2 Id , where it reduces to normalized ℓ2 error. We then derive a PAC guarantee giving an explicit finite-sample, high-probability bound on the combined effects of sampling variability and Gaussian noise, providing a baseline for general covariance structures. i.i.d.

Theorem 4 (PAC Mahalanobis Error for a Noisy Gaussian Sample Mean). Let X1 , . . . , XN ∼ N (µ, σ 2 Id ) and define   N γ2 1 X Xi , µ̃ = µ̂ + η, η ∼ N 0, Id , µ̂ = N i=1 N where η is independent of X1 , . . . , XN . For any ϵ, δ ∈ (0, 1), the noisy empirical mean satisfies
Pr ∥µ̃ − µ∥2Σ−1 ≤ ϵ2 ≥ 1 − δ, Σ = σ 2 Id , 30

Preprint.

whenever 1 + γ 2 /σ 2 N≥ ϵ2

r d+2

1 1 d log + 2 log δ δ

! .

Proof. Since µ̂ − µ and η are independent Gaussian random vectors,   σ2 + γ 2 µ̃ − µ ∼ N 0, Id , N 2 1 + γ /σ 2 2 Thus, ∥µ̃ − µ∥2Σ−1 = χd . N By the standard chi-squared tail bound,   √ Pr χ2d ≤ d + 2 dx + 2x ≥ 1 − e−x . Setting x = log(1/δ) gives, with probability at least 1 − δ, ! r 2 2 1 1 1 + γ /σ ∥µ̃ − µ∥2Σ−1 ≤ d + 2 d log + 2 log . N δ δ Hence the desired bound is at most ϵ2 under the stated condition on N . For a target ℓ2 error tolerance satisfying Pr(|µ̃ − µ|22 ≤ ϵ2 ) ≥ 1 − δ, the required sample size obeys ! r σ2 + γ 2 1 1 N≥ d + 2 d log + 2 log . ϵ2 δ δ Thus, under standard DP, the sample size grows linearly with the injected noise variance γ 2 and dimension d. Our setting exhibits a substantially different dependence, as shown in this work. Remark 4. Although ℓ2 and Mahalanobis norms are proportional for Σ = σ 2 Id , they have different interpretations. The ℓ2 norm measures absolute geometric error and depends on feature scale, whereas the Mahalanobis norm is dimensionless and scale-invariant, measuring error in the distribution’s intrinsic geometry. In the non-isotropic case, it further accounts for directional variances and correlations through covariance whitening, unlike ℓ2 , which weights all directions equally. This motivates using Mahalanobis error as our primary metric.

31

Related documents

• Limited Information and Quick Decisions: Consumer Privacy Calculus for Mobile Applications#369755
• The law of data (privacy) protection: a comparative and theoretical study#461811
• A Design Theory for Transparency of Information Privacy Practices#400575
• Federated learning privacy incentives: Reverse auctions and negotiations#177240
• The Ethics of Data Privacy#77220