Objective Perturbation

The core mechanism adds a linear random term bᵀθ to the objective function before minimization. The noise vector b is drawn from a distribution with density proportional to exp(-η||b||), where η is calibrated to the privacy parameters. This ensures the minimizer itself is a differentially private output, exploiting the convexity of the loss function to absorb the perturbation into the final model parameters without iterative noise addition.

While output perturbation adds noise to the final learned parameters, objective perturbation integrates privacy into the training process itself.

• Output Perturbation: Solves the exact non-private objective, then adds noise proportional to the model's sensitivity.
• Objective Perturbation: Solves a single, privacy-enforcing optimization problem. This often yields tighter utility bounds for strongly convex losses because the noise is absorbed during optimization rather than applied post-hoc.

The standard proof of objective perturbation relies on the loss function being convex and differentiable. For empirical risk minimization, the regularizer must be a strongly convex function (e.g., L2 regularization). The strong convexity parameter λ controls the trade-off between privacy and utility: a larger λ reduces the sensitivity of the minimizer to individual data points, requiring less noise for the same privacy guarantee, but introduces more bias into the model.

Objective perturbation achieves pure ε-differential privacy in a single step. For a loss function with Lipschitz constant L and a regularizer with strong convexity parameter Δ, the mechanism guarantees ε-DP if the noise scale η satisfies specific conditions. Crucially, the privacy proof does not require tracking the privacy loss across iterations, as the entire computation is a single, atomic randomized mapping from the dataset to the model parameters.

Objective perturbation is naturally suited for regularized empirical risk minimization. The algorithm solves: min_θ (1/n) Σᵢ ℓ(θ; xᵢ, yᵢ) + (λ/2)||θ||² + (1/n) bᵀθ where ℓ is the per-example loss and b is the privacy-preserving noise. This formulation is directly compatible with standard convex optimization solvers, making it practical for logistic regression, linear regression, and support vector machines with smooth loss functions.

The formal privacy guarantee of objective perturbation degrades for non-convex loss functions, such as those in deep neural networks. The sensitivity analysis relies on the uniqueness of the minimizer and the contraction properties of convex optimization. In non-convex landscapes, where multiple local minima exist, the mapping from dataset to parameters is not stable enough to bound sensitivity. For deep learning, gradient perturbation (DP-SGD) is the preferred alternative.

The simplest approach to differential privacy where calibrated noise is added directly to the final model parameters or predictions after training completes. Unlike objective perturbation, this method does not modify the optimization process itself.

• Noise scale determined by the sensitivity of the learning algorithm
• Computationally cheaper than objective perturbation
• Often results in lower utility for the same privacy budget
• Used in Laplace mechanism and Gaussian mechanism applications

The dominant method for training deep neural networks with differential privacy. Per-example gradients are clipped to bound sensitivity, then Gaussian noise is added before each parameter update.

• Core algorithm: Differentially Private Stochastic Gradient Descent
• Uses moments accountant for tight privacy budget tracking
• Scales to large models but introduces significant computational overhead
• Privacy amplification via subsampling improves the privacy-utility trade-off

A general-purpose mechanism for selecting discrete outputs privately when the goal is to choose the 'best' item from a set. Selection probability is exponentially proportional to utility score.

• Designed for non-numeric queries where Laplace/Gaussian noise is inapplicable
• Requires a utility function that scores each candidate output
• Sensitivity is measured as the maximum change in utility from a single record
• Often used as a building block in more complex private algorithms

Private Aggregation of Teacher Ensembles trains a student model using noisy voting from an ensemble of teacher models, each trained on disjoint data partitions.

• Teachers never see data outside their partition
• Student learns from noisy aggregated labels only
• Privacy cost depends only on the number of student queries
• Provides strong user-level privacy guarantees when each user's data stays in one partition

An efficient mechanism for answering a stream of threshold queries while consuming privacy budget only for queries that exceed the threshold. Ideal for monitoring and anomaly detection.

• Maintains a noisy threshold that adapts dynamically
• Only spends budget on 'above-threshold' answers
• Enables answering many queries when few are significant
• Critical for building privacy-preserving monitoring systems

A trust model where each user perturbs their own data before transmission to an untrusted aggregator. No raw data ever leaves the user's device.

• Foundation: randomized response technique from survey methodology
• Used by Apple, Google, and Microsoft for telemetry collection
• Higher noise requirements than central DP models
• Eliminates need for a trusted data curator entirely