Composition Theorems and Privacy Budget Management

Applying a differential privacy mechanism, such as noise addition, in a single round of federated learning provides an $(\epsilon, \delta)$ guarantee for that specific interaction. However, federated learning typically involves numerous communication rounds, sometimes hundreds or thousands. Each round potentially leaks a small amount of information. A critical question arises: how does the overall privacy loss accumulate across these multiple rounds? Simply stating the per-round guarantee is insufficient; we need to understand the total privacy cost over the entire training process. This is where composition theorems become essential.

Understanding Privacy Loss Accumulation

Imagine repeatedly querying a database (or in our case, repeatedly receiving noisy aggregated updates derived from client data) using DP mechanisms. Each query introduces some privacy loss. Composition theorems provide bounds on the total privacy loss after a sequence of such queries or mechanisms.

Basic Sequential Composition

The simplest way to analyze the combined effect is through basic sequential composition. It states that if you apply $k$ mechanisms, where the $i$-th mechanism is $(\epsilon_i, \delta_i)$-differentially private, the sequence of all $k$ mechanisms is $(\sum_{i=1}^k \epsilon_i, \sum_{i=1}^k \delta_i)$-differentially private.

If all mechanisms are identical, providing $(\epsilon, \delta)$-DP each time, then after $k$ rounds, the total privacy loss is bounded by $(k\epsilon, k\delta)$.

$$\epsilon_{total} \le k \epsilon_{round}$$ $$\delta_{total} \le k \delta_{round}$$

While simple and intuitive, this linear accumulation often results in a loose upper bound. In a typical FL scenario with many rounds ($k$ large), $k\epsilon$ can quickly become very large, suggesting a weak overall privacy guarantee unless the per-round $\epsilon_{round}$ is made extremely small. Making $\epsilon_{round}$ too small, however, often requires adding excessive noise, significantly degrading model utility. For practical FL systems needing hundreds of rounds, basic composition is often too pessimistic.

Advanced Composition

Fortunately, tighter bounds exist under the framework of advanced composition. These theorems leverage the fact that the privacy losses don't simply add up linearly in the worst way possible, especially concerning the $\epsilon$ parameter.

A standard result in advanced composition (derived from analyzing the moments accountant or using techniques like Rényi Differential Privacy) shows that for a sequence of $k$ mechanisms, each satisfying $(\epsilon, \delta)$-DP, the combined mechanism satisfies $(\epsilon', \delta')$-DP for any $\delta'' > 0$, where:

$$\epsilon' \approx \sqrt{2k \ln(1/\delta'')} \epsilon + k \epsilon (e^\epsilon - 1)$$ $$\delta' = k\delta + \delta''$$

Let's break down the expression for $\epsilon'$:

• The dominant term for small $\epsilon$ is often the first one: $\sqrt{2k \ln(1/\delta'')} \epsilon$. Notice the $\sqrt{k}$ dependency. This means the total $\epsilon'$ grows roughly sublinearly with the number of rounds $k$, rather than linearly as in basic composition.
• The second term $k \epsilon (e^\epsilon - 1)$ captures higher-order effects. For small $\epsilon$, $e^\epsilon - 1 \approx \epsilon$, so this term behaves like $k\epsilon^2$.
• $\delta''$ is an additional parameter representing a small probability that the privacy guarantee fails, in addition to the accumulated base $\delta$ values ($k\delta$). It's typically chosen to be small, for example, smaller than $1/N$, where $N$ is the dataset size.

The implication is significant: advanced composition allows for a much more favorable accumulation of privacy loss, especially for the $\epsilon$ parameter. We can afford a larger per-round $\epsilon_{round}$ for the same total budget $\epsilon_{total}$ compared to basic composition, leading to potentially better model utility.

Comparison of total privacy loss ($\epsilon$) accumulation over $k$ rounds using basic (linear) and advanced (sublinear) composition, assuming $\epsilon_{round}=0.1$, $\delta_{round}=10^{-5}$, and $\delta''=10^{-6}$ for the advanced calculation. Advanced composition yields significantly tighter bounds for larger $k$.

Modern privacy accounting methods, often based on Rényi Differential Privacy (RDP), provide frameworks for precisely tracking privacy loss under composition. RDP uses a different function (the RDP curve) to measure privacy loss, which composes very naturally. Tools like Google's dp-accounting library implement these techniques, allowing developers to accurately compute the $(\epsilon, \delta)$-DP guarantee for complex algorithms like DP-FedAvg run over multiple rounds.

Managing the Privacy Budget

The total acceptable privacy loss for the entire federated learning process is known as the privacy budget, typically denoted as $(\epsilon_{total}, \delta_{total})$. This budget represents the maximum cumulative privacy leakage we are willing to tolerate. Choosing appropriate values for $\epsilon_{total}$ and $\delta_{total}$ depends heavily on the sensitivity of the data, the application context, and any regulatory requirements (like GDPR or HIPAA). Common practice often aims for $\epsilon_{total}$ in the single digits (e.g., 1 to 10) and $\delta_{total}$ to be very small (e.g., less than $1/N_{clients}$, where $N_{clients}$ is the number of clients).

Once a total budget $(\epsilon_{total}, \delta_{total})$ is set for, say, $T$ communication rounds, the task becomes budget allocation: deciding how much privacy loss $(\epsilon_{round}, \delta_{round})$ is permissible in each round such that the total loss remains within the budget according to composition theorems.

Several strategies exist:

1. Uniform Allocation: The simplest approach is to divide the budget roughly equally across rounds. Using the advanced composition intuition ($\epsilon \propto \sqrt{k}$), one might set $\epsilon_{round} \approx \epsilon_{total} / \sqrt{T}$ and $\delta_{round} = \delta_{total} / T$. This requires determining the total number of rounds $T$ in advance.
2. Non-Uniform Allocation: It might be beneficial to spend more budget (allow larger $\epsilon_{round}$) in the initial rounds when model updates are larger and potentially more informative for convergence, and less budget (smaller $\epsilon_{round}$) in later rounds during fine-tuning. This requires careful planning and analysis.
3. Adaptive Allocation: The per-round budget could be adjusted dynamically based on the training progress, convergence speed, or other runtime factors. This is more complex but potentially optimizes the privacy-utility trade-off more effectively.

Practical Notes

• Accounting Tools: Manually applying composition theorems can be complex and error-prone, especially with advanced techniques like RDP. Using dedicated privacy accounting libraries is highly recommended. These libraries take the parameters of the DP mechanism used in each round (e.g., noise multiplier $\sigma$, clipping norm $C$, sampling probability $q$ in DP-SGD/DP-FedAvg) and the number of rounds, and compute the resulting $(\epsilon, \delta)$.
• Parameter Tuning: There's a direct relationship between the noise added (e.g., noise standard deviation $\sigma$ relative to the clipping norm $C$), the per-round privacy loss $\epsilon_{round}$, and model utility. Lower noise generally means better utility but higher $\epsilon_{round}$, consuming the budget faster. Higher noise provides better per-round privacy (lower $\epsilon_{round}$) but might hurt convergence or final accuracy. Tuning these parameters ($\sigma$, $C$, $T$, batch size, learning rate) while respecting the total privacy budget $(\epsilon_{total}, \delta_{total})$ is a core challenge in implementing DP-FL systems.
• Budget Depletion: Once the pre-defined privacy budget is exhausted after $T$ rounds, the training process must stop releasing differentially private outputs to maintain the guarantee.

Understanding and correctly applying composition theorems is fundamental for building federated learning systems with meaningful, quantifiable privacy guarantees over the entire training duration. Advanced composition and specialized accounting tools are indispensable for achieving practical privacy-utility trade-offs in multi-round federated processes.