Differentially Private Empirical Risk Minimization (DP-ERM)

Injects calibrated noise directly into the loss function or its Taylor expansion before optimization begins. This method solves a perturbed optimization problem, ensuring the resulting model parameters satisfy differential privacy. It is particularly effective for strongly convex loss functions like logistic regression.

• Mechanism: Adds a linear noise term b^T θ and a quadratic regularizer to the objective.
• Advantage: Often yields tighter utility bounds than output perturbation for convex problems.
• Constraint: Requires the loss function to be strictly convex and doubly differentiable.

Trains a model on the non-private empirical risk using standard optimization, then adds noise to the final learned parameters θ* before release. The noise scale is calibrated to the sensitivity of the optimal solution to changes in the input data.

• Simplicity: Acts as a post-processing wrapper around any deterministic training algorithm.
• Sensitivity Bound: Relies on the strong convexity of the loss function to bound how much θ* shifts when a single record changes.
• Limitation: Inefficient for high-dimensional models where the L2 sensitivity of the parameter vector is large.

The dominant method for deep learning. Instead of perturbing the final model, noise is injected into the stochastic gradients during every iteration of training. Per-example gradient clipping bounds the influence of any single record, and Gaussian noise proportional to the clipping norm is added to the batched gradient.

• Algorithm: g_tilde = 1/B (Σ clip(∇f_i, C) + N(0, σ²C²I))
• Privacy Accounting: Uses a Moments Accountant or RDP to track the cumulative privacy loss over thousands of iterations.
• Scalability: Compatible with non-convex neural networks and large-scale datasets.

The theoretical utility guarantee for DP-ERM. It quantifies the difference between the expected loss of the private model and the true minimum loss. For (ε, δ)-DP, the excess risk scales as O(√p / (ε n)) where p is the dimensionality and n is the dataset size.

• Dimensionality Dependence: Utility degrades linearly with the square root of the parameter count.
• Sample Efficiency: Achieving high privacy (small ε) requires proportionally larger datasets to maintain constant utility.
• Tightness: This bound is minimax optimal for general convex empirical risk minimization.

The fundamental tension in DP-ERM governed by the privacy budget ε. As ε decreases (stronger privacy), the variance of the injected noise increases, degrading model accuracy. The trade-off is modulated by:

• Dataset Size (n): Larger datasets dilute the relative impact of noise.
• Clipping Norm (C): A smaller norm reduces sensitivity but introduces bias by truncating gradient information.
• Model Complexity: Over-parameterized models tend to memorize, requiring more noise to achieve the same ε.

A direct consequence of the composition theorem in DP-ERM. If a mechanism provides ε-differential privacy for a single record, it provides kε-differential privacy for a group of size k. This protects against adversaries with side information about multiple related records.

• Implication: Protecting a family of 4 under ε=1 single-record privacy requires accounting for a total budget of ε=4.
• Mitigation: User-level privacy definitions in DP-SGD clip and group all gradients from a single user before noising, providing a flat ε guarantee regardless of the number of contributions.

A DP-ERM technique that adds calibrated noise directly to the loss function before optimization. Unlike output perturbation, this method solves a single, privacy-preserving optimization problem. The noise is scaled by the sensitivity of the regularized objective, providing a tighter privacy budget than perturbing the final model weights. This approach is particularly effective for strongly convex loss functions like logistic regression and linear SVMs.

The simplest DP-ERM approach: train a standard non-private model, then add noise to the final model parameters before release. The noise magnitude is calibrated to the L2 sensitivity of the model weights with respect to the training data. While straightforward to implement, this method often requires more noise than objective or gradient perturbation, resulting in lower utility for the same privacy budget.

The workhorse algorithm for deep learning DP-ERM. During each training step, per-example gradients are computed, their L2 norms are clipped to a threshold C, and Gaussian noise calibrated to C and the privacy parameters is added to the batch gradient. The Moments Accountant tracks cumulative privacy loss across iterations, providing tight (ε, δ) bounds. This enables training of complex neural networks with formal privacy guarantees.

A family of techniques that incorporate the privacy budget directly into the training objective as a regularization term. By penalizing solutions that depend heavily on individual data points, the optimizer naturally converges to models with lower sensitivity. This approach often achieves better utility-privacy trade-offs than generic noise injection by exploiting the structure of the hypothesis class, particularly in high-dimensional sparse settings.

An alternative to DP-SGD for constrained optimization problems. This projection-free algorithm maintains a sparse atomic representation of the model, adding noise only to the linear minimization oracle at each iteration. It is particularly effective for training models with structured sparsity constraints, such as low-rank matrix completion or L1-regularized problems, under differential privacy.

A hybrid framework combining ideas from PATE and DP-ERM. Multiple models are trained on disjoint data partitions, and their predictions are privately aggregated to label a public dataset. A final model is then trained on this labeled public data. This decouples the private training from the public model deployment, enabling the use of arbitrary non-private architectures for the final model while maintaining end-to-end privacy.