Differentially Private Model Merging

1. Problem Formulation

In real-world machine learning deployments, privacy requirements (e.g., $\epsilon$ and $\delta$ parameters) often change dynamically due to evolving regulations or user preferences. Retraining models from scratch for every new privacy constraint is computationally expensive and requires access to raw data, which may be restricted.

The paper addresses the following problem:
Given a set of $N$ existing models $\{\theta_1, \dots, \theta_N\}$ trained on the same dataset $D$ with different privacy/utility tradeoffs (i.e., different privacy budgets $\epsilon_i$), how can we efficiently merge them to generate a new model $\theta$ that satisfies a target privacy constraint $(\epsilon', \delta')$ without:

1. Accessing the raw data $D$.
2. Performing additional training steps.
3. Suffering a significant loss in utility compared to retraining.

The authors note that without knowledge of the training algorithms' internal structures, a "no-free-lunch" theorem (Proposition 3.1) suggests that any valid merging mechanism must essentially rely on the most private model, offering no utility gain. Therefore, the work assumes access to the privacy profiles (RDP/PLD parameters) or the specific training algorithms (e.g., DP-SGD) of the input models.

2. Methodology

The authors propose two data-independent, post-processing merging mechanisms:

A. Random Selection (RS)

• Mechanism: The algorithm randomly selects one model $\theta_i$ from the set $\{\theta_1, \dots, \theta_N\}$ based on a probability distribution $\pi = (\pi_1, \dots, \pi_N)$.
• Assumptions: Requires only the privacy profiles (RDP or PLD parameters) of the individual input models. It does not require knowledge of the internal training structure.
• Privacy Accounting:
  • RDP: The RDP parameter $\epsilon_\alpha^{RS}$ is bounded by a log-sum-exp function of the individual models' RDP parameters:
    $$\epsilon_\alpha^{RS}(\pi) \le \frac{1}{\alpha-1} \log \left( \sum_{i=1}^N \pi_i e^{(\alpha-1)\epsilon_{\alpha,i}} \right)$$
  • PLD: The privacy loss distribution (PLD) of the mixture is bounded by the convex combination of the individual PLDs.
• Utility: The expected utility is a linear function of $\pi$.

B. Linear Combination (LC)

• Mechanism: The algorithm outputs a deterministic weighted average of the models: $\theta = \sum_{i=1}^N \lambda_i \theta_i$.
• Assumptions: Requires stronger assumptions about the training process. Specifically, the paper analyzes LC under DP-SGD, assuming independent noise addition across models and known hyperparameters (learning rates, clipping norms, noise multipliers).
• Privacy Accounting:
  • Without Structural Assumptions: If only the final privacy parameters are known, LC offers no privacy advantage over releasing all models jointly (the bound is the sum of individual costs).
  • With DP-SGD Structure: By analyzing the per-step updates and the aggregation of Gaussian noise, the authors derive tighter bounds. The aggregated noise variance depends on the weighted sum of individual noise terms.
  • RDP: Derived via a complex summation over subsets of models and steps, utilizing the specific structure of DP-SGD updates.
  • PLD: Uses a surrogate privacy loss random variable to approximate the hockey-stick divergence, allowing for composition via convolution.

3. Key Contributions

1. Novel Framework: This is the first work to systematically study model merging specifically to satisfy flexible, target privacy constraints during inference, rather than just improving generalization.
2. Two Merging Algorithms:
   • RS: A lightweight, broadly applicable method requiring only privacy profiles.
   • LC: A method that leverages algorithmic structure (DP-SGD) to potentially achieve better utility/privacy tradeoffs.
3. Theoretical Analysis:
   • Provided tight privacy accounting for both methods using Rényi Differential Privacy (RDP) and Privacy Loss Distributions (PLD).
   • Mean Estimation Case Study: Theoretically proved that for Gaussian mean estimation, LC strictly dominates RS in terms of Mean Squared Error (MSE) for the same privacy budget. This is because LC utilizes information from all models, whereas RS discards $N-1$ models.
   • No-Free-Lunch: Proved that without structural assumptions (like DP-SGD), LC cannot improve upon the trivial solution of selecting the most private model.
4. Empirical Validation: Demonstrated that both methods allow for a continuous tradeoff curve between privacy and utility, outperforming naive composition baselines.

4. Results

Synthetic Data (Mean Estimation)

• LC vs. RS: LC consistently outperformed RS, achieving lower MSE for the same privacy budget. This validates the theoretical finding that LC leverages the additivity of Gaussian noise effectively.
• Accounting Tightness: PLD-based accounting provided tighter (smaller) $\epsilon$ bounds compared to RDP for the same utility.

Real-World Datasets (MNIST & CIFAR-10)

• Flexibility: Both RS and LC successfully generated models satisfying various target $\epsilon$ values without retraining.
• Performance:
  • MNIST (Convex): LC generally performed well, though the Pareto frontier was sometimes sparse in the middle range.
  • CIFAR-10 (Non-Convex): LC showed limitations in the "middle" of the privacy/utility tradeoff curve, often requiring extreme weights (relying heavily on one model) to be effective. RS demonstrated superior adaptability in non-convex settings.
• PLD vs. RDP: Across all experiments, PLD accounting yielded significantly tighter privacy guarantees (lower $\epsilon$) than RDP for the same utility.
• Pretraining Scenario: When models were initialized from a non-private pre-trained model, the merged models sometimes outperformed all individual input models. This suggests that merging can average out DP-induced noise while preserving shared useful structures, a phenomenon observed in non-private model merging literature.

5. Significance and Implications

• Operational Efficiency: The proposed methods allow organizations to deploy models that adapt to changing privacy regulations (e.g., GDPR, CCPA) instantly without retraining, saving significant computational resources and time.
• Privacy-Utility Optimization: By providing a continuous spectrum of models via mixing coefficients ($\pi$ or $\lambda$), the framework allows practitioners to fine-tune the exact privacy/utility balance required for a specific use case.
• Methodological Insight: The paper highlights a crucial distinction:
  • RS is robust and requires minimal assumptions, making it suitable for general black-box model merging.
  • LC offers theoretical superiority in specific settings (like Gaussian mechanisms) but requires detailed knowledge of the training algorithm (DP-SGD) to achieve tight privacy bounds.
• Future Directions: The work opens avenues for designing more sophisticated merging rules for non-convex models and developing private procedures to tune the merging parameters ($\lambda, \pi$) themselves.

In summary, this paper provides a rigorous theoretical and practical framework for "on-the-fly" privacy adaptation in machine learning, demonstrating that merging existing models is a viable and efficient alternative to retraining for dynamic privacy requirements.