0.1
Empirical Risk Minimization & Distributed Stochastic Gradient Descent
In standard supervised machine learning, we are given a dataset $D$ drawn from an unknown underlying data distribution $\mathcal{D}$. A deep neural network is parameterized by a weight vector $x \in \mathbb{R}^d$, where $d$ represents the total number of trainable parameters (often millions or tens of millions of float32 values in modern computer vision models). The goal of Empirical Risk Minimization (ERM) is to find optimal weights $x^*$ that minimize the expected loss:
$$\min_{x \in \mathbb{R}^d} f(x) \triangleq \mathbb{E}_{\xi \sim \mathcal{D}} [l(x; \xi)] \approx \frac{1}{|D|} \sum_{i=1}^{|D|} l(x; \xi_i)$$
In Decentralized Parallel Stochastic Gradient Descent (D-PSGD), the global dataset $D$ is partitioned across $n$ independent computing nodes (agents), $V = \{1, 2, \dots, n\}$, such that agent $i$ possesses a local private partition $D_i$. The joint optimization goal becomes:
$$\min_{x \in \mathbb{R}^d} \frac{1}{n} \sum_{i=1}^n f_i(x), \quad \text{where } f_i(x) \triangleq \frac{1}{|D_i|} \sum_{\xi \in D_i} l(x; \xi)$$
Unlike centralized training where a parameter server computes an exact global average $x = \frac{1}{n} \sum_i x_i$, decentralized agents must rely on diffusive consensus over a network graph $\mathcal{G}=(V,E)$. In each iteration, agent $i$ pulls parameter estimates from its direct neighbors and computes a weighted average using mixing weights. Lian et al. (NeurIPS 2017) proved that as long as the mixing matrix is doubly stochastic and symmetric, decentralized SGD asymptotically achieves the same $O(1/\sqrt{nT})$ convergence rate as centralized SGD, while completely eliminating the central server bottleneck!
0.2
The Anatomy of Privacy Leakage: Why Gradients Expose Raw Images
Many engineers initially believe that because raw training images are never transmitted across the network, distributed learning is inherently private. This intuition is provably false. The model parameters and gradients transmitted by an agent carry high-dimensional signatures of the exact images used to compute them.
1. Gradient Inversion & DLG Attacks (Zhu et al., 2019)
Consider a fully connected neural layer $z = W a + b$, where $a$ is the activation vector from the previous layer. By the chain rule of backpropagation, the gradient of the loss $L$ with respect to the weight matrix $W$ is:
$$\frac{\partial L}{\partial W} = \left(\frac{\partial L}{\partial z}\right) a^T = \delta \cdot a^T$$
Notice that the gradient is an outer product containing the exact activation vector $a$! For the very first layer of a vision model, $a$ is the raw input image pixels! A curious neighbor can initialize a dummy noise image $x^*$ and solve an optimization problem:
$$\min_{x^*} \|\nabla W(x^*) - \nabla W_{\text{received}}\|_2^2 + \mathcal{R}_{\text{TV}}(x^*)$$
Within a few hundred iterations, $x^*$ converges into a crystal-clear, pixel-perfect copy of the victim's private training image!
2. Membership Inference Attacks (Shokri et al., 2017)
Deep neural networks naturally exhibit slight overconfidence on samples that were part of their training set versus unseen samples. A curious neighbor observing the iterative parameter trajectories can train a shadow classifier to determine with high statistical certainty whether a specific patient's medical record or a specific citizen's face was used in training.
To thwart both gradient inversion and membership inference, the outputs of the learning process must satisfy a mathematically provable privacy definition: Differential Privacy.
0.3
Differential Privacy & The Gaussian Mechanism
Originally formulated by Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith (2006), Differential Privacy provides a rigorous mathematical guarantee: the outcome of any randomized analysis on a dataset is virtually indistinguishable whether any single individual's data is included or excluded.
The Hypothesis Testing Definition of $(\epsilon, \delta)$-DP
Let $D$ and $D'$ be two neighboring datasets differing by exactly one record ($|D \Delta D'| = 1$). A randomized mechanism $\mathcal{M}$ satisfies $(\epsilon, \delta)$-Differential Privacy if for all measurable output sets $S$:
$$\Pr[\mathcal{M}(D) \in S] \le e^\epsilon \Pr[\mathcal{M}(D') \in S] + \delta$$
- $\epsilon$ (Privacy Loss Budget): Bounds the maximum multiplicative advantage an adversary can gain from the presence or absence of a single record. Smaller $\epsilon$ means stronger privacy. Typical practical values: $\epsilon \in [0.5, 4.0]$.
- $\delta$ (Relaxation Parameter): The probability that the strict $e^\epsilon$ bound fails. To be meaningful, $\delta$ must be strictly smaller than $1/|D|$ (e.g., $\delta = 10^{-5}$ for a dataset of 60,000 images), representing a negligible failure probability.
The Gaussian Mechanism & Global $l_2$ Sensitivity
To turn an arbitrary function $f: \mathcal{D} \to \mathbb{R}^d$ into a differentially private mechanism, we add zero-mean Gaussian noise calibrated to the function's global $l_2$ sensitivity:
$$\Delta_2(f) \triangleq \max_{D, D': |D \Delta D'|=1} \|f(D) - f(D')\|_2$$
By Dwork et al. [14], adding noise $G \sim \mathcal{N}(0, \sigma^2 I_d)$ satisfies $(\epsilon, \delta)$-DP provided:
$$\sigma \ge \frac{\Delta_2(f) \sqrt{2 \ln(1.25/\delta)}}{\epsilon}$$
In deep learning, gradients are computed over unbounded parameter spaces; thus, their raw sensitivity $\Delta_2$ is mathematically $\infty$! To bound sensitivity, Abadi et al. [16] introduced gradient clipping: each individual gradient vector $g$ is clipped so that its $l_2$ norm never exceeds a fixed threshold $C$:
$$\bar{g} = \frac{g}{\max(1, \|g\|_2 / C)} \implies \|\bar{g}\|_2 \le C$$
Therefore, for a dataset of size $|D_i|$, replacing one training sample can alter the empirical average gradient by at most:
$$\Delta_2 = \frac{C}{|D_i|}$$
0.4
Privacy Composition: Why Naive Accounting Destroys Deep Learning
A neural network cannot be trained in a single iteration; it requires $T$ consecutive SGD update steps (e.g., $T = 10,000$ to $100,000$ steps). Every single step accesses the private training data and releases perturbed parameters.
1. Basic Composition Theorem
The privacy budget increases linearly: $\epsilon_{\text{total}} = T \cdot \epsilon'$.
If each step consumes $\epsilon' = 0.1$, after 1,000 steps the total budget explodes to $\epsilon = 100$ (completely worthless privacy guarantee!).
2. Advanced Composition Theorem (Dwork et al. 2010)
Using martingales, total budget scales as $O(\sqrt{T \ln(1/\delta')} \epsilon' + T \epsilon'(e^{\epsilon'} - 1))$.
Better, but still contains loose constants that force practitioners to inject massive Gaussian noise.
3. Rényi Differential Privacy (Mironov 2017)
Tracks the Rényi divergence of order $\lambda_R > 1$:
$$D_{\lambda_R}(P \| Q) = \frac{1}{\lambda_R - 1} \ln \int P(x)^{\lambda_R} Q(x)^{1-\lambda_R} dx$$
Gaussian mechanisms compose strictly linearly in RDP! Converting back to $(\epsilon, \delta)$ yields an optimal sublinear bound $O(\sqrt{T})$.