Differentially Private Model Merging
Qichuan Yin 1 Manzil Zaheer 2 Tian Li 1
arXiv:2604.20985v1 [cs.LG] 22 Apr 2026
Abstract
On the other hand, it is not uncommon for service providers to have access to multiple DP models (e.g., trained with different hyperparameters) with varying privacy parameters. For instance, during model development stage, one may train a non-private model as a reference, and train a portfolio of private models (on the same dataset) to explore the privacy/utility tradeoff. In this work, we therefore ask: can we merge the existing models with different privacy/utility tradeoffs to output a magnitude of models that satisfy certain target privacy requirement efficiently without touching raw data or performing any additional training?
In machine learning applications, privacy requirements during inference or deployment time could change constantly due to varying policies, regulations, or user experience. In this work, we aim to generate a magnitude of models to satisfy any target differential privacy (DP) requirement without additional training steps, given a set of existing models trained on the same dataset with different privacy/utility tradeoffs. We propose two post processing techniques, namely random selection and linear combination, to output a final private model for any target privacy parameter. We provide privacy accounting of these approaches from the lens of Rényi DP and privacy loss distributions for general problems. In a case study on private mean estimation, we fully characterize the privacy/utility results and theoretically establish the superiority of linear combination over random selection. Empirically, we validate our approach and analyses on several models and both synthetic and real-world datasets.
Though various variants of model merging has been extensively studied in prior literature (e.g., Wortsman et al., 2022), it remains open how to merge private models given a target privacy, and how to perform tight accounting of privacy guarantees. For instance, existing privacy composition results (e.g., sequential or advanced composition (Dwork et al., 2010)) are not tailored to any model merging algorithms and may result in a suboptimal privacy/utility tradeoff. To this end, we propose two simple, data-independent algorithms that enables modular and efficient combination of multiple private models to satisfy changing privacy requirements during inference time. We further provide tailored privacy accounting based on Rényi differential privacy (Mironov, 2017b) and privacy loss distributions (Meiser & Mohammadi, 2018; Sommer et al., 2018) for general ML problems, as well as a toy mean estimation problem.
1. Introduction Differential privacy (DP) (Dwork, 2006) offers a rigorous statistical framework to quantify privacy leakage of random algorithms and has been widely used in practice Abowd et al. (e.g., 2022). During inference or deployment time of real-world applications, the privacy requirements can constantly change due to evolving regulatory and policy contexts, or dynamic user experience. It is therefore critical to update the deployed models quickly while satisfying the target privacy constraints.
In particular, the first merging algorithm is based on the intuitive idea of randomly outputting any model based on some probability distribution (named random selection, or RS). And the second algorithm is to perform a linear combination of the models (named linear combination, or LC). That is to say, suppose the algorithm takes as input two models θ1 and θ2 ,1 RS flips a coin independent of the data and output θ1 with probability π, and θ1 otherwise. LC outputs the deterministic result θλ = λθ1 + (1 − λ)θ2 . In both cases, we provide algorithms to choose mixing coefficients π and λ, aiming to optimize utilities subject to the privacy constraint. Our contributions can be summarized in the following.
In the presence of new target privacy constraints, re-training (or finetuning) a model with DP may need extra hyperparameter tuning (e.g., noise multiplier and gradient clipping threshold) and its implementation of per-gradient clipping can incur significant computation and systems costs (Ponomareva et al., 2023).
• We study the problem of merging private models under the constraints of target privacy during inference time. We introduce two light-weight and data-independent post
1
The University of Chicago 2 Google DeepMind. Correspondence to: Qichuan Yin <[email protected]>.
1
Preprint. April 24, 2026.
1
Our framework handles N models in the rest of the paper.
Differentially Private Model Merging
processing mechanisms, random selection (RS) and linear combination (LC), as well as efficient algorithms on setting the hyperparameters in these mechanisms.
stochastic weight averaging (Izmailov et al., 2018) to the DP setting, and find that averaging checkpoints can improve performance and reduce variance. Shejwalkar et al. (2022) more broadly investigate aggregates of intermediate checkpoints during training to increase the accuracy of DP model. However, most existing work treats merging primarily as a tool to improve performance , rather than as a tool designed to accommodate flexible privacy requirements.
• On general problems, we provide privacy accounting for both mechanisms based on Rényi differential privacy and privacy loss distributions. We discuss a case study on a mean estimation problem where linear combination dominates random selection.
Popular privacy accounting techniques, such as those based on Rényi differential privacy (RDP) and privacy loss distributions (PLD) (Mironov, 2017a;b; Wang et al., 2019; Dong et al., 2022; Meiser & Mohammadi, 2018; Gopi et al., 2021; Koskela et al., 2021; Doroshenko et al., 2022; Sommer et al., 2018), yield tighter bounds on the cumulative privacy loss and have become standard in practical deployments of DPSGD. In this work, we explore RDP and PLD accountant to audit privacy of our proposed approaches. For neighbouring datasets D and D′ , RDP uses Rényi divergence of order α (denoted as Dα ) to measure the difference btween output distributions, forming a curve (RDP parameters or profiles) α 7→ εα , where εα = sup Dα M(D) ∥ M(D′ ) . (1)
• We validate our theoretical claims via empirical evaluation. Additionally, the experiments demonstrate that both RS and LC improve privacy/utility tradeoffs than those under naive privacy accounting in both synthetic and realworld datasets.
2. Related Work and Preliminaries Model Merging. Model merging has emerged as a widely used technique for combining multiple trained models, but focus on non-private settings. Early work focuses on weight averaging of models that share the same architecture, e.g., model souping Wortsman et al. (2022). More sophisticated variants assign data-dependent or sparse weights to individual parameters, such as fisher information-weighted averaging (Matena & Raffel, 2022), TIES (Yadav et al., 2023), or AdaMerging (Yang et al., 2023). These ideas have also been adapted to a wider range of modern applications (Ilharco et al., 2022; Yang et al., 2024; Jin et al., 2022; Yu et al., 2024). To the best of our knowledge, no prior has performed systematic studies on merging private models under DP constraints.
D∼D ′
The main benefit is that it composes additively across T PT (t) steps: εtotal = α t=1 εα . We can then convert (α, εα )RDP into standard (ε, δ)-DP (Mironov, 2017a). PLD-based accounting instead works with the hockey-stick divergence Hε (P, Q) ≜ sup P (S) − eε Q(S) . (2) S
Differential Privacy. Differential privacy (DP) (Dwork, 2006) (Definition 2.1) is a classic statistical framework of measuring privacy properties for randomized algorithms. In machine learning, the dominant approach to enforcing DP constraints is to use DP variants of stochastic gradient descent (DP-SGD (Abadi et al., 2016)), which clip perexample gradients and add calibrated noise at each iteration.
Here P and Q denote the (pessimistic estimate of) output distributions of a mechanism M on neighboring datasets D and D′ , and S is all measurable events. We can track the PLD parameters or profiles via δω (ε) = max{Hε (P, Q), Hε (Q, P )}, and compose privacy loss over steps via convolution (Sommer et al., 2018).
Definition 2.1 (Differential Privacy (Dwork, 2006)). A randomized mechanism M that operates on datasets consisting of individual datapoints is (ε, δ)-DP if for all (measurable) subsets S of outputs and for all neighboring datasets D, D′ that differ in exactly one record, we have
Although PLD-based accounting is often numerically tighter than RDP in practice, we still include RDP results for several reasons. First, RDP typically leads to simpler and more interpretable expressions, which makes the privacy analysis easier to present and understand. The analytical structure of RDP is often more amenable to theoretical comparison (e.g., Section 4.1). Second, RDP accounting is usually computationally lighter and is widely supported in existing DP libraries and pipelines, making it a convenient interface for practical deployment.
Pr[M(D) ∈ S] ≤ eε Pr[M(D′ ) ∈ S] + δ. When δ = 0, we simply say that M is ε-DP. Differential Privacy Model Merging. Model merging in differential privacy have recently emerged as simple yet effective post-processing tools to improve generalization. This direction is particularly appealing because DP-SGD introduces additional noise and often yields less stable checkpoints. Indri et al. (2023) proposed DP-SWA, which adapts
3. Problem Formulation We consider N differentially private algorithms M1 , . . . , MN applied on the same dataset D and 2
Differentially Private Model Merging
each outputting parameters θ1 (D), . . . , θN (D) ∈ Rp . For i ∈ {1, . . . , N }, the training mechanism Mi satisfies (εi , δi )-DP (Definition 2.1). Note that we allow one of the models to be non-private, i.e., some εi → ∞. Our goal is to construct a (possibly randomized) mechanism h that takes as input these N models along with the algorithms, and outputs N ′ ′ θ(D) = h {θi (D)}N i=1 , {Mi }i=1 ; ε , δ
rather than arbitrary ones. In particular, we study the setting where the inputs are associated with some known RDP or PLD parameters (which can be inferred from hyperparameters of the learning algorithms) (Section 5), or where the inputs are directly produced by running DP-SGD (Section 6). In the next sections, we first formally introduce two model merging algorithms (two instances of h), random selection and linear combination (Section 4). We then discuss privacy accounting of RS (Section 5) and LC (Section 6) mechanisms, and consider how to choose an appropriate merger h that exploits the additional assumptions of M.
that satisfies target (ε′ , δ ′ )-DP. Obviously, for suitably large (ε′ , δ ′ ), there always exists a trivial soN ′ ′ lution set h {θi (D)}N ∈ {h : i=1 , {Mi }i=1 ; ε , δ h depends only on the most private θi (D) }. Therefore, rather than identifying a single construction, we aim to characterize a large class of feasible merged outputs with as tight privacy accounting as possible, which translates to better privacy/utility tradeoffs.
4. Model Merging via Random Selection or Linear Combination In this section, we first formally propose two dataindependent merging mechanisms, and illustrate the privacy/utility tradeoff introduced by these mechanisms on a Gaussian mean estimation problem (Section 4.1).
Necessities of Knowing {Mi }N i=1 . Ideally, we would like the merging algorithm h to depend only on the N model parameters {θi (D)}N i=1 without having access to the hyperparameters of the training algorithms {Mi }N i=1 that produce them. However, such mechanism-agnostic post processing merging algorithms may be fundamentally limited. In particular, next we show that when N = 2, under mild regularity conditions, any h that outputs an (ε′ , δ ′ )-DP model must lie very close to the class {h : h depends only on the more private θi (D) }.
Random Selection (RS). We propose a mechanism independent of D that samples a model index I from a categorical distribution and output θI (D) as the merged model. That is, given target privacy (ε′ , δ ′ ), we output θ(D) = θI (D),
Linear Combination (LC). The LC method for N models on dataset D is defined as
′
x,a,b∈Rp
DT V (h(x, a), h(x, b)) >
(4)
where π = (π1 , . . . , πN ) ∈ ∆N −1 (a probability simplex) and π is dependent on (ε′ , δ ′ ) (Section 5). Note that RS only randomly samples one model following some distribution. Another natural choice is to leverage all the models by linearly averaging them.
Proposition 3.1 (No-free-lunch without {Mi }N i=1 ). Assume the mapping h = h θ1 (D), θ2 (D); ε′ , δ ′ (either deterministic or random) is measurable and independent of (M1 , M2 ). Assume ε1 < ε′ < ε2 and δ1 = δ2 = δ. If sup
I ∼ Cat(π1 , . . . , πN ),
1 − e−ε (1 − δ ′ ) , (3) 1 − e−ε2 (1 − δ)
θ(D) =
N X
λi θi (D), λ = [λ1 , · · · , λN ] ∈ ∆N −1 . (5)
i=1
then the merged output h θ1 (D), θ2 (D) cannot be (ε′ , δ ′ )DP for all admissible choices of (M1 , M2 ).
In both cases, as h does not have access to D, the privacy of composing N models is fully determined by how the privacy losses of {Mi }N i=1 aggregated under different instantiations of h, and the main task becomes privacy accounting for the RS or LC procedure.
The complete proof is provided in Appendix A. Condition 3 describes mergers h(·, ·) that react too much to changes in the less private model θ2 . If varying θ2 while fixing θ1 can induce a large total-variation change in the distribution of h(θ1 , θ2 ), then no universal privacy guarantee is possible.
At a high level, RS is entirely characterized by privacy parameters of RDP or PLD, as the output model is randomly sampled from the input N models. Therefore, its privacy accounting depends on the individual selected model’s privacy parameters, making RS broadly applicable even when we do not understand the detailed procedure of the training algorithm (as long as we have access to privacy parameters). In contrast, LC requires to impose stronger assumptions on the structures (e.g., hyperparameters and updating rules) of the training algorithms that produce private input models (formalized in Section 6). Due to stronger assumptions, in
Proposition 3.1 formalizes that, without structural assumption on M1 , M2 , one cannot, in general, design a merger that is substantially different from the trivial merger while satisfying (ε′ , δ ′ )-DP. In particular, any deterministic merger that aims to be valid uniformly over (M1 , M2 ) must lie in the trivial class. Therefore, to obtain meaningful improvements beyond the trivial merger, we focus on practically relevant mechanisms 3
Differentially Private Model Merging
Theorem 4.2. Assume ∆ is small enough. By Lemmas 4.1 , 2 2 when σLC (λ) = σRS (π), the LC estimator with parameter λ achieves privacy no worse than RS with parameter π under RDP. Since for any π ∈ [0, 1] there exists a λ ∈ [0, 1] such 2 2 that σLC (λ) = σRS (π), it follows that LC achieves MSE no larger than RS under the same target RDP privacy budget.
practical scenarios, the best LC strategy can potentially outperform the best RS strategy under the same privacy budget. To make this intuition concrete, we study a special case on a Gaussian mean estimation problem, before introducing general accounting. 4.1. Case Study: Mean Estimation
Theorem 4.2 shows that, under mean estimation and small sensitivity ∆, LC is preferable to RS. This aligns the experiment results in Section 8.1. This is due to LC indeed leverages more models. The problem of mean estimation uses additivity of independent Gaussian noise; such a clean Gaussian structure typically does not exist for general problems. One of the main technical challenges is to develop accurate and tight privacy accounting methods for general model merging under minimal assumptions. In the next two sections, we first analyze RS under the minimal assumption that each candidate mechanism admits privacy accounting via RDP and PLD. We then turn to LC, where we leverage the DP-SGD structure which enables tighter privacy bounds.
This section studies mean estimation with Gaussian distributions, one of the simplest statistical tasks where we can precisely characterize the privacy and utilities of RS and LC, under RDP accounting. In this setting, LC is never worse than RS in terms of meansquared error (MSE) under the same privacy budget. Intuitively, RS discards information by selecting only one candidate, while LC can always choose to mimic RS (by putting all weight on a single model) or improve upon it by averaging across candidates when beneficial. Problem Setup. We observe n one-dimensional I.I.D. Gaussian samples and aim to estimate the unknown mean µ. Let µ̂ denote the empirical mean and assume the ℓ2 sensitivity of outputting µ̂ is ∆. Consider two independent Gaussian mechanisms applied to µ̂ such that the private models satisfy θ1 (D) ∼ N (µ̂, σ12 ) and θ2 (D) ∼ N (µ̂, σ22 ). For any merged estimator θ(D) derived from (θ1 (D), θ2 (D)) by RS or LC, we note that θ(D) is unbiased relative to the empirical mean. The MSE risk decomposes as E (θ(D) − µ)2 = E (θ(D) − µ̂)2 + E (µ̂ − µ)2 ;
5. Privacy of Random Selection Recall that we have trained N private models on the same dataset D, obtaining output parameters θ1 (D), . . . , θN (D) ∈ Rp . As discussed in Section 3, there is no general post-processing algorithm that improves utilities beyond the degenerated solutions if we do not have access to any parameters of the training algorithms {Mi }N i=1 . Hence, for random selection, we assume that we are given the hyperparameters of M, from which we derive the RDP and PLD profiles of each input model. For each Mi , we denote the RDP parameters as {εα,i }α>1 and the PLD privacy parameters as ε 7→ δi (ε). To this end, we develop two complementary accounting techniques: an RDP-based bound that is convenient for analysis and optimization, and a PLD-based method that is typically tighter in practice.
so comparing the MSE of RS and LC reduces to comparing E (θ(D) − µ̂)2 . Main Results. Under random selection with parameter π ∈ [0, 1], the output θ(D) follows a mixed Gaussian distribution π N (µ, σ12 ) + (1 − π) N (µ, σ22 ). While under linear combination with parameter λ, the output θ(D) ∼ N (µ̂, λ2 σ12 + (1 − λ)2 σ22 ). For simplicity, we define mixture distributions Pπ = π N (µ̂, σ12 ) + (1 − π) N (µ̂, σ22 ), Qπ = π N (µ̂ + ∆, σ12 ) + (1 − π) N (µ̂ + ∆, σ22 ), and 2 the RS/LC variance as σRS (π) = πσ12 + (1 − π)σ22 , 2 σLC (λ) = λ2 σ12 + (1 − λ)2 σ22 . Then, we have the following result. Lemma 4.1. For any π, λ ∈ [0, 1], we have RDP parameter (α, εRS α (π)) for RS satisfying εRS α = Dα
Pπ ∥Qπ
RDP Accounting. We begin with the RDP approach by establishing an explicit upper bound on the RDP parameters of RS. Theorem 5.1 ((α, εRS α )-RDP). For any α > 1, random selection (Eq. (4)) over N private models (each being (α, εα,i )-RDP) satisfy (α, εRS α (π))-RDP where εRS α (π) ≤
α∆2 2 2 > 2 (π) + cπ ∆ + o(∆ ), 2σRS
(6)
Theorem 5.1 (proved in Appendix C) provides an explicit upper bound on the RDP parameter of random selection in terms of the individual model’s parameters {εα,i }N i=1 and the mixing weights π ∈ ∆N −1 . This bound immediately enables us to certify (ε, δ)-DP for candidate mixtures via the standard RDP-to-DP conversion as follows. Given a
when ∆ → 0. Here cπ ≥ 0 is a constant depending on π, and when π ∈ (0, 1), cπ > 0. And RDP parameter (α, εLC α (λ)) for LC satisfying εLC α =
N X 1 log πi e(α−1)εα,i . α−1 i=1
α∆2 2 (λ) . 2σLC 4
Differentially Private Model Merging
Algorithm 1 RS with RDP accounting ′
Algorithm 2 RS with PLD accounting
′
1: Input: target privacy (ε′ , δ ′ ); hyperparameter sets of
1: Input: target privacy (ε , δ ), orders grid A; hyperpaN rameter sets of {Mi }N i=1 : {Si }i=1 . N −1
N {Mi }N i=1 : {Si }i=1 . 2: Output: set of π ∈ ∆N −1 satisfying the target privacy. 3: For each i ∈ {1, . . . , N }, obtain the PLD parameters ε 7→ {Hε (Pi , Qi ), Hε (Qi , Pi )} by Si . 4: function P DP Delta(π, ε) N 5: δ+ ← i=1 πi Hε (Pi , Qi ) PN 6: δ− ← i=1 πi Hε (Qi , Pi ) 7: δ RS (π; ε) ← max{δ+ , δ− } 8: return δ RS (π; ε) 9: return {π | DP Delta(π, ε′ ) ≤ δ ′ }
2: Output: set of π ∈ ∆ satisfying the target privacy. 3: For each i ∈ {1, . . . , N }, obtain the RDP parameters
{εα,i }α∈A by Si . 4: function DP Eps(π, δ) 5: for α ∈ A do 6: ai ← (α − 1) εα,i , i ∈ {1, . . . , N }
PN
ai /(α − 1) 7: εRS α (π) ← log i=1 πi e RS 8: εα (π; δ) ← εα (π) + log(1/δ)/(α − 1) 9: return: minα∈A εα (π; δ ′ ) 10: return {π | DP Eps(π, δ ′ ) ≤ ε′ }
Consequently, we have δ RS (ε) is upper bounded by
target failure probability δ ∈ (0, 1), and an order grid A, the εRS α (π)-RDP algorithm satisfies (ε, δ)-DP where log(1/δ ′ ) ′ RS ε := ε(π; δ ) = min εα (π) + . α>1 α−1
max
N nX i=1
πi Hε (Pi , Qi ),
N X
o πi Hε (Qi , Pi ) .
i=1
α∈A
Theorem 5.2 (proved in Appendix D) also yields a simple feasibility test based on the privacy loss distribution of random selection. Given a target privacy parameter ε′ , we evaluate δ RS (ε′ ) for a candidate mixing weight π and π is feasible if and only if δ RS (ε′ ) ≤ δ ′ . We summarize this method in Algorithm 2.
For a target privacy budget ε′ , we accept a mixing weight π if ε(π; δ ′ ) ≤ ε′ . This provides us the criterion for whether a candidate π satisfies the target privacy guarantee. We summarize the method in Algorithm 1. PLD Accounting. In the PLD accounting, we note that random selection induces the mixture distributions over the N models. That is, considering any neighboring datasets D and D′ , the output probabilities of RS are D PRS =
N X
πi PiD ,
PiD = Law(Mi (D))
′
′ QD i = Law(Mi (D ))
Priacy/Utility Tradeoff under Random Selection. For a target (ε′ , δ ′ ), The accounting methods above provide a feasible set of π ∈ ∆N −1 . In practice, one would naturally like to choose π that yields a strong utility among all feasible π’s. This calls for selection rules over π. Under random selection, the expected utility is linear in π, making the tradeoff easier to reason about. In typical DP scenarios, more private models tend to have lower utilities, so a natural strategy is to choose π that nearly saturates the privacy budget, e.g., ε(π; δ ′ ) ≈ ε′ in RDP, thereby biasing selection towards higher-utility models while maintaining the privacy guarantee. Moreover, many selection rules are possible in practice. For example, one may evaluate candidate mixtures on a public dataset and choose the best-performing option.
i=1 ′
QD RS =
N X
′
πi QD i ,
i=1
where Law(X) refers to the distribution induced by random variable X. Further, we define Pi and Qi are pes′ simistic estimates of PiD and QD respectively, which i ′ ′ D means Hε (PiD , QD ) ≤ H (P , Q ) and Hε (QD ε i i i i , Pi ) ≤ Hε (Qi , Pi ). Note that the hockey-stick divergence used by PLD accounting Hε (·, ·) (Eq. (2)) is jointly convex over (P, Q). Then we have following result about the PLD parameter δ RS (ε) of the random selection output. Theorem 5.2. For any ε≥ 0 and π=(π1 , . . . , πN ) ∈ ∆N −1 , it holds that ′
D sup Hε (PRS , QD RS ) ≤
D∼D ′
N X
6. Privacy of Linear Combination In Section 4.1, we leverage the additivity of independent Gaussian noise and show that, for mean estimation with Gaussian mechanism, LC strictly dominates RS. However, this favorable structure does not hold for general problems. For random selection, the only assumption we make is access to the individual RDP/PLD parameters of each input model. In contrast, we show in this section that this is not sufficient for linear combination. That is, if we only know these privacy parameters and impose no further assumptions, then the privacy under LC cannot improve upon
πi Hε (Pi , Qi )
i=1
and symmetrically, ′
D sup Hε (QD RS , PRS ) ≤
D∼D ′
N X
πi Hε (Qi , Pi ).
i=1
5
Differentially Private Model Merging
that of simply releasing all the models {θ1 , . . . , θN } jointly. This observation (formalized in Section 6.1 below) motivates the need for additional structural assumptions to obtain meaningful privacy accounting for LC (Section 6.2).
6.2. Linear Combination under DP-SGD In this section, we assume the input models are trained via DP-SGD (Abadi et al., 2016), one of the most popular DP algorithms in ML.
6.1. Limitation Result without Knowing Original Training Algorithms
Per-Step Update. At step t = 1, . . . , T , each mechanism i ∈ [N ] forms a mini-batch by subsampling from the dataset (t) (t) mini-batch size with sampling ratio qi (i.e., qi = fixed total sample amount ). Let
Suppose we only know the final RDP or PLD privacy parameters of each private learning mechanism {Mi }N i=1 without any further algorithmic structure information (i.e., the exact updating rules) about {Mi }N i=1 . We show below, when the mechanisms are instantiated with fresh independent randomness conditioned on the dataset D, the LC mechanism admits a universal worst-case upper bound, and this bound can be achieved.
(t)
zi ∈ {0, 1} be the indicator of whether the differing record between neighboring datasets is included in the mini-batch of mechanism i at step t. Then for any subset J ⊆ [N ], the (t) (t) event { zi = 1 ∀i ∈ J, zi = 0 ∀i ∈ / J } occurs with probability Y (t) Y (t) (t) ρJ := qi 1 − qi .
Theorem 6.1 (Worst-case bounds and tightness). Consider the linear combination mechanism defined by θ(D) = PN i=1 λi θi (D). Assume the mechanisms are instantiated with fresh independent randomness conditional on the dataset D. We have the following results.
i∈J
(t) (t) (t) We compute the clipped gradient g̃i = clip gi , Ci (t) (t) (t) such that ∥g̃i ∥2 ≤ Ci , and add Gaussian noise ei ∼ 2 (t) (t) N 0, σi Ci I , independently across i. The local update is (t) (t−1) (t) (t) (t) θi = θi − ηi g̃i + ei .
(1) RDP upper bound. The RDP parameter of θ is no worse than that of the joint release (i.e., releasing {θ1 , · · · , θN }). Thus, for every α > 1, the LC mechanism satisfies (α, εLC α (λ))-RDP where εLC α (λ) ≤
N X
εα,i .
Define the model output via LC after step t as θ(t) = PN (t) i=1 λi θi . The combined update can be written as
(7)
θ
(t)
−θ
(t−1)
= −
i=1
N X
(t)
λ i ηi
(t)
(t)
g̃i +ei
(t) (t) := − g λ +eλ ,
i=1
(2) PLD upper bound. Let ωi be the PLD of θi , and let ωjoint = ω1 ⋆ · · · ⋆ ωN be the PLD of the joint release. Then the PLD parameter of θ is no worse than that of the joint release. That is, for any ε ≥ 0, δ LC (ε) ≤ δjoint (ε),
i∈J /
PN (t) (t) (t) (t) (t) (t) where g λ := i=1 λi ηi g̃i and eλ := i=1 λi ηi ei . (t) Note that the aggregated noise eλ follows the distribution PN (t) 2 (t) 2 (t) (t) (t) 2 N 0, (sλ ) I , where (sλ ) := i=1 λi ηi σi Ci . Define the clipping-weighted mixing coefficients X (t) (t) (t) (t) (t) wi := λi ηi Ci , i ∈ [N ], ∆J := wi , PN
(8)
where δjoint (ε) is computed from ωjoint . (3) Tightness. The bounds in Eq. (7)-(8) are worst-case tight: there exist mechanisms {Mi }N i=1 under which the equality holds.
i∈J
and let Ft−1 denote the sigma field generated by all randomness of all models up to step t − 1. Then we have following results for accounting. Theorem 6.2. For any an integer order α ≥ 2, the step-t mechanism satisfies the following RDP bound conditional on Ft−1 : X Y (t) γJ 1 α! . Q ε(t) log B(γ) ρJ α (λ) ≤ α−1 J γJ !
Theorem 6.1 (proved in Appendix E) establishes that the privacy parameter of the deterministic linear combination is fully controlled by that of the joint model, without additional assumptions. Moreover, the bound is worst-case tight; so LC satisfies no better privacy guarantee gain beyond the joint release {θ1 , · · · , θN }. Therefore, without additional information beyond the input models’ privacy parameters, one cannot derive a universally tighter privacy guarantee for LC. In particular, the resulting joint-release bounds are substantially larger than the RS bounds in Theorems 5.1 and 5.2, which are always upper-bounded by the maximum RDP/PLD parameter among all input models. This highlights that, without further structure, LC is not guaranteed to outperform RS. Next we impose additional structures on the learning procedure that generates private input models.
γ∈Nα
J
(9) Here summation and product over J P means over J ∈ J = {J | J ⊆ [N ]}, Nα = {(γJ )J∈J | J∈J γJ = α, γJ ≥ ˜ (t) = ∆(t) /s(t) and 0, γJ ∈ Z}, ∆ J J λ ! X 2 X 2 (t) (t) 2 ˜ ˜ B(γ) = exp γJ ∆ − γJ ∆ . J
J
6
J
J
Differentially Private Model Merging
Algorithm 3 LC with RDP accounting ′
Algorithm 4 LC with PLD accounting
′
1: Input: Target privacy (ε′ , δ ′ ), hyperparameter sets of
1: Input: Target privacy (ε , δ ), orders grid A, hyperpaN rameter sets of {Mi }N i=1 : {Si }i=1 , total step T . N −1
N {Mi }N i=1 : {Si }i=1 , total step T . 2: Output: Set of λ ∈ ∆N −1 satisfying target privacy 3: function DP Delta(λ, ε) 4: for t = 1 to T do Compute the per-step privacy-loss random variable 5: L̃(t) via Eq. (11) 6: Discretize L̃(t) on grid to obtain its PLD ω (t) 7: Compose the T steps via convolution ω ← ω (1) ∗ ω (2) ∗ · · · ∗ ω (T ) 8: Compute the induced privacy parameter δ LC (ε) from the composed PLD ω. 9: return δ LC (ε) 10: return {π | DP Delta(π, ε′ ) ≤ δ ′ }
2: Output: Set of λ ∈ ∆ satisfying target privacy 3: function DP Eps(λ, δ) 4: for α ∈ A do 5: for t = 1 to T do (t) Compute the per-step RDP parameter εα (λ) 6:
via (9). PT
(t)
7: εLC α (λ) ← t=1 εα (λ) 8: εα (λ; δ) ← εLC α (λ) + log(1/δ)/(α − 1) 9: return: minα∈A εα (π; δ ′ ) 10: return {π | DP Eps(λ, δ ′ ) ≤ ε′ }
In practice, we apply Theorem 6.2 by summing the per-step privacy costs over all T iterations and then converting the resulting RDP parameters into DP guarantees. We summarize the accounting procedures in Algorithm 3.
Then, for every ε ≥ 0, we have Hε (P (t) , Q(t) ) = E[(eL
|Nα | =
N
L :=
α+2 −1 . 2N − 1
L(t) ,
L̃ :=
T X
L̃(t) .
t=1
Lemma 6.3 characterizes the exact per-step privacy loss random variable for the linear combination mechanism. Building on this representation, Theorem 6.4 introduces a tractable surrogate per-step privacy-loss random variable and shows that it upper bounds the corresponding hockeystick divergences in both directions. Combined with Corollary 6.5, this provides a practical composition rule. The PLD of the full mechanism can be upper bounded by convolving the surrogate PLDs across steps. We summarize the resulting PLD accounting procedure in Algorithm 4.
where Y (t) ∼ Q(t) . vJ is the mean shift between D and D′ conditioned on J = {i : zi = 1}. ϕ(·; µ, Σ) denotes gaussian density with mean µ and covariance Σ.
Different Total Steps Across Input Models. In some applications, the input candidate models may be trained with diffeerential privacy for different numbers of iterations {Ti }N i=1 . To make the accounting go through, we can align all runs to a common iteration T ≜ maxi Ti . For any model i with Ti < T , we could use an equivalent T -step representation by appending T − Ti virtual steps.
Theorem 6.4. Under the notation of Lemma 6.3, consider the practical surrogate privacy loss random variable
L̃(t) = log
(t)
h h i i Then, for every ε ≥ 0, E eL − eε + ≤ E eL̃ − eε + h h i i and E 1 − eε+L + ≤ E 1 − eε+L̃ + hold. Consequently, the PLD of the composed mechanism can be upper bounded by the convolution of the per-step surrogate PLDs.
(t) (t) 2 (t) (t) ρ ϕ Y ; v , (s ) I J J J⊆[N ] λ , (10) (t) 2 (t) ϕ Y ; 0, (sλ ) I
(t) (t) Z (t) ; ∆J , (sλ )2 , (t) ϕ Z (t) ; 0, (sλ )2
T X t=1
P
(t) J⊆[N ] ρJ ϕ
− eε )+ ],
Corollary 6.5 (Composition via surrogate privacy loss random variables). Under the notation of Lemma 6.3 and Theorem 6.4, define
Lemma 6.3. Let P (t) and Q(t) denote the distribution of θ(t) − θ(t−1) under D and D′ conditional on Ft−1 . Then the privacy loss random variable L(t) satisfies
P
(t)
Hε (Q(t) , P (t) ) = E[(1 − eε+L )+ ] ≤ E[(1 − eε+L̃ )+ ].
Thus, the computation is exponential in N but independent of the model size. In practice, N is typically small and such computation is lightweight (e.g., not involving any (t) forward or backward passes); so computing εα (λ) remains tractable, though it is more complex than RS. Moreover, for PLD accounting, we have following results.
L(t) = log
− eε )+ ] ≤ E[(eL̃ (t)
The right-hand side of Eq. (9) depends on the number of input models N and the RDP order α, but not on the model size. The sum is taken over γ ∈ Nα , i.e., over all nonnegative integer vectors (γJ )J⊆[N ] that sum to α. Since |J | = 2N , the number of such γ is the number of compositions of α into 2N nonnegative parts:
(t)
Utility/Privacy Tradeoffs. While LC does not enjoy the same clean utility/privacy tradeoff structure as RS in general,
(11)
7
Differentially Private Model Merging
especially for nonconvex models, many practical selection rules remain applicable. In particular, LC can still be tuned effectively by evaluating performance on a public benchmark or a non-sensitive validation set.
parameters of each model. In contrast, assuming access to RDP and PLD parameters typically yields tighter accounting. Hence, the joint-release bounds in Theorem 6.1 (the right-hand sides of Eq (7) and Eq. (8)) using RDP/PLD parameters are in general tighter than (ε, δ)-only composition bounds. Besides, beyond simply assuming access to RDP and PLD parameter, our analysis makes explicit how RS and LC interact with the underlying privacy accounting. RS exploits mixture structure through log-sum-exp and convexity, while LC admits tight bounds when additional algorithmic structure is available. This highlights why our bounds can improve over general joint-release accounting. Theorem 6.1 also implies that our LC RDP/PLD accounting gives a tighter result than the joint-release RDP/PLD bound; and RS can also be tighter. Overall, when richer privacy profiles (e.g., RDP parameters across orders) are available, our accounting procedures provide stronger guarantees. Formally, we present Proposition 7.1 below, which establishes our argument for the case of N independent and identical Gaussian mechanisms.
6.3. On Recycling Checkpoints Recent work such as Shejwalkar et al. (2022); Indri et al. (2023) considers improving private learning by recycling checkpoints from a single DP-SGD run. This setting differs fundamentally from ours in that the input models are not independent (since they share the early optimization steps). This distinction matters for privacy accounting. Our RS procedure depends only on the individual privacy profiles (RDP/PLD) of each candidate model and does not require independence between candidates; therefore RS remains directly applicable to checkpoint recycling and can guarantee effectively privacy/utility tradeoffs (see Appendix H.3 for empirical results). In contrast, our LC analysis relies on additional structure (in particular, independent noise) to obtain tighter bounds; when the inputs are correlated checkpoints, these assumptions are not satisfied, and our LC guarantees do not apply to checkpoint recycling.
Proposition 7.1. Consider releasing N models on the same dataset, where each release follows the same Gaussian mechanism (e.g., mean estimation with sensitivity ∆ and noise Z ∼ N (0, σ 2 )). Fix δ ∈ (0, 12 ). By RDP accounting, each model satisfies (ε, δ)-DP. Composing the N releases using the (ε, δ) advanced composition bound (Dwork et al., 2010, Theorem III.3) with δ ′ = N δ + δ0 yields a composed privacy parameter εcom . Using the joint RDP bound (RHS of Eq. (7)) in Theorem 6.1 yields a guarantee (εRDP , δ ′ ). We have that εRDP ≤ εcom .
More broadly, the limitation of applying LC to recycled checkpoints is intuitive: under DP-SGD and standard privacy accounting, it cannot yield a privacy guarantee better than the least private checkpoint (typically the checkpoint taken at the largest training step). To see why, consider two checkpoints θ1 and θ2 taken from the same DP-SGD run at steps t1 < t2 . A linear merge can be written as θ = λθ1 + (1 − λ)θ2 = θ1 + (1 − λ)(θ2 − θ1 ).
We provide the complete proof in Appendix G.
Since θ2 − θ1 is exactly the cumulative update from step t1 to t2 , this merge is essentially equivalent to re-scaling the updates on the segment t ∈ {t1 +1, . . . , t2 } by a factor (1−λ). However, standard DP accounting for DP-SGD is driven by the sampling rate, clipping bound, noise multiplier, and number of steps, and is typically independent of the learning rate. Therefore, such a post-processing does not reduce the privacy cost attributed to the steps up to t2 , and the resulting guarantee cannot be tighter than that of the checkpoint θ2 itself. In other words, while checkpoint recycling can improve utilities, linear combination over correlated checkpoints is not able to achieve tighter privacy relative to the least private model, without additional assumptions.
8. Empirical Evaluation In this section, we first present results on a toy mean estimation problem for RS and LC algorithms under both RDP and PLD accounting, corresponding to analysis in Section 4.1. Then on real world datasets with both convex and non-convex models, we present the privacy/utility tradeoffs of a set of models output by RS and LC, and demonstrate tighter privacy bounds than baseline composition methods. Additional experiment details are discussed in Appendix H. 8.1. Synthetic Data: Mean Estimation i.i.d.
We generate X1 , . . . , Xn ∼ N (0, 1) with n = 100, and then clip the samples to enforce a bounded domain, i.e., Xj ← clip(Xj , −1, 1). The goal is to estimate the population mean µ for dataset D = {X1 , . . . , Xn }. We generate two private estimates as input. Figure 1 report the Pareto frontier between losses (mean squared error) and privacy budgets of the RS and LC algorithms under RDP and PLD accounting. PLD gives tighter privacy upper bounds than
7. Compare with Other Composition Methods Extensive prior literature has studied DP composition of jointly releasing multiple models (e.g., Dwork et al., 2010; Kairouz et al., 2015). Among them, Dwork et al. (2010) is one of the seminal works, and Kairouz et al. (2015) further improves the bounds. However, these results are stated purely using the privacy information in the form of (εi , δi ) 8
Differentially Private Model Merging
(a) RS with RDP
(b) RS with PLD
(c) LC with RDP
(d) LC with PLD
Figure 1. Privacy/utility tradeoffs of mean estimation (δ = 10−5 ). Input models are also marked in the figure.
RDP. Also, both methods achieve flexible privacy by tracing out a continuous MSE/privacy tradeoff as the target privacy level changes. Moreover, LC consistently outperforms RS, validating our theoretical arguments in Section 4.1.
Figure 2. Heatmap of the privacy parameter ε on MNIST (δ = 10−5 ) as the merging weights vary when combining three models. 0.915 0.910
We next evaluate our method on two standard benchmarks: MNIST and CIFAR-10, and train both convex and nonconvex models from scratch. MNIST consists of 70,000 grayscale images of handwritten digits from 10 classes (LeCun et al., 2002). Following the standard split, we use 60,000 examples for training and 10,000 for testing. We train a logistic regression model with DP-SGD. CIFAR-10 contains 60,000 natural RGB images from 10 classes, with 32 × 32 resolution and three channels (Krizhevsky et al., 2009). We use the standard training/test image split with a ResNet18 model (batch normalization layers replaced with group normalization). All DP-SGD hyperparameters and implementation details are deferred to Appendix H.
0.905
Accuracy
8.2. Results on Real Datasets
0.900 0.895
RS under RDP RS under PLD LC under RDP LC under PLD Base Models(RDP) Base Models(PLD)
0.890 0.885 0
2
4
6
Privacy budget
8
10
Figure 3. Privacy/utility tradeoffs on MNIST (δ = 10−5 )
set into two disjoint halves, Dpre and Dpriv . We first train a non-private model on Dpre using standard SGD, and then use this model as initialization for DP-SGD on Dpriv . From this initialization, we train multiple private models with different DP-SGD hyperparameters, yielding different privacy/utility tradeoffs. We then apply RS and LC to these private models the same way as in other experiments. Note that the privacy guarantee in this experiment is with respect to Dpriv only, since Dpre is disjoint from the private training subset and considered non-private.
Figure 2 reports the privacy changes as different mixing weight changes under both RS and LC with RDP and PLD. Both methods successfully adapt to flexible privacy requirements. Figure 3 shows the pareto frontier of RS and LC with RDP and PLD. All methods exhibit a clear accuracy/privacy tradeoff. Across all settings, the ε values guaranteed by PLD are consistently smaller than those obtained from RDP. Figure 4 shows the Pareto frontiers (tradeoffs between utilities and privacy budgets) of RS and LC under both RDPand PLD-based accounting. We observe that LC performs well only when one model receives a very large weight; consequently, the middle portion of the frontier is sparse. This behavior highlights the challenges of nonconvex models, and also illustrates the stronger adaptability of RS.
Figure 5 shows the Pareto frontiers of RS and LC under both RDP- and PLD-based accounting. We observe that the same qualitative conclusions continue to hold in the pretraining-based setting. Both RS and LC enable flexible adaptation to different target privacy budgets without additional training, while PLD-based accounting remains consistently tighter than RDP-based accounting. Compared with training from scratch, pretraining improves the overall utility level, while the relative behavior of the merging
Starting from a Pretrained Model. To study a more practical training pipeline, we additionally consider a pretrainingbased setup on CIFAR-10. We randomly split the training 9
Differentially Private Model Merging
tion, without any additional training steps. We provide principled privacy accounting based on both RDP and PLD, and our experiments demonstrate the practical accuracy/privacy tradeoffs of the proposed methods across synthetic and real datasets and models. Several directions remain open. It would be interesting to design and analyze more sophisticated merging rules that better handle challenging regimes such as nonconvex models. On the practical side, an important next step is to develop effective and private procedures for tuning merging parameters (e.g., selecting λ and π) under privacy constraints. Figure 4. Privacy/utility tradeoffs of CIFAR-10 (δ = 10−5 ).
References Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308–318, 2016.
methods remains broadly similar. Interestingly, in this pretraining-based setting, we also observe a phenomenon that was already present in some of our earlier experiments: the merged model may outperform all individual candidate models. This effect is particularly visible with pretraining, which may be because a stronger common initialization places the candidate models in a more compatible region of the parameter space, making merging more effective at preserving shared useful structure while averaging out part of the DP-induced noise. Similar observations have also appeared in the non-private model merging literature (Wortsman et al., 2022; Matena & Raffel, 2022). This further highlights the value of the our framework: model merging is not only a tool for adapting to different target privacy budgets after training, but may also provide utility gains relative to the the input models.
Abowd, J. M., Ashmead, R., Cumings-Menon, R., Garfinkel, S., Heineck, M., Heiss, C., Johns, R., Kifer, D., Leclerc, P., Machanavajjhala, A., et al. The 2020 census disclosure avoidance system topdown algorithm. Harvard Data Science Review, 2, 2022. Dong, J., Roth, A., and Su, W. J. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022. Doroshenko, V., Ghazi, B., Kamath, P., Kumar, R., and Manurangsi, P. Connect the dots: Tighter discrete approximations of privacy loss distributions. arXiv preprint arXiv:2207.04380, 2022.
0.8700
Dwork, C. Differential privacy. In International colloquium on automata, languages, and programming, pp. 1–12. Springer, 2006.
Accuracy
0.8695
Dwork, C., Rothblum, G. N., and Vadhan, S. Boosting and differential privacy. In 2010 IEEE 51st annual symposium on foundations of computer science, pp. 51–60. IEEE, 2010.
0.8690
RS under RDP RS under PLD LC under RDP LC under PLD Base Models(RDP) Base Models(PLD)
0.8685
0.8680 7.5
10.0
12.5
15.0
17.5
Privacy budget
20.0
22.5
Gopi, S., Lee, Y. T., and Wutschitz, L. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34:11631–11642, 2021.
25.0
Figure 5. Privacy/utility tradeoffs of CIFAR-10 starting from a pretrained model (δ = 10−5 ).
9. Conclusion and Future Directions
Ilharco, G., Ribeiro, M. T., Wortsman, M., Gururangan, S., Schmidt, L., Hajishirzi, H., and Farhadi, A. Editing models with task arithmetic. arXiv preprint arXiv:2212.04089, 2022.
To the best of our knowledge, this is the first work that studies model merging to meet flexible privacy requirements during deployment time. We have proposed two merging strategies, based on random selection and linear combina-
Indri, P., Drucks, T., and Gärtner, T. Can stochastic weight averaging improve generalization in private learning? In ICLR 2023 Workshop on Trustworthy and Reliable LargeScale Machine Learning Models, 2023. 10
Differentially Private Model Merging
Izmailov, P., Podoprikhin, D., Garipov, T., Vetrov, D., and Wilson, A. G. Averaging weights leads to wider optima and better generalization. arXiv preprint arXiv:1803.05407, 2018.
Sommer, D., Meiser, S., and Mohammadi, E. Privacy loss classes: The central limit theorem in differential privacy. Cryptology ePrint Archive, 2018. Wang, Y.-X., Balle, B., and Kasiviswanathan, S. P. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd international conference on artificial intelligence and statistics, pp. 1226–1235. PMLR, 2019.
Jin, X., Ren, X., Preotiuc-Pietro, D., and Cheng, P. Dataless knowledge fusion by merging weights of language models. arXiv preprint arXiv:2212.09849, 2022. Kairouz, P., Oh, S., and Viswanath, P. The composition theorem for differential privacy. In International conference on machine learning, pp. 1376–1385. PMLR, 2015.
Wortsman, M., Ilharco, G., Gadre, S. Y., Roelofs, R., Gontijo-Lopes, R., Morcos, A. S., Namkoong, H., Farhadi, A., Carmon, Y., Kornblith, S., et al. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In International conference on machine learning, pp. 23965– 23998. PMLR, 2022.
Koskela, A., Jälkö, J., Prediger, L., and Honkela, A. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference on Artificial Intelligence and Statistics, pp. 3358–3366. PMLR, 2021.
Yadav, P., Tam, D., Choshen, L., Raffel, C. A., and Bansal, M. Ties-merging: Resolving interference when merging models. Advances in Neural Information Processing Systems, 36:7093–7115, 2023.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009. LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradientbased learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 2002.
Yang, E., Wang, Z., Shen, L., Liu, S., Guo, G., Wang, X., and Tao, D. Adamerging: Adaptive model merging for multi-task learning. arXiv preprint arXiv:2310.02575, 2023.
Matena, M. S. and Raffel, C. A. Merging models with fisherweighted averaging. Advances in Neural Information Processing Systems, 35:17703–17716, 2022.
Yang, E., Shen, L., Guo, G., Wang, X., Cao, X., Zhang, J., and Tao, D. Model merging in llms, mllms, and beyond: Methods, theories, applications and opportunities. arXiv preprint arXiv:2408.07666, 2024.
Meiser, S. and Mohammadi, E. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 247–264, 2018.
Yousefpour, A., Shilov, I., Sablayrolles, A., Testuggine, D., Prasad, K., Malek, M., Nguyen, J., Ghosh, S., Bharadwaj, A., Zhao, J., et al. Opacus: User-friendly differential privacy library in pytorch. arXiv preprint arXiv:2109.12298, 2021.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263– 275. IEEE, 2017a.
Yu, L., Yu, B., Yu, H., Huang, F., and Li, Y. Language models are super mario: Absorbing abilities from homologous models as a free lunch. In Forty-first International Conference on Machine Learning, 2024.
Mironov, I. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pp. 263– 275. IEEE, 2017b. Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C., McMahan, H. B., Vassilvitskii, S., Chien, S., and Thakurta, A. G. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113–1201, 2023. Puccetti, G. and Wang, R. Extremal dependence concepts. 2015. Shejwalkar, V., Ganesh, A., Mathews, R., Mu, Y., Song, S., Thakkar, O., Thakurta, A., and Zheng, X. Recycling scraps: Improving private learning by leveraging intermediate checkpoints. arXiv preprint arXiv:2210.01864, 2022. 11
Differentially Private Model Merging
A. Proof of Proposition 3.1 Proof. Consider following counterexample: θ1 (D) ≡ C with probability 1 and then h(θ1 , θ2 ) can be reduce to a function d
h̃(θ2 ) that only depends on θ2 . Since h is nontrival, there at least are two points {a, b} s.t h̃(a) ̸= h̃(b). Therefore there is at least one S ⊆ RP , such that P(h̃(a) ∈ S) > P(h̃(b) ∈ S) Consider P(θ2 (D) = a) = p, P(θ2 (D)) = 1 − p, and P(θ2 (D′ ) = a) = p′ , P(θ2 (D)) = 1 − p′ such that p = eε2 p′ + δ = 1 ⇒ p′ = e−ε2 (1 − δ) then P(h̃(θ2 (D)) ∈ S) = pP(h̃(a) ∈ S) + (1 − p)P(h̃(b) ∈ S) ′
= eε2 p′ P(h̃(a) ∈ S) + δP(h̃(a) ∈ S) + eε (1 − p′ )P(h̃(b) ∈ S) ′
′
− (eε − 1 + (eε2 − eε )p′ + δ)P(h̃(b) ∈ S) ′
′
> eε P(h̃(θ2 (D′ )) ∈ S) + ((eε2 − eε )p′ + δ)P(h̃(a) ∈ S) ′
′
− (eε − 1 + (eε2 − eε )p′ + δ)P(h̃(b) ∈ S) ′
′
= eε P(h̃(θ2 (D′ )) ∈ S) + (1 − eε −ε2 (1 − δ))(P(h̃(a) ∈ S) − P(h̃(b) ∈ S)) ′
− (eε − 1)P(h̃(b) ∈ S) The last equality is gained by bringing p′ = e−ε2 (1 − δ) into the equation. −ε′ ′
−ε′
, we know If DT V (h̃(a), h̃(b)) > e1−eδ−ε+1−e 2 (1−δ) ′
′
sup(1 − eε −ε2 (1 − δ))(P(h̃(a) ∈ S) − P(h̃(b) ∈ S)) − (eε − 1)P(h̃(b) ∈ S) S ′
′
≥ (1 − eε −ε2 (1 − δ))DT V (h̃(a), h̃(b)) − (eε − 1)(1 − DT V (h̃(a), h̃(b))) > δ′ and thus there exists S such that ′
P(h̃(θ2 (D)) ∈ S) > eε P(h̃(θ2 (D′ )) ∈ S) + δ ′ . We finish the proof.
B. Proof of Lemma 4.1 and Theorem 4.2 Proof of Lemma 4.1. Since under linear combination with parameter λ, the output θ(D) ∼ N (µ̂, λ2 σ12 + (1 − λ)2 σ22 ) and 2 σLC (λ) = λ2 σ12 + (1 − λ)2 σ22 . Thus α∆2 εLC α = 2 (λ) . 2σLC Next we prove εRS α = Dα Pπ ∥Qπ ≥
α∆2 2 2 (π) + o(∆ ). 2σRS
Write p for the density of Pπ and note that Qπ ’s density q(x) = p(x − ∆). Define (p′ (x))2 dx. p(x) R
Z Jχ (P ) := Step 1. We show that Dα (Pπ ∥Qπ ) ≥
α Jχ (Pπ ) ∆2 + o(∆2 ). 2 12
(12)
Differentially Private Model Merging
R α Consider p(x − ∆) 1−α dx, so that Dα (Pπ ∥Qπ ) = Ψα (∆)/(α − 1). Differentiate over ∆ and note R ′ Ψα (∆) := log p(x) ′ that p dx = 0, we know Ψα (0) = 0 and Ψ′′α (0) = α(α − 1) Jχ (P ), which yields (12). Step 2. Let random variable X ∼ Pπ , we next show 1 . Var(X)
Jχ (Pπ ) ≥
(13)
Let s(x) = p′ (x)/p(x) be the score. For any smooth h, integration by parts gives E[h′ (X)] = −E[h(X)s(X)]. By 2 2 2 2 Cauchy-Schwarz, (E[h′ (X)]) over h shows Jχ (P ) ≥ ≤ E[h(X) ] E[s(X) ] = E[h(X) ] Jχ′(P ). Taking the supremum ′ 2 2 suph E[h (X)] /E[h(X) ] . Choosing h(x) = x − E[X] yields E[h (X)] = 1 and E[h(X)2 ] = Var(X), proving (13). Note that when π ∈ (0, 1), Pπ is mixed gaussian distribution, thus the bound could not be reached and thus cπ > 0. Combining step 1 and step 2 we finish the proof.
C. Proof of Theorem 5.1 Lemma C.1. For any α > 1, π ∈ ∆N −1 , and ai , bi ≥ 0 (i = 1, 2, . . . , N ), N X
πi ai
N α X
i=1
π i bi
1−α
≤
i=1
N X
1−α πi aα . i bi
i=1 (1−α)/α
α−1/α
, vi = b i . By Hölder’s Proof of C.1. Let the conjugate exponents be (r, s) = (α, α/(α − 1)). Let ui = ai bi inequality, we have X 1/r X 1/s X 1/α X (α−1)/α X X 1−α πi ai = πi ui vi ≤ πi uri πi vis = πi a α πi bi . i bi i
i
i
i
i
i
Raising both sides to the power α and we finish the proof. Proof of (6). Let Pi = Law(Mi (D)) and Qi = Law(Mi (D′ )) be the output distribution of the two DP mechanisms on neighboring datasets D ∼ D′ . Let N N X X Pmix = π i Pi , Qmix = πi Qi , i=1
be distributions with densities pmix = e
i=1
PN
i=1 πi pi and qmix =
(α−1)Dα (Pmix ∥Qmix )
Z =
PN
i=1 πi qi . By the definition,
1−α pα mix qmix dx =
Z X N
πi p i
N α X
i=1
πi q i
1−α dx.
i=1
Applying Lemma C.1, we know 1−α pα mix (x) qmix (x) ≤
N X
1−α πi p α (x). i (x) qi
i=1
Thus, e(α−1)Dα (Pmix ∥Qmix ) ≤
N X
Z πi
1−α pα = i qi
i=1
N X
πi e(α−1)Dα (Pi ∥Qi ) .
i=1
Thus, Dα (Pmix ∥Qmix ) ≤
N X 1 log πi e(α−1)Dα (Pi ∥Qi ) . α−1 i=1
Since εα,i = supD∼D′ Dα (Pi ∥Qi ), we obtain εRS α (λ) ≤
N X 1 log πi e(α−1)εα,i , α−1 i=1
We finish the proof. 13
∀α > 1.
Differentially Private Model Merging
D. Proof of Theorem 5.2 Proof of Theorem 5.2. For any ε ≥ 0, recall the hockey-stick divergence is defined as n o Hε (P, Q) = sup P (S) − eε Q(S) ,
(14)
S
Thus for any measurable S, PRS (S) − eε QRS (S) =
N X
πi Pi (S) − eε Qi (S) .
i=1
Taking supremum over S, we obtain Hε (PRS , QRS ) = sup
N X
N N X X πi Pi (A) − eε Qi (A) ≤ πi sup Pi (A) − eε Qi (A) = πi Hε (Pi , Qi ).
A i=1
i=1
A
i=1
This proves the first inequality. The second inequality follows by the same argument after swapping the roles of P and Q: Hε (QRS , PRS ) ≤
N X
πi Hε (Qi , Pi ).
i=1
Using the two bounds above for each neighboring pair D ∼ D′ , we have δ RS (ε) ≤ sup max
N nX
D∼D ′
πi Hε (Pi , Qi ),
N X
o πi Hε (Qi , Pi ) ,
i=1
i=1
We finish the proof.
E. Proof of Theorem 6.1 Proof. Fix any neighboring datasets D ∼ D′ , let P joint , Qjoint be the output distributions of the joint release Mjoint := (M1 , . . . , MN ) on D and D′ , respectively. Similarly, we define P LC , QLC be the output distributions of LC on D and D′ . Obviously, the linear-combination mechanism can be understood as a post-processing of the joint release. (1) RDP upper bound. release, we have
Since the linear-combination mechanism can be understood as a post-processing of the joint Dα (P LC ∥ QLC ) ≤ Dα (P joint ∥ Qjoint ).
(15)
Under the definition of Rényi divergence, we have Dα (P joint ∥ Qjoint ) =
N X
Dα (Pi ∥ Qi ) ≤
i=1
Combining (15)-(16) and taking the worst case over D ∼ D′ yields εLC α (λ) ≤ (2) PLD upper bound. release, we have
N X
εα,i .
(16)
i=1
PN
i=1 εα,i .
Since the linear-combination mechanism can be understood as a post-processing of the joint Hε (P LC ∥ QLC ) ≤ Hε (P joint ∥ Qjoint ).
(17)
Similarly, we have Hε (QLC , P LC ) ≤ Hε (Qjoint , P joint ). Therefore, δ LC (ε) = max{Hε (P LC , QLC ), Hε (QLC , P LC )} ≤ max{Hε (P joint , Qjoint ), Hε (Qjoint , P joint )} =: δjoint (ε). Moreover, from PLD accounting, we know the PLD of the joint release is the convolution ωjoint = ω1 ⋆ · · · ⋆ ωN , and δjoint (ε) is computed from ωjoint . 14
Differentially Private Model Merging
(3) Tightness. We show PN the bounds in (7)-(8) are worst-case tight by an explicit construction. Let p1 , . . . , pN be positive integers and set p = i=1 pi . For each i ∈ [N ], let M′i be any mechanism whose output lies in Rpi , and Mi output its Pi−1 Pi p dimensional version θi : D → Rp , where the j=1 pj + 1−th element to j=1 pj −th element is Mi′ (D) and other elements are 0. Now consider the linear-combination output θ(D) :=
N X
λi θi (D) ∈ Rp .
i=1
Intuitively, linear-combination does not lose any information from the joint release. As a result, for every neighboring pair D ∼ D′ and every α > 1, Rényi divergence is preserved. We have Dα P LC ∥ QLC = Dα Pjoint ∥ Qjoint , and likewise the hockey-stick divergence (hence the PLD profile) is also preserved: δ LC (ε) = δjoint (ε),
∀ ε ≥ 0.
Therefore the upper bounds (7)-(8) cannot be improved in general. This establishes worst-case tightness.
F. Proof of Theorem 6.2, Lemma 6.3, Theorem 6.4 and Corollary 6.5 Proof of Theorem 6.2. Fix a step t and omit the superscript (t) for simplicity. Let D, D′ be neighboring datasets. Recall for each i ∈ [N ], let zi ∈ {0, 1} indicate whether the differing record is included in mechanism i’s minibatch. By clipping, for each i, ∥λi ηi g̃i ∥2 ≤ wi . Thus, conditioning on J = {i : zi = 1}, the mean shift between D and D′ for the mixed update is a vector vJ satisfying ∥vJ ∥2 ≤ ∆J . (18) Let ϕ0 denote the density of N (0, s2 I) and ϕJ denote the density of N (vJ , s2 I). WLOG, using translation invariance, we may represent the step-t output distributions as X p(x) = ρJ ϕJ (x), q(x) = ϕ0 (x), J⊆[N ]
where p and q is the density of the step-t mechanism under D and D′ . Define the corresponding distributions are P, Q For an integer α ≥ 2, the Rényi divergence is Z Z X α 1 1 α 1−α Dα (P ∥Q) = log p(x) q(x) dx = log ρJ ϕJ (x) ϕ0 (x)1−α dx. α−1 α−1 J
Since X J
α X γJ α! Y Q ρJ ϕJ (x) . ρJ ϕJ (x) = γ ! J J γ∈Nα
J
and all terms are nonnegative, we could exchange sum and integral to get Z X α! Y γJ Q p(x)α q(x)1−α dx = ρJ I(γ), J γJ ! γ∈Nα
where I(γ) :=
Z Y
J
ϕJ (x)γJ ϕ0 (x)1−α dx.
J
Since ϕJ (x) = ϕ0 (x) exp ⟨x, vJ ⟩/s2 − ∥vJ ∥22 /(2s2 ) . Then P D P Y γ J vJ E γJ ∥vJ ∥22 ϕJ (x)γJ ϕ0 (x)1−α = ϕ0 (x) exp x, J 2 − J 2 . s 2s J
15
(19)
Differentially Private Model Merging
Using the Gaussian mgf regard to X ∼ N (0, s2 I), we have 2
P
J γJ v J 2 − 2s2
I(γ) = exp
2 J γJ ∥vJ ∥2
P
! .
(20)
Using (18) and the triangle inequality, X
γ J vJ
J
≤ 2
X
γJ ∥vJ ∥2 ≤
X
J
γ J ∆J
J
and note that γJ2 ∥vJ ∥22 ≥ γJ ∥vJ ∥22 . Thus X
γJ ∥vJ ∥2
2
−
X
J
γJ ∥vJ ∥22
J
is a increasing function of ∥vJ ∥2 . Thus, P I(γ) ≤ exp
J γJ ∥vJ ∥2
2
−
2 J γJ ∥vJ ∥2
P
!
P ≤ exp
2s2
J γ J ∆J
2
−
2s2
2 J γ J ∆J
P
! .
˜ J = ∆J /s in the inequality, we know Bringing ∆ ˜
P I(γ) ≤ B(γ) = exp
J γJ ∆ J
2
− 2
P
˜
J γJ (∆J )
2
! .
Substituting this bound into (19) gives Z X Y γ α! Q p(x)α q(x)1−α dx ≤ B(γ) ρJJ . γ ! J J γ∈Nα
J
Therefore, X Y γ α! 1 Q log Dα (P ∥Q) ≤ B(γ) ρJJ , α−1 J γJ ! γ∈Nα
J
Taking the worst case over D ∼ D′ yields the result. We finish the proof. Proof of Lemma 6.3. Fix a step t and omit the superscript (t) for simplicity and use s represent sλ . Let D, D′ be neighboring datasets. Recall the definition of the privacy loss random variable L := log
dP (Y ), dQ
Y ∼ Q.
(21)
WLOG, using translation invariance, we may represent the densities of P and Q as X p(x) = ρJ ϕJ (x), q(x) = ϕ0 (x), J⊆[N ]
where ϕ0 denote the density of N (0, s2 I) and ϕJ denote the density of N (vJ , s2 I) Bringing p(x) and q(x) into 21, we know P J⊆[N ] ρJ ϕJ (Y ) L(Y ) := log , Y ∼ Q. ϕ0 (Y )
16
Differentially Private Model Merging
Proof of Theorem 6.4. We use the same notation as Proof of Lemma 6.3. First we consider the surrogate for Hε (P, Q). Step 1: Rewrite the Hε (P, Q) in the terms of projections of Y . We notice that if we let ZJ = ⟨Y, ∥vvJJ∥2 ⟩ and ζJ = ∥vJ ∥2 , we have ZJ ∼ N (0, s2 ) and ϕJ (Y ) 1 1 = exp(− 2 ∥Y − vJ ∥22 + 2 ∥Y ∥22 ) ϕ0 (Y ) 2s 2s 1 1 = exp(− 2 ζJ2 + 2 ζJ ZJ ) 2s s P
By Lemma 6.3, we know exp(L(Y )) =
J⊆[N ] ρJ ϕJ (Y )
ϕ0 (Y )
=
1 2 1 J⊆[N ] ρJ exp(− 2s2 ζJ + s2 ζJ ZJ ), and therefore
P
X
Hϵ (P, Q) = E(exp(L(Y )) − eϵ )+ = E
ρJ exp(−
J⊆[N ]
where G((zJ )J⊆[N ] ) =
P
1 2 1 ζ + ζJ ZJ ) − eϵ = EG((ZJ )J⊆[N ] ), 2s2 J s2 +
1 2 1 ϵ J⊆[N ] ρJ exp(− 2s2 ζJ + s2 ζJ zJ ) − e
+
.
N
Step 2: G is supermodular We next prove G is supermodular on R2 N
Lemma F.1. G is supermodular on R2 . Moreover, G is coordinatewise nondecreasing. Proof. Write TJ (zJ ) = ρJ exp
ζ2 ζJ zJ − J2 2 s 2s
,
Then
ψ(x) = (x − eε )+ . !
G((zJ )J ) = ψ
X
TJ (zJ ) .
J
We first note that each TJ is nondecreasing. Since ψ is nondecreasing, it follows that G is coordinatewise nondecreasing. Next we prove that G is supermodular. Since ψ is convex and nondecreasing, it suffices toP verify that G has increasing differences. Fix J1 ̸= J2 , and let all coordinates other than (zJ1 , zJ2 ) be fixed. Define G0 = J̸=J1 ,J2 TJ (zJ ). Then G = ψ G0 + TJ1 (zJ1 ) + TJ2 (zJ2 ) . For x1 ≥ x2 and y1 ≥ y2 , since ψ is convex, we know ψ G0 + TJ1 (x1 ) + TJ2 (y1 ) − ψ G0 + TJ1 (x2 ) + TJ2 (y1 ) ≥ ψ G0 + TJ1 (x1 ) + TJ2 (y2 ) − ψ G0 + TJ1 (x2 ) + TJ2 (y2 ) , Therefore G has increasing differences in (zJ1 , zJ2 ). Since this holds for every pair J1 ̸= J2 , G is supermodular. Back to the proof, since G is supermodular, we considera standard supermodular function result: Definition F.2 ((Puccetti & Wang, 2015)). A function c : Rd → R is said to be mean-compatible with a random vector (X1 , . . . , Xd ) if there exist measurable functions bj : R → [0, ∞), j = 1, . . . , d, such that |c(x1 , . . . , xd )| ≤
d X
bj (xj ),
∀(x1 , . . . , xd ) ∈ Rd ,
j=1
and E[bj (Xj )] < ∞,
j = 1, . . . , d.
Theorem F.3 (Theorem 2.1(b)(d) in (Puccetti & Wang, 2015)). For a random vector (X1 , . . . , Xd ) with joint distribution function F , the following statements are equivalent: (a) F is given by F (x1 , . . . , xd ) = Fd∨ (x1 , . . . , xd ) := min F1 (x1 ), . . . , Fd (xd ), 17
x1 , . . . , xd ∈ R,
Differentially Private Model Merging
where Fj is the marginal distribution of Xj , j = 1, . . . , d; (b) for all supermodular functions c : Rd → R that are mean-compatible with (X1 , . . . , Xd ), we have that n o d E[c(X1 , . . . , Xd )] = sup E[c(X1′ , . . . , Xd′ )] : Xj′ = Xj , j = 1, . . . , d . In our setting, let (Z)J be (X1 , . . . , Xd ), F ((zJ )J ) = P(Z ≤ zJ , ∀J ∈ J ) = P(Z ≤ min zJ ) = min FJ (zJ ). J
J
Thus the condition (a) holds. Define bJ (z) := |ρJ | exp(−
uJ z u2J + 2 ) + eϵ , 2 2s s
z ∈ R.
Then it is easy to verify G((zJ )J ) ≤
X
bJ (zJ ),
∀(zJ )J .
J
And since Z is Gaussian, its moment generating function is finite. Therefore, E[exp( us2J Z)] < ∞. Hence E[bJ (ZJ )] < ∞. d
Thus the function G is mean-compatible with (Z)J . Thus by Theorem F.3, since ZJ = Z and G is supermodular, we know Hϵ (P, Q) = EG((ZJ )J⊆[N ] ) ≤ EG((Z)J⊆[N ] ) = E exp(L(Z)) − eϵ + , where Z ∼ N (0, s2 ) and exp(L(Z)) =
1 1 2 J⊆[N ] ρJ exp(− 2s2 ζJ + s2 ζJ Z).
P
Step 3: Monotonicity in ∥vJ ∥2 Now consider tJ (ζJ ) satisfying L(Z) ≥ eϵ ⇔ Z ≥ tJ (ζJ ) , we have Z X d d ( ρK ϕ(z; ζJ , s2 ) − eϵ ϕ(z; 0, s2 ))dz E exp(L(Z)) − eϵ + = dζJ dζJ z≥tJ (ζJ ) K⊆[N ] Z d = ρJ − ϕ(z; ζJ , s2 )dz dz z≥tJ (ζJ ) = ρJ ϕ(tJ (ζJ ); ζJ , s2 ) ≥ 0 Here we note that by definition of t, the boundary term disappears. Thus let P 2 J⊆[N ] ρJ ϕ Z; ∆J , s L̃ = log , Z ∼ N (0, s2 ), ϕ(Z; 0, s2 ) We know
Hϵ (P, Q) ≤ E exp(L(Z)) − eϵ + ≤ E exp(L̃(Z)) − eϵ . +
For the Hϵ (Q, P ) part, a similar argument applies after swapping P and Q, so the same type of bound holds for Hϵ (Q, P ). Alternatively, one may also use the identity Hϵ (Q, P ) = 1 − eϵ + eϵ H−ϵ (P, Q). This is due to Z Hϵ (Q, P ) =
ϵ
+
Z
(q − eϵ p) + (eϵ p − q)+ dµ = 1 − eϵ + eϵ H−ϵ (P, Q)
(q − e p) dµ =
Since EeL̃ =
X
Z ρJ
ϕ(z; ∆J , s2 )dz = 1,
J
18
Differentially Private Model Merging
we know E(eϵ eL̃ − 1)+ = E(eϵ eL̃ − 1) + E(1 − eϵ eL̃ )+ = eϵ − 1 + E(1 − eϵ eL̃ )+ and thus Hϵ (Q, P ) = 1 − eϵ + eϵ H−ϵ (P, Q) ≤ 1 − eϵ + E(eϵ eL̃ − 1)+ = E(1 − eϵ eL̃ )+ Hence, the reverse direction is covered as well, and it yields the similar surrogate bound. Proof of Corollary 6.5. We consider the following lemma. Lemma F.4. Let L(t) be privacy loss random variables step t (t ∈ [1 . . . T ]), conditioned on all randomness up to step t − 1, Ft−1 , and L̃(t) is surrogate. Define (t)
(t) δL̃(t) (ϵ) := E (1 − eϵ−L̃ )+ .
δL(t) (ϵ) := E[(1 − eε−L )+ ], Suppose that ∀t
δL̃(t) (ϵ) ≥ δL(t) (ϵ),
∀ε ∈ R.
Then δL̃(1) +···+L̃(T ) (ε) ≥ δL(1) +···+L(T ) (ε),
∀ε ∈ R.
Proof. For T = 2, note (1)
δL(1) +L(2) (ϵ) = E[eL E[(eL
(2)
(1)
(1)
(1)
− eϵ−L )+ ] | F1 ] = E[eL δL(2) (ϵ − L(1) )] ≤ E[eL δL̃(2) (ϵ − L(1) )] = δL(1) +L̃(2) (ϵ).
By the construction, L̃(2) only depend on randomness in step 2 and thus is independent to L(1) . So similarly, δL(1) +L̃(2) (ϵ) ≤ δL̃(1) +L̃(2) (ϵ). Thus δL(1) +L(2) (ϵ) ≤ δL̃(1) +L̃(2) (ϵ). This proves the result for T = 2. Assume now that the statement holds for T = k − 1. For T = k, let O1 = L(1) + · · · + L(k−1) ,
O2 = L(k) ,
and define O1′ , O2′ analogously. By the induction hypothesis, δO1′ (ε) ≥ δO1 (ε) for all ε. Applying the two-term result to (O1 , O2 ) and (O1′ , O2′ ) yields the claim for T = k. By induction, we finish the proof. Corollary 6.5 is a direct application of Lemma F.4. We finish the proof.
G. Proof of Proposition 7.1 Proof. WLOG, we assume ∆ σ = 1 Step 1 Per-release RDP parameter. For the Gaussian mechanism (mean estimation with ℓ2 -sensitivity ∆ and noise Z ∼ N (0, σ 2 )), the per-release Rényi DP parameter at order α > 1 is εα =
α ∆2 . 2σ 2
Step 2 Per-release (ε, δ) from RDP. Since ε = inf
α>1
We know ε=
log(1/δ) εα + α−1
∆p ∆2 + 2 log(1/δ) 2 2σ σ 19
,
Differentially Private Model Merging
Step 3 composition in (ε, δ). Applying (Dwork et al., 2010, Theorem III.3) to N releases, each satisfying (ε, δ)-DP, yields a composed guarantee (εcom , δ ′ ) with δ ′ = N δ + δ0 , and p εcom = ε 2N log(1/δ0 ) + N ε(eε − 1) . Step 4 Joint RDP accounting. By additivity of RDP under composition, we know log(1/δ ′ ) log(1/δ ′ ) N α ∆2 εRDP = inf N εα + + = inf α>1 α>1 α−1 2σ 2 α−1 Thus εRDP =
∆p N ∆2 + 2N log(1/δ ′ ). 2 2σ σ
We only need to prove p N ∆2 ∆p 2N log(1/δ ′ ) ≤ ε 2N log(1/δ0 ) + N ε(eε − 1). + 2 2σ σ Let t = ∆ σ ,s =
p
2 log(1/δ). Bringing
1 2 t + st 2 into the inequality, and use eε > 1 + ε, since eε > 1 + ε, we only need to prove ε=
p p N 2 1 1 t + t 2N log(1/δ ′ ) ≤ ( t2 + st) 2N log(1/δ0 ) + N ( t2 + st)2 2 2 2 p p Let A ≜ 2N log(1/δ0 ) and C ≜ 2N log(1/δ ′ ). Since δ ′ = N δ + δ0 ≥ δ0 , we have C ≤ A. Therefore the left-hand side is at most N2 t2 + tA, and it is enough to show 1 1 2 N 2 t + tA ≤ t2 + st A + N t2 + st . 2 2 2
(22)
Rearranging (22), the gap equals h 1 2 1 i t2 + st − t A + N t2 + st − t2 2 2 2 1 1 1 = t2 + (s − 1)t A + N t4 + st3 + (s2 − )t2 . 2 4 2 p √ Since δ ≤ 1/2, we have s = 2 log(1/δ) ≥ 2 log 2 > 1, hence both s − 1 ≥ 0 and s2 − 12 ≥ 0. Since t ≥ 0 and A ≥ 0, every term on the right-hand side is nonnegative, so the gap is ≥ 0. We finish the proof. 1
H. Experiment Details We use 42 for random seed in all experiments. H.1. MNIST Dataset and Model. We use MNIST with the standard train/test split (60,000/10,000). Images are normalized. We train a logistic regression classifier: Flatten → Linear(28×28 → 10), optimized with cross-entropy loss. We report test-set classification accuracy (and loss) after each epoch and use the final test accuracy for Pareto-frontier plots. 20
Differentially Private Model Merging
DP-SGD Implementation. We use the Opacus package (Yousefpour et al., 2021) to train with DP-SGD under Poisson sampling. The optimizer is SGD. In our experiments, we train three base models with the following hyperparameters: learning rate 0.1,
C = 1,
σ = 0.5,
T = 3 epochs;
learning rate 0.1,
C = 2,
σ = 0.5,
T = 3 epochs;
learning rate 0.1,
C = 1,
σ = 2,
T = 3 epochs.
We use N = 60,000 training samples and batch size B = 256, giving sampling rate q = B/N . The total number of optimization steps is set to total steps = T · len(train loader). H.2. CIFAR-10 Dataset and Model. We use CIFAR-10 with the standard split (50,000/10,000). We apply standard data preprocessing. We use ResNet18 with CIFAR-10 adaptations: the first convolution is replaced by a 3 × 3 stride-1 convolution and the max-pooling layer is removed. The final fully-connected layer is set to output 10 classes. We report test-set accuracy (and loss) after each epoch; the final test accuracy is used for the accuracy–privacy Pareto-frontier plots. DP-SGD Implementation. We train ResNet18 with DP-SGD using Opacus. To ensure compatibility with per-sample gradients, we (i) apply ModuleValidator.fix(model) to replace batch normalization layers (e.g., BN → GN), and (ii) disable in-place operations by setting all ReLU layers to inplace=False. We use the SGD optimizer with per-sample gradient clipping norm C and noise multiplier σ. We use batch size B = 256 and train for T = 20 epochs. We fix the randomness of data shuffling using a DataLoader generator seed of 42. We generate candidate models by sweeping the learning rate η ∈ {0.01, 0.02, 0.04} and C ∈ {1, 2, 4}. For each setting, σ is chosen so that the resulting RDP ε is below the target thresholds ( ε < 10 and ε < 9). DP-SGD from a Pretrained Model Initialization. In addition to training from scratch, we also consider a pretrainingbased setup on CIFAR-10 to better reflect practical workflows. We randomly split the original training set into two disjoint subsets of equal size, denoted by Dpre and Dpriv . We first train a non-private ResNet18 model on Dpre using standard SGD, and then use the resulting checkpoint as initialization for DP-SGD on Dpriv . All merged candidate models are produced from this common pretrained initialization. The privacy guarantee in this setting is with respect to Dpriv only, since Dpre is disjoint from the private training subset and is not included in the DP accounting. We fix the randomness of data split using a generator seed of 42. We train the pretrained model using standard SGD with batch size B = 128 and learning rate η = 0.1, and train for T = 100 epochs. Starting from the pretrained checkpoint, we fine-tune the model on Dpriv using DP-SGD in Opacus with the same implementation adjustments as above, including ModuleValidator.fix(model) and setting all ReLU layers to inplace=False. We use the SGD optimizer with per-sample gradient clipping norm C = 1, noise multiplier σ, batch size B = 256, and train for T = 3 epochs. As in the from-scratch experiments, we fix the randomness of data shuffling using a DataLoader generator seed of 42. We generate candidate models by sweeping the learning rate η ∈ {0.005, 0.01}, and σ ∈ {0.4, 0.5}. H.3. RS for Merging Checkpoints from the Same Run We also consider the checkpoint-merging setting studied in Indri et al. (2023); Shejwalkar et al. (2022), where the candidate models are checkpoints from a single DP-SGD training run and therefore are generally not independent. This distinction matters: our LC accounting relies on independence noises across the input mechanisms, whereas RS does not. Since RS only requires access to the individual privacy profiles, it remains applicable even when the inputs are correlated checkpoints. We run experiments under DP-SGD on both an MNIST and CIFAR. We follow the similar hyperparameters selection of the main experiments. We construct three candidate models by taking checkpoints at training steps T ∈ {1, 2, 3} for MNIST and at training steps T ∈ {12, 16, 20} for CIFAR-10. The results are shown in Figure 6. We observe that RS still achieves a favorable privacy/utility tradeoff in this correlated-checkpoint regime. H.4. More Experiment Results
21
Differentially Private Model Merging
0.884
0.53
0.883
0.52
Accuracy
Accuracy
0.885
0.882 0.881 0.880
0.50
RS under RDP RS under PLD Base Models(RDP) Base Models(PLD)
0.879 0.2
0.3
Privacy budget
0.4
0.51
RS under RDP RS under PLD Base Models(RDP) Base Models(PLD)
0.49 0.5
5
(a) Privacy/utility tradeoffs on MNIST within same run (δ = 10−5 )
6
7
Privacy budget
8
9
10
(b) Privacy/utility tradeoffs on CIFAR-10 within same run (δ = 10−5 )
Figure 6. Privacy/utility tradeoffs of merging checkpoints from same run.
(a) DP parameter as π changes
(b) MSE as π changes
Figure 7. Random selection results for mean estimation with δ = 10−5 .
(a) DP parameter as λ changes
(b) MSE as λ changes
Figure 8. Linear combination results for mean estimation with δ = 10−5 .
22