Differential Privacy

The Laplace Mechanism is a fundamental algorithm for achieving differential privacy for numerical queries (e.g., counts, sums, averages). It adds noise drawn from a Laplace distribution, where the scale of the noise is calibrated to the query's sensitivity (the maximum possible change in the query's output from adding or removing one individual's data) divided by the desired privacy budget (epsilon).

• Key Property: Provides pure (ε)-differential privacy.
• Example: To privately release the average salary from a dataset, the mechanism calculates the true average, determines the sensitivity of the averaging function, and adds Laplace noise proportional to sensitivity / ε.
• Use Case: Ideal for releasing aggregate statistics from databases.

The Gaussian Mechanism is similar to the Laplace Mechanism but adds noise drawn from a Gaussian (normal) distribution. It is used when the weaker guarantee of (ε, δ)-differential privacy is acceptable, where δ represents a small probability of privacy failure.

• Key Property: Provides (ε, δ)-differential privacy, often allowing for less noise than the Laplace mechanism for the same ε when δ > 0.
• Noise Scale: The standard deviation of the Gaussian noise is scaled by the query's L2 sensitivity and a complex function of ε and δ.
• Use Case: Common in iterative algorithms like differentially private stochastic gradient descent (DP-SGD) for machine learning, where many queries are made.

The Exponential Mechanism is used for non-numeric queries where the output is a discrete object, such as selecting the best candidate from a set (e.g., 'Which disease is most prevalent?' or 'What is the most common job title?'). It works by assigning a utility score to each possible output and then sampling an output with a probability exponentially proportional to its utility, scaled by the privacy budget.

• Key Property: Can handle arbitrary output spaces, not just real numbers.
• How it works: Outputs with higher utility scores are exponentially more likely to be selected. The sensitivity here is of the utility function, not the output itself.
• Use Case: Privately releasing the "most frequent" item, selecting a hyperparameter, or choosing a decision from a set of options.

The privacy budget, epsilon (ε), quantifies the maximum allowable privacy loss. A smaller ε means stronger privacy. Composition theorems dictate how the privacy budget is consumed when multiple differentially private mechanisms are applied to the same dataset.

• Basic Composition: The ε values of sequential queries simply add up. If you run two mechanisms with ε=0.5 each, the total privacy loss is ε=1.0.
• Advanced Composition: Allows for a tighter (better) bound on total privacy loss for many queries, often scaling with the square root of the number of queries.
• Critical Management: Tracking and managing the cumulative ε across all analyses on a dataset is essential to avoid exhausting the budget and violating the privacy guarantee.

This distinction defines where the noise is added in the data pipeline.

• Central Model (Trusted Curator): Raw data is sent to a trusted server, which applies a DP mechanism (like Laplace) before releasing results. Provides more accurate results for a given ε but requires trust in the central entity.
• Local Model: Each individual's device adds DP noise to their data before sending it to the server. No entity ever sees clean data, offering stronger privacy but requiring significantly more noise, which reduces utility.
• Use Case Comparison: Central DP is used for organizational data analysis. Local DP is the foundation for privacy in systems like Google's RAPPOR for collecting browser statistics or Apple's emoji suggestions.

DP-SGD is the canonical algorithm for training machine learning models with differential privacy. It modifies standard Stochastic Gradient Descent by:

1. Clipping Gradients: The gradient for each training example is clipped to a maximum L2 norm. This bounds the sensitivity—how much one example can influence the model update.
2. Adding Noise: Gaussian noise is added to the average of the clipped gradients for each training batch.
3. Privacy Accounting: Using composition theorems (like the Moment Accountant), the total privacy cost (ε, δ) of the entire training run is precisely tracked.

• Trade-off: The noise and clipping introduce a privacy-utility trade-off; higher privacy (lower ε) typically reduces final model accuracy.

Selecting the best model configuration (hyperparameters) often requires multiple training runs and evaluating performance on a validation set. Applying differential privacy to this process protects the validation data. Techniques involve using the Exponential mechanism to privately select the best-performing configuration based on a noisy version of the validation score.

• Key Challenge: The tuning process itself can leak information about the validation data through repeated queries.
• Solution: A differentially private hyperparameter optimization algorithm accounts for the privacy budget spent across all tuning trials.

Instead of releasing a raw dataset or a trained model, one can use differential privacy to generate a synthetic dataset that mirrors the statistical properties of the original data. This is achieved by training a generative model (like a GAN or a marginal-based model) with DP-SGD. The synthetic data can then be used freely for model development without privacy constraints.

• Key Benefit: Enables open data sharing and collaboration where raw data is too sensitive.
• Example: Creating a synthetic population of patient health records for academic research, where correlations between conditions are preserved but no record corresponds to a real individual.

Even model inference can leak information. When users query a model via an API (e.g., "Is this transaction fraudulent?"), the sequence of answers could reveal details about the training data. Applying differential privacy to the inference outputs adds a layer of protection. This is crucial for machine learning as a service (MLaaS) platforms handling sensitive client data.

• Mechanism: Adding a small amount of random noise to the model's confidence scores or prediction labels before returning them to the user.
• Goal: Prevents membership inference attacks, where an adversary tries to determine if a specific data point was in the model's training set.

In differential privacy, the privacy budget or epsilon (ε) is a non-negative parameter that quantifies the maximum allowable privacy loss. A smaller ε provides stronger privacy guarantees but typically reduces the accuracy or utility of the query outputs.

• Core Definition: ε bounds the log of the ratio of the probabilities of seeing the same output for two adjacent datasets. An algorithm is ε-differentially private if this ratio is ≤ e^ε.
• Primary Use Case: Tracks cumulative privacy expenditure across multiple queries or training steps. Once the budget is exhausted, no further queries can be answered under the same guarantee.
• Management: Advanced compositions (e.g., Rényi Differential Privacy) allow for tighter tracking of the budget over many computations. This is critical for iterative processes like machine learning training.