Differential Privacy

The epsilon (ε) parameter is the core quantifier of the privacy guarantee. It bounds the maximum multiplicative difference in the probability of any output when a single individual's data is present or absent from the dataset. A smaller ε provides stronger privacy but typically reduces data utility.

• Interpretation: ε controls the 'privacy loss.' An algorithm with ε = 0.1 offers a stronger guarantee than one with ε = 1.0.
• Trade-off: Tuning ε manages the fundamental privacy-utility trade-off. For highly sensitive data (e.g., medical records), a very low ε (e.g., 0.01 to 0.1) is used, while for less sensitive aggregate analytics, a higher ε (e.g., 1.0 to 5.0) may be acceptable.

The delta (δ) parameter in (ε, δ)-Differential Privacy represents a small probability of the privacy guarantee failing. It allows for a negligible chance of a catastrophic privacy breach, which often enables more practical algorithms with better utility.

• Pure DP vs. Approximate DP: Pure Differential Privacy has δ = 0. Approximate Differential Privacy (δ > 0) is a relaxed, more commonly used variant.
• Typical Values: δ is set to a cryptographically small value, significantly less than the inverse of the dataset size (e.g., δ < 1e-5). This ensures the probability of failure is effectively negligible in practice.

A fundamental theorem of differential privacy states that any function applied to the output of a differentially private algorithm remains differentially private. No further analysis, computation, or transformation—without access to the original private data—can weaken the guarantee.

• Implication for Edge AI: A model trained with a DP algorithm can be deployed, its inferences analyzed, and its outputs aggregated without any additional privacy loss. This property is critical for building complex, multi-stage analytics pipelines on edge devices.

Differential privacy guarantees compose, allowing the privacy cost of multiple analyses to be calculated precisely.

• Sequential Composition: If you run k DP algorithms, each with parameters (ε_i, δ_i), on the same dataset, the total privacy cost is (Σε_i, Σδ_i).
• Parallel Composition: If you run DP algorithms on disjoint subsets of the data, the overall privacy cost is the maximum of the individual (ε_i, δ_i) parameters, not the sum. This is highly efficient for distributed edge learning.
• Advanced Composition: Tighter bounds exist (e.g., using the Moments Accountant) that provide better-than-linear growth of ε for many queries, enabling practical deep learning with DP-SGD.

Differential privacy extends its guarantee to protect groups of individuals. If an algorithm is ε-differentially private for single individuals, then it is kε-differentially private for a group of size k. This linear degradation with group size is inherent.

• Consequence: The guarantee weakens for very large groups. This formalizes the intuition that complete privacy for large populations is incompatible with releasing useful statistical information.
• Design Consideration: System architects must define the 'neighbor' relation in the DP definition (e.g., 'single user' vs. 'single device') based on the required level of group protection.

The family of (ε, δ)-differentially private mechanisms is closed under convex combination. This means if you have multiple DP algorithms, you can create a new algorithm that randomly selects among them according to some probability distribution, and the resulting algorithm is also DP (with parameters that can be bounded).

• Application: This property is useful in algorithm design, such as in exponential mechanism-based selections or in creating smoother, more robust randomized responses. It provides flexibility in constructing complex private algorithms from simpler, proven components.