<figure><img src="image_1.png" /></figure>

HAL
open science

# Mathematical Foundations of Trustworthy AI

Aizierjiang Aiersilan

► To cite this version:

Aizierjiang Aiersilan. Mathematical Foundations of Trustworthy AI. Doctoral. Studies in Trustworthy AI, Online, Macau SAR China. 2026, pp.142. hal-05449393

HAL Id: hal-05449393

https://hal.science/hal-05449393v1

Submitted on 8 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Mathematical Foundations of
Trustworthy AI

*Theory, Algorithms, and Engineering Principles*

LECTURE NOTES

Aizierjiang Aiersilan

Version 1.0 — January 8, 2026

## Abstract

When I was learning about Trustworthy AI, I found there were limited systematic books on its mathematical foundations, so I put together my notes taken during the early phase of my self-learning. In them, I provide a rigorous mathematical examination of Trustworthy AI, exploring reliable machine learning through the lens of constrained optimization, statistical learning theory, and differential geometry. I bring together concepts to define the multi-dimensional requirements of AI systems, moving beyond heuristic approaches toward a grounded engineering discipline. The notes formalize critical properties such as adversarial robustness via Lipschitz continuity and dual norms, algorithmic fairness via group constraints and impossibility theorems, and causal inference via structural causal models, etc. Through these, I aim to provide a useful systematic mathematical foundation for better understanding Trustworthy AI.

Keywords: Trustworthy AI, Adversarial Robustness, Algorithmic Fairness, Differential Privacy, Explainability, Causal Inference, Safe Reinforcement Learning
# Contents

1 Notation and Conventions 5

2 Introduction: The Necessity of Trust 6

3 Statistical Learning Theory and Generalization 7

3.1 The Learning Problem Formulation 7

3.2 Bias-Variance Decomposition 10

3.3 Uniform Convergence and VC Dimension 11

3.4 Rademacher Complexity 12

3.5 The Double Descent Phenomenon 13

3.6 PAC Learning Framework 14

3.7 Margin-Based Generalization Bounds 14

3.8 Algorithmic Stability 15

4 Adversarial Robustness 17

4.1 The Phenomenon of Adversarial Examples 17

4.2 High-Dimensional Geometry and Concentration 17

4.3 Taxonomy of Adversarial Attacks 18

4.4 White-Box Attacks 18

4.5 Black-Box Attacks 22

4.6 Adversarial Training and Robust Optimization 23

4.7 Certified Robustness via Randomized Smoothing 25

4.8 Natural Distribution Shifts and Domain Adaptation 27

5 Mathematical Foundations of Algorithmic Fairness 31

5.1 The Philosophical and Mathematical Underpinnings 31

5.2 Group Fairness: Statistical Parity and Beyond 31

5.3 Individual Fairness: The Metric Approach 32

5.4 Impossibility Results and Trade-offs 32

5.5 Intersectionality and Multi-Group Fairness 34

5.6 Fairness Metrics and Evaluation 34

5.7 Algorithmic Techniques for Fairness 35

5.8 Causal Fairness and Counterfactual Reasoning 36

5.9 Fairness in Modern AI Systems 39

5.10 Implementation Templates and Code Examples 40

5.11 Mechanisms for Fair Learning 43
<table><tbody><tr><td><strong>6 Privacy and Data Sovereignty</strong></td><td><strong>45</strong></td></tr><tr><td>6.1 Differential Privacy Foundations</td><td>45</td></tr><tr><td>6.2 Mechanisms for Differential Privacy</td><td>45</td></tr><tr><td>6.3 Composition and Renyi Differential Privacy</td><td>46</td></tr><tr><td>6.4 Privacy in Deep Learning</td><td>47</td></tr><tr><td>6.5 Secure Multi-Party Computation</td><td>48</td></tr><tr><td>6.6 Attacks on Privacy</td><td>52</td></tr><tr><td>6.7 Exercises</td><td>53</td></tr><tr><td><strong>7 Explainability and Interpretability</strong></td><td><strong>55</strong></td></tr><tr><td>7.1 Foundations of Explainable AI (XAI)</td><td>55</td></tr><tr><td>7.2 Taxonomy of XAI Methods</td><td>55</td></tr><tr><td>7.3 Feature Attribution Methods</td><td>55</td></tr><tr><td>7.4 Concept-Based Explanations</td><td>57</td></tr><tr><td>7.5 Evaluating Explanations</td><td>57</td></tr><tr><td>7.6 Algorithmic Recourse and Counterfactual Explanations</td><td>58</td></tr><tr><td><strong>8 Causal Inference and Machine Learning</strong></td><td><strong>62</strong></td></tr><tr><td>8.1 The Ladder of Causation</td><td>62</td></tr><tr><td>8.2 Structural Causal Models (SCM)</td><td>62</td></tr><tr><td>8.3 Interventions and the Do-Operator</td><td>62</td></tr><tr><td>8.4 The Do-Calculus</td><td>63</td></tr><tr><td>8.5 Counterfactuals</td><td>64</td></tr><tr><td>8.6 Causal Fairness</td><td>64</td></tr><tr><td>8.7 Exercises</td><td>64</td></tr><tr><td><strong>9 Federated Learning</strong></td><td><strong>66</strong></td></tr><tr><td>9.1 Introduction to Decentralized Learning</td><td>66</td></tr><tr><td>9.2 Federated Optimization Algorithms</td><td>66</td></tr><tr><td>9.3 Personalized Federated Learning</td><td>68</td></tr><tr><td>9.4 Communication Efficiency</td><td>69</td></tr><tr><td>9.5 Privacy and Security in FL</td><td>69</td></tr><tr><td>9.6 Robustness to Byzantine Attacks</td><td>70</td></tr><tr><td>9.7 Exercises</td><td>70</td></tr><tr><td><strong>10 Safe Reinforcement Learning</strong></td><td><strong>72</strong></td></tr><tr><td>10.1 The Alignment Problem in RL</td><td>72</td></tr><tr><td>10.2 Constrained Markov Decision Processes (CMDP)</td><td>72</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>10.3 Safe Exploration</td>
      <td>73</td>
    </tr>
    <tr>
      <td>10.4 Value Alignment and Inverse RL</td>
      <td>75</td>
    </tr>
    <tr>
      <td>10.5 Reward Hacking and Specification Gaming</td>
      <td>76</td>
    </tr>
    <tr>
      <td><strong>11 Out-of-Distribution Detection and Uncertainty Quantification</strong></td>
      <td><strong>80</strong></td>
    </tr>
    <tr>
      <td>11.1 The Problem of Distribution Shift</td>
      <td>80</td>
    </tr>
    <tr>
      <td>11.2 Approaches to OOD Detection</td>
      <td>81</td>
    </tr>
    <tr>
      <td>11.3 Bayesian Approaches to Uncertainty</td>
      <td>83</td>
    </tr>
    <tr>
      <td>11.4 Calibration</td>
      <td>84</td>
    </tr>
    <tr>
      <td>11.5 Conformal Prediction</td>
      <td>85</td>
    </tr>
    <tr>
      <td>11.6 Selective Prediction (Rejection)</td>
      <td>86</td>
    </tr>
    <tr>
      <td><strong>12 Engineering and Governance</strong></td>
      <td><strong>89</strong></td>
    </tr>
    <tr>
      <td>12.1 Formal Verification of Neural Networks</td>
      <td>89</td>
    </tr>
    <tr>
      <td>12.2 From Theory to Practice: MLOps for Trustworthy AI</td>
      <td>91</td>
    </tr>
    <tr>
      <td>12.3 Documentation and Transparency</td>
      <td>92</td>
    </tr>
    <tr>
      <td>12.4 AI Governance and Regulation</td>
      <td>92</td>
    </tr>
    <tr>
      <td><strong>13 Advanced Topics in Trustworthy AI</strong></td>
      <td><strong>95</strong></td>
    </tr>
    <tr>
      <td>13.1 Neural Architecture Design for Trustworthiness</td>
      <td>95</td>
    </tr>
    <tr>
      <td>13.2 Robust Statistics and Heavy-Tailed Data</td>
      <td>97</td>
    </tr>
    <tr>
      <td>13.3 Causal Machine Learning</td>
      <td>98</td>
    </tr>
    <tr>
      <td>13.4 Privacy-Preserving Machine Learning: Advanced Topics</td>
      <td>100</td>
    </tr>
    <tr>
      <td>13.5 Trustworthy AI for Large Language Models</td>
      <td>100</td>
    </tr>
    <tr>
      <td><strong>14 Mathematical Background</strong></td>
      <td><strong>103</strong></td>
    </tr>
    <tr>
      <td>14.1 Probability Theory Foundations</td>
      <td>103</td>
    </tr>
    <tr>
      <td>14.2 Concentration Inequalities</td>
      <td>104</td>
    </tr>
    <tr>
      <td>14.3 Information Theory</td>
      <td>105</td>
    </tr>
    <tr>
      <td>14.4 Convex Optimization</td>
      <td>106</td>
    </tr>
    <tr>
      <td><strong>15 Advanced Proofs and Derivations</strong></td>
      <td><strong>108</strong></td>
    </tr>
    <tr>
      <td>15.1 Proof of the VC Dimension Lower Bound</td>
      <td>108</td>
    </tr>
    <tr>
      <td>15.2 Derivation of the Evidence Lower Bound (ELBO)</td>
      <td>108</td>
    </tr>
    <tr>
      <td>15.3 Proof of Differential Privacy Composition</td>
      <td>109</td>
    </tr>
    <tr>
      <td>15.4 Convergence of SGD for Convex Objectives</td>
      <td>110</td>
    </tr>
    <tr>
      <td>15.5 Proof of Rademacher Complexity Bound</td>
      <td>110</td>
    </tr>
    <tr>
      <td>15.6 Shapley Value Axioms and Uniqueness</td>
      <td>111</td>
    </tr>
  </tbody>
</table>
<table><tr><td><b>16 Python Implementation Details</b></td><td><b>112</b></td></tr><tr><td>16.1 Fast Gradient Sign Method (FGSM)</td><td>112</td></tr><tr><td>16.2 Differential Privacy: Laplace Mechanism</td><td>112</td></tr><tr><td>16.3 Fairness Regularization</td><td>113</td></tr><tr><td>16.4 Projected Gradient Descent Attack</td><td>113</td></tr><tr><td>16.5 Adversarial Training Loop</td><td>114</td></tr><tr><td>16.6 Conformal Prediction</td><td>115</td></tr><tr><td>16.7 Integrated Gradients</td><td>116</td></tr><tr><td><b>17 Comprehensive Evaluation Metrics</b></td><td><b>119</b></td></tr><tr><td>17.1 Robustness Metrics</td><td>119</td></tr><tr><td>17.2 Fairness Metrics</td><td>119</td></tr><tr><td>17.3 Privacy Metrics</td><td>120</td></tr><tr><td>17.4 OOD Detection Metrics</td><td>121</td></tr><tr><td>17.5 Explainability Metrics</td><td>121</td></tr><tr><td><b>18 Glossary of Key Terms</b></td><td><b>122</b></td></tr><tr><td><b>19 List of Notation</b></td><td><b>135</b></td></tr><tr><td><b>20 Acknowledgments</b></td><td><b>138</b></td></tr></table>
## 1 Notation and Conventions

Throughout this document, we use consistent mathematical notation. Let $\mathcal{X} \subseteq \mathbb{R}^d$ denote the input space and $\mathcal{Y}$ the output space. A dataset is $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$. We use $\mathbb{E}$ for expectation, Var for variance, and $P(\cdot)$ for probability.

**Probability Notation:** $P(X)$ or $\mathcal{P}$ denotes a probability distribution. We write $X \perp Y | Z$ for conditional independence.

**Norms:** $\|x\|_p$ is the $L_p$ norm: $\|x\|_2 = \sqrt{\sum_i x_i^2}$ (Euclidean), $\|x\|_\infty = \max_i |x_i|$ (max). For matrices, $\|W\|_{op}$ is the spectral norm.

**Indicator Function:** $\mathbb{I}(\text{event}) = 1$ if true, 0 otherwise.

**Operators:** $\arg\min_x f(x)$ and $\arg\max_x f(x)$ denote the minimizing and maximizing arguments. $\nabla f$ is the gradient.

**Causal Notation:** Interventions are denoted by the do-operator $do(X = x)$, setting variable $X$ to value $x$. Counterfactuals are written as $Y_{x'}$, the value of $Y$ under intervention $do(X = x')$. Graph manipulations include $G_{\bar{X}}$ (arrows into $X$ removed) and $G_X$ (arrows out of $X$ removed).

**Subscripts and Superscripts:** Common conventions include $t$ for time step or round, $k$ for client $k$ in federated learning, $*$ for optimal values, $'$ for baseline or perturbed versions, and $\hat{\cdot}$ for empirical estimates.

**Federated Learning:** Client-specific quantities are denoted with subscripts, e.g., $p_k$ for client weight, $F_k$ for local loss, $S_t$ for selected clients at round $t$.

**Safety and Robustness:** Barrier functions are denoted $h(s)$, Lyapunov functions $V(s)$, and uncertainty sets $\mathcal{U}$.

**General Conventions:** Bold symbols like $\mathbf{w}$ denote vectors or matrices. Calligraphic letters like $\mathcal{X}$ denote sets or spaces. Greek letters are used for parameters (e.g., $\epsilon$ for perturbation budgets, $\delta$ for failure probabilities).
## 2 Introduction: The Necessity of Trust

The rapid and pervasive integration of Artificial Intelligence (AI) into the fabric of modern society has fundamentally altered the landscape of decision-making in critical sectors such as healthcare, finance, criminal justice, and autonomous transportation. While the empirical performance of these systems, measured by aggregate metrics like accuracy or F1-score on static test sets, has reached superhuman levels, this superficial success often masks deep-seated vulnerabilities. The deployment of AI in high-stakes environments has precipitated a crisis of trust, driven by high-profile failures where systems have exhibited brittleness in the face of adversarial manipulation, exhibited unintended disparities in data sub-populations, leaked sensitive personal information, or operated as inscrutable black boxes whose reasoning cannot be audited. Trustworthy AI, therefore, is not merely a collection of ethical guidelines or policy desiderata; it is a rigorous technical discipline that demands a foundational reimagining of how we design, train, and verify machine learning systems. It requires moving beyond the paradigm of average-case performance maximization to a regime of worst-case robustness, causal validity, and provable constraints.

We posit that the nebulous concept of “trust” can be decomposed into a set of mathematically precise, verifiable properties. Rather than relying on intuition, we define these properties through the lens of constrained optimization, statistical learning theory, and differential geometry. **Robustness** is formalized as the invariance of the model’s output under bounded perturbations of the input, requiring Lipschitz continuity or specific geometric margins. **Fairness** is articulated as statistical independence between model predictions and sensitive attributes, or as the equality of error rates across demographic groups, often invoking impossibility theorems that delineate the trade-offs between different ethical ideals. **Privacy** is rigorously defined via Differential Privacy, which quantifies the stability of the algorithm’s output distribution with respect to the presence or absence of any single individual’s data. **Explainability** seeks to provide faithful, interpretable surrogates or attribution maps that elucidate the decision boundary, while **Causality** ensures that the model captures the structural equations governing the data generation process, rather than merely exploiting spurious correlations. This document may also serve as a comprehensive mathematical and technical reference for Trustworthy AI.

<table><caption>Table 1: Dimensions of Trustworthy AI and their Mathematical Formalizations</caption><thead><tr><td>Dimension</td><td>Core Concept</td><td>Mathematical Formalism</td></tr></thead><tbody><tr><td>Robustness</td><td>Stability under perturbation</td><td>Lipschitz continuity, Dual norms, Min-max optimization</td></tr><tr><td>Fairness</td><td>Independence from sensitive traits</td><td>Statistical Parity (Y&#770; &perp; A), Equalized Odds (Y&#770; &perp; A|Y)</td></tr><tr><td>Privacy</td><td>Indistinguishability of datasets</td><td>Differential Privacy (ε, δ-DP), Renyi Divergence</td></tr><tr><td>Explainability</td><td>Interpretability of decisions</td><td>Shapley values, Local linear approximations, Saliency maps</td></tr><tr><td>Causality</td><td>Structural validity</td><td>Structural Causal Models (SCM), Do-calculus, Intervention</td></tr></tbody></table>

*Note:* In this table, $\hat{Y}$ denotes the model prediction, A represents the sensitive attribute, Y is the true label, $\perp$ indicates statistical independence, and $\epsilon, \delta$ are privacy budget parameters.
# 3 Statistical Learning Theory and Generalization

This section establishes the mathematical foundations of statistical learning theory, which provides the theoretical framework for understanding when and why machine learning algorithms work. We develop the core concepts rigorously, with complete proofs and detailed explanations that connect the mathematical formalism to practical implications for Trustworthy AI.

## 3.1 The Learning Problem Formulation

### 3.1.1 Mathematical Setup

The fundamental goal of supervised machine learning is to construct a predictive mapping $f: \mathcal{X} \to \mathcal{Y}$ that generalizes well to unseen data. Let $\mathcal{X} \subseteq \mathbb{R}^d$ denote the input manifold and $\mathcal{Y}$ the output space. We assume the existence of a joint probability distribution $\mathcal{P}$ over $\mathcal{X} \times \mathcal{Y}$. The learner is provided with a training dataset $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$, where each sample is drawn independently and identically distributed (i.i.d.) from $\mathcal{P}$.

**Definition 3.1** (Statistical Learning Problem). A statistical learning problem is specified by a tuple $(\mathcal{X}, \mathcal{Y}, \mathcal{P}, \mathcal{H}, \ell)$ where:

* $\mathcal{X} \subseteq \mathbb{R}^d$ is the **input space** (feature space)

* $\mathcal{Y}$ is the **output space** (label space)

* $\mathcal{P}$ is an unknown probability distribution over $\mathcal{X} \times \mathcal{Y}$

* $\mathcal{H} \subseteq \{f: \mathcal{X} \to \mathcal{Y}\}$ is the **hypothesis class**

* $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$ is the **loss function**

The assumption of i.i.d. sampling is central to classical learning theory, allowing us to apply the Law of Large Numbers and concentration inequalities to bound the difference between empirical observations and true population statistics. However, in the context of Trustworthy AI, this assumption is often violated—adversaries may shift the distribution, or the deployment environment may differ from the training environment (distribution shift).

### 3.1.2 Common Output Spaces and Loss Functions

For **binary classification**, $\mathcal{Y} = \{-1, +1\}$ or $\{0, 1\}$. Common loss functions include:

* **0-1 Loss**: $\ell_{0-1}(\hat{y}, y) = \mathbb{I}(\hat{y} \neq y)$

* **Hinge Loss**: $\ell_{hinge}(\hat{y}, y) = \max(0, 1 - y\hat{y})$ (used in SVMs)

* **Logistic Loss**: $\ell_{log}(\hat{y}, y) = \log(1 + e^{-y\hat{y}})$ (used in logistic regression)

* **Exponential Loss**: $\ell_{exp}(\hat{y}, y) = e^{-y\hat{y}}$ (used in AdaBoost)

For **multi-class classification**, $\mathcal{Y} = \{1, 2, \dots, K\}$. The cross-entropy loss is:

$$ \ell_{CE}(\hat{p}, y) = - \sum_{k=1}^{K} \mathbb{I}(y = k) \log \hat{p}_k = - \log \hat{p}_y \quad (1) $$
where $\hat{p} \in \Delta^{K-1}$ is a probability distribution over classes, $\hat{p}_k$ is the predicted probability for class $k$, $y \in \{1, \dots, K\}$ is the true class label, and $\mathbb{I}(\cdot)$ is the indicator function which is 1 if the argument is true and 0 otherwise.

For regression, $\mathcal{Y} = \mathbb{R}$ or $\mathcal{Y} = \mathbb{R}^m$. Common loss functions include:

*   **Squared Loss:** $\ell_2(\hat{y}, y) = (y - \hat{y})^2$

*   **Absolute Loss:** $\ell_1(\hat{y}, y) = |y - \hat{y}|$

*   **Huber Loss:** $\ell_{\delta}(\hat{y}, y) = \begin{cases} \frac{1}{2}(y - \hat{y})^2 & |y - \hat{y}| \le \delta \\ \delta(|y - \hat{y}| - \frac{\delta}{2}) & \text{otherwise} \end{cases}$ where $\delta > 0$ is a threshold parameter controlling the transition from quadratic to linear behavior.

*   **Quantile Loss:** $\ell_{\tau}(\hat{y}, y) = \max(\tau(y - \hat{y}), (\tau - 1)(y - \hat{y}))$ for $\tau \in (0, 1)$, where $\tau$ represents the target quantile (e.g., $\tau = 0.5$ for median regression).

### 3.1.3 Risk and Empirical Risk

The quality of a predictor $f$ is measured by a loss function $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\ge 0}$. The true objective is to minimize the *expected risk* (also called *population risk* or *true risk*), which represents the average loss over the entire data distribution:

**Definition 3.2 (Expected Risk).** The expected risk of a hypothesis $f \in \mathcal{H}$ is:

$$ \mathcal{R}(f) := \mathbb{E}_{(x,y) \sim \mathcal{P}}[\ell(f(x), y)] = \int_{\mathcal{X} \times \mathcal{Y}} \ell(f(x), y) d\mathcal{P}(x, y) \quad (2) $$

where $\mathbb{E}$ denotes the expectation operator with respect to the joint distribution $\mathcal{P}$, and $\ell$ is the loss function.

**Definition 3.3 (Bayes Optimal Predictor).** The Bayes optimal predictor $f^*$ minimizes the expected risk over all measurable functions:

$$ f^* = \arg\min_{f: \mathcal{X} \to \mathcal{Y}} \mathcal{R}(f) \quad (3) $$

where the minimization is taken over the space of all measurable functions from $\mathcal{X}$ to $\mathcal{Y}$. The corresponding minimum risk $\mathcal{R}(f^*) = \mathcal{R}^*$ is called the **Bayes risk**.

**Proposition 3.1 (Bayes Optimal Predictors).** For common loss functions, the Bayes optimal predictor has closed form:

1.  For squared loss: $f^*(x) = \mathbb{E}[Y|X = x]$ (conditional mean)

2.  For absolute loss: $f^*(x) = \text{median}(Y|X = x)$ (conditional median)

3.  For 0-1 loss: $f^*(x) = \arg\max_y P(Y = y|X = x)$ (MAP estimate)

*Proof.* We prove each case separately.

**Case 1 (Squared Loss):** For squared loss:

$$ \mathcal{R}(f) = \mathbb{E}[(Y - f(X))^2] = \mathbb{E}[\mathbb{E}[(Y - f(X))^2|X]] \quad (4) $$

$$ = \mathbb{E}[\mathbb{E}[Y^2|X] - 2f(X)\mathbb{E}[Y|X] + f(X)^2] \quad (5) $$
Taking the functional derivative with respect to $f(x)$ and setting to zero:

$$ \frac{\partial}{\partial f(x)} \mathbb{E}[(Y - f(X))^2 | X = x] = -2 \mathbb{E}[Y | X = x] + 2f(x) = 0 \quad (6) $$

Thus $f^*(x) = \mathbb{E}[Y | X = x]$.

**Case 2 (Absolute Loss):** For absolute loss, we minimize:

$$ \mathcal{R}(f) = \mathbb{E}[|Y - f(X)|] = \mathbb{E}[\mathbb{E}[|Y - f(X)| | X]] \quad (7) $$

For a fixed $x$, we need to minimize $\mathbb{E}[|Y - c| | X = x]$ over $c \in \mathbb{R}$. This is a classical result: the minimizer of $\mathbb{E}[|Z - c|]$ for any random variable $Z$ is the median of $Z$. To see this, note that the derivative of $g(c) = \mathbb{E}[|Y - c| | X = x]$ is:

$$ g'(c) = \mathbb{E}[\mathrm{sign}(c - Y) | X = x] = P(Y < c | X = x) - P(Y > c | X = x) \quad (8) $$

This equals zero when $P(Y < c | X = x) = P(Y > c | X = x) = 1/2$, i.e., when $c$ is the conditional median.

**Case 3 (0-1 Loss):** For 0-1 loss in classification:

$$ \mathcal{R}(f) = \mathbb{E}[\mathbb{I}(f(X) \neq Y)] = \mathbb{E}[\mathbb{E}[\mathbb{I}(f(X) \neq Y) | X]] \quad (9) $$

$$ = \mathbb{E}[P(f(X) \neq Y | X)] = \mathbb{E}[1 - P(Y = f(X) | X)] \quad (10) $$

For fixed $x$, we maximize $P(Y = c | X = x)$ over $c \in \mathcal{Y}$. This is achieved by the maximum a posteriori (MAP) estimate:

$$ f^*(x) = \arg \max_{y \in \mathcal{Y}} P(Y = y | X = x) \quad (11) $$

□

Since $\mathcal{P}$ is unknown, we cannot compute $\mathcal{R}(f)$ directly. Instead, we resort to the *Empirical Risk Minimization* (ERM) principle, which minimizes the empirical average of the loss on the training set:

**Definition 3.4 (Empirical Risk).** Given a dataset $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$, the empirical risk is:

$$ \hat{\mathcal{R}}_{\mathcal{D}}(f) := \frac{1}{N} \sum_{i=1}^{N} \ell(f(x_i), y_i) \quad (12) $$

where $N$ is the number of training samples and $(x_i, y_i)$ is the $i$-th input-output pair.

**Definition 3.5 (Empirical Risk Minimization).** The ERM principle selects the hypothesis that minimizes empirical risk:

$$ \hat{f}_{\text{ERM}} = \arg \min_{f \in \mathcal{H}} \hat{\mathcal{R}}_{\mathcal{D}}(f) \quad (13) $$

The central question of learning theory is: Under what conditions does minimizing the empirical risk $\hat{\mathcal{R}}(f)$ lead to a small expected risk $\mathcal{R}(f)$? This convergence is governed by the complexity of the hypothesis class $\mathcal{H}$ from which $f$ is chosen. If $\mathcal{H}$ is too complex, we may find a function that fits the training data perfectly (memorization) but fails to generalize; if it is too simple, we may fail to capture the underlying patterns (underfitting).
### 3.1.4 Decomposition of Excess Risk

A key insight is to decompose the excess risk of ERM into interpretable components:

**Theorem 3.2 (Excess Risk Decomposition).** Let $f^* = \arg\min_f \mathcal{R}(f)$ be the Bayes optimal predictor, $f_H^* = \arg\min_{f \in \mathcal{H}} \mathcal{R}(f)$ be the best-in-class predictor, and $\hat{f} = \arg\min_{f \in \mathcal{H}} \hat{\mathcal{R}}(f)$ be the ERM solution. Then:

$$ \underbrace{\mathcal{R}(\hat{f}) - \mathcal{R}(f^*)}_{\text{Excess Risk}} = \underbrace{\mathcal{R}(f_H^*) - \mathcal{R}(f^*)}_{\text{Approximation Error}} + \underbrace{\mathcal{R}(\hat{f}) - \mathcal{R}(f_H^*)}_{\text{Estimation Error}} \quad (14) $$

where $\mathcal{R}(\cdot)$ denotes the expected risk.

The approximation error measures the expressiveness of $\mathcal{H}$—how well the best function in our hypothesis class can approximate the true optimal function. This error decreases as $\mathcal{H}$ becomes richer.

The estimation error measures the statistical difficulty of finding the best function in $\mathcal{H}$ from finite samples. This error increases with the complexity of $\mathcal{H}$ and decreases with more data.

This decomposition reveals a fundamental trade-off: richer hypothesis classes reduce approximation error but increase estimation error. Trustworthy AI adds additional constraints to $\mathcal{H}$ (fairness, robustness), which may increase approximation error but provide crucial safety guarantees.

## 3.2 Bias-Variance Decomposition

To understand the sources of error in a learning algorithm, we can decompose the expected risk into interpretable components. Consider the squared error loss $\ell(y, \hat{y}) = (y - \hat{y})^2$ in a regression setting. Let the true relationship be $y = g(x) + \epsilon$, where $\epsilon \sim \mathcal{N}(0, \sigma^2)$ is irreducible noise with zero mean and variance $\sigma^2$. Let $\hat{f}_D(x)$ be the predictor learned from a specific dataset $D$. We are interested in the expected error of the algorithm at a point $x$, averaged over all possible realizations of the training dataset $D$.

**Theorem 3.3 (Bias-Variance Decomposition).** For squared loss and $y = g(x) + \epsilon$ with $\mathbb{E}[\epsilon] = 0$ and $\text{Var}(\epsilon) = \sigma^2$:

$$ \mathbb{E}_D \mathbb{E}_\epsilon [(y - \hat{f}_D(x))^2] = \sigma^2 + (g(x) - \bar{f}(x))^2 + \mathbb{E}_D [(\hat{f}_D(x) - \bar{f}(x))^2] \quad (15) $$

where $\bar{f}(x) = \mathbb{E}_D[\hat{f}_D(x)]$ is the average prediction over all possible training sets $D$, $\mathbb{E}_\epsilon$ denotes expectation over the random choice of training set, and $\mathbb{E}_\epsilon$ denotes expectation over the noise in the test point.

*Proof.* We begin by expanding the expected squared error:

$$ \mathbb{E}_D \mathbb{E}_\epsilon [(y - \hat{f}_D(x))^2] = \mathbb{E}_D \mathbb{E}_\epsilon [(g(x) + \epsilon - \hat{f}_D(x))^2] \quad (16) $$

Expanding the square and using linearity of expectation:

$$ = \mathbb{E}_D \mathbb{E}_\epsilon [(g(x) - \hat{f}_D(x))^2 + \epsilon^2 + 2\epsilon(g(x) - \hat{f}_D(x))] \quad (17) $$

Since $\epsilon$ is independent of $D$ and has mean zero, the cross-term vanishes ($\mathbb{E}_\epsilon[\epsilon] = 0$). Also, $\mathbb{E}_\epsilon[\epsilon^2] = \sigma^2$:

$$ = \mathbb{E}_D [(g(x) - \hat{f}_D(x))^2] + \sigma^2 \quad (18) $$
Now we analyze the term $\mathbb{E}_D[(g(x) - \hat{f}_D(x))^2]$. Let $\bar{f}(x) = \mathbb{E}_D[\hat{f}_D(x)]$ be the average prediction. We add and subtract $\bar{f}(x)$:

$$ \mathbb{E}_D[(g(x) - \hat{f}_D(x))^2] = \mathbb{E}_D[(g(x) - \bar{f}(x) + \bar{f}(x) - \hat{f}_D(x))^2] \quad (19) $$

Let $a = g(x) - \bar{f}(x)$ (a constant with respect to $D$) and $b = \bar{f}(x) - \hat{f}_D(x)$. Then:

$$ \mathbb{E}_D[(a + b)^2] = a^2 + \mathbb{E}_D[b^2] + 2a \mathbb{E}_D[b] \quad (20) $$

$$ = (g(x) - \bar{f}(x))^2 + \mathbb{E}_D[(\hat{f}_D(x) - \bar{f}(x))^2] + 2(g(x) - \bar{f}(x)) \mathbb{E}_D[\bar{f}(x) - \hat{f}_D(x)] \quad (21) $$

The cross term is zero because $\mathbb{E}_D[\hat{f}_D(x)] = \bar{f}(x)$ by definition, so $\mathbb{E}_D[\bar{f}(x) - \hat{f}_D(x)] = 0$.

Thus, we arrive at the classic decomposition:

$$ \text{Error} = \underbrace{\sigma^2}_{\text{Irreducible}} + \underbrace{(g(x) - \bar{f}(x))^2}_{\text{Bias}^2} + \underbrace{\mathbb{E}_D[(\hat{f}_D(x) - \bar{f}(x))^2]}_{\text{Variance}} \quad (22) $$

□

**Remark 3.1 (Interpretation of Terms).**

* The **Bias** term measures the systematic error introduced by the simplifying assumptions of the model class (e.g., approximating a non-linear function with a linear model). It represents the error incurred even with infinite data, due to fundamental limitations of the hypothesis space.

* The **Variance** term measures the sensitivity of the model to the specific realization of the training data, quantifying how much predictions fluctuate across different datasets of the same size.

* The **Irreducible Error** ($\sigma^2$) represents noise inherent in the data-generating process that no model can eliminate.

In the context of Trustworthy AI, we often introduce constraints (such as fairness or robustness) that restrict the hypothesis space $\mathcal{H}$. This inevitably increases the bias of the model (as we may exclude the “true” unconstrained minimizer) but can potentially reduce variance or ensure safety properties that are critical for deployment. Understanding this trade-off is essential for designing trustworthy systems where perfect accuracy is sacrificed for guaranteed safety or fairness.

## 3.3 Uniform Convergence and VC Dimension

To guarantee generalization, we require that the empirical risk converges to the true risk uniformly over the hypothesis class $\mathcal{H}$. If the convergence is not uniform, the learning algorithm might select a “bad” hypothesis that happens to perform well on the training set due to random chance.

**Definition 3.6 (Uniform Convergence).** A hypothesis class $\mathcal{H}$ has the uniform convergence property if for every $\epsilon > 0$ and $\delta > 0$, there exists a sample size $N(\epsilon, \delta)$ such that for all $N \ge N(\epsilon, \delta)$:

$$ P \left( \sup_{f \in \mathcal{H}} |\mathcal{R}(f) - \hat{\mathcal{R}}(f)| > \epsilon \right) < \delta \quad (23) $$

where $P$ denotes the probability over the random draw of the training set of size $N$.
The Vapnik-Chervonenkis (VC) dimension provides a combinatorial measure of the complexity of $\mathcal{H}$ for binary classification. It is defined as the size of the largest set of points that can be “shattered” by $\mathcal{H}$, meaning that the hypothesis class can assign all possible $2^N$ label configurations to the points.

**Theorem 3.4 (Vapnik-Chervonenkis Bound).** For a binary classification problem with 0-1 loss, if $\mathcal{H}$ has finite VC dimension $d_{VC}$, then with probability at least $1 - \delta$, for any $f \in \mathcal{H}$:

$$ \mathcal{R}(f) \le \hat{\mathcal{R}}(f) + \sqrt{\frac{8d_{VC}\ln(2N) + 8\ln(4/\delta)}{N}} \quad (24) $$

where $N$ is the number of samples, $\ln$ is the natural logarithm, and the probability is taken over the random draw of the training set.

*Proof Sketch.* The key insight is to bound the growth function $\Pi_{\mathcal{H}}(N)$, which counts the maximum number of distinct labelings that $\mathcal{H}$ can produce on any dataset of size $N$. Sauer's Lemma establishes that if $d_{VC}(\mathcal{H}) = d$, then:

$$ \Pi_{\mathcal{H}}(N) \le \sum_{i=0}^{d} \binom{N}{i} \le \left(\frac{eN}{d}\right)^d \quad (25) $$

This polynomial growth (compared to the exponential $2^N$ for unrestricted classes) enables uniform convergence. Using a union bound over the $\Pi_{\mathcal{H}}(N)$ possible dichotomies and applying Hoeffding's inequality yields the stated bound. The full proof requires symmetrization arguments and is found in [33]. □

This bound is fundamental because it is distribution-free; it holds for any data distribution $\mathcal{P}$. However, this universality comes at a cost: the bound is often loose for practical applications. For modern neural networks, the VC dimension is roughly proportional to the number of parameters, which can be in the billions. The VC bound would suggest that we need billions of samples to generalize, yet these networks generalize well with far fewer samples. This discrepancy motivates the study of data-dependent complexity measures.

## 3.4 Rademacher Complexity

Rademacher Complexity measures the ability of the hypothesis class to fit random noise. Unlike VC dimension, it depends on the specific distribution of the data.

**Definition 3.7 (Empirical Rademacher Complexity).** Let $\sigma = (\sigma_1, \dots, \sigma_N)$ be independent Rademacher variables where $P(\sigma_i = 1) = P(\sigma_i = -1) = 0.5$. The empirical Rademacher complexity of $\mathcal{H}$ on a dataset $S = \{x_1, \dots, x_N\}$ is:

$$ \hat{\mathfrak{R}}_{S}(\mathcal{H}) = \mathbb{E}_{\sigma} \left[ \sup_{f \in \mathcal{H}} \frac{1}{N} \sum_{i=1}^{N} \sigma_i f(x_i) \right] \quad (26) $$

where $\mathbb{E}_{\sigma}$ denotes the expectation over the random variables $\sigma$.

**Definition 3.8 (Rademacher Complexity).** The Rademacher complexity of $\mathcal{H}$ for sample size $N$ is the expected value of the empirical Rademacher complexity over random samples of size $N$:

$$ \mathfrak{R}_N(\mathcal{H}) = \mathbb{E}_{S \sim \mathcal{P}^N} [\hat{\mathfrak{R}}_S(\mathcal{H})] \quad (27) $$

where $\mathcal{P}^N$ denotes the product distribution of $N$ i.i.d. samples from $\mathcal{P}$.
Intuitively, if a hypothesis class is complex enough to correlate with random noise labels $\sigma_i$, it has high capacity and is prone to overfitting.

**Theorem 3.5 (Rademacher Generalization Bound).** With probability at least $1 - \delta$, for all $f \in \mathcal{H}$:

$$ \mathcal{R}(f) \le \hat{\mathcal{R}}(f) + 2 \mathfrak{R}_N(\mathcal{H}) + \sqrt{\frac{\ln(1/\delta)}{2N}} \quad (28) $$

where $\mathcal{R}(f)$ is the expected risk, $\hat{\mathcal{R}}(f)$ is the empirical risk, and $\mathfrak{R}_N(\mathcal{H})$ is the Rademacher complexity.

*Proof Sketch.* The proof proceeds via symmetrization. Let $S = \{(x_i, y_i)\}_{i=1}^N$ be the training set and $S' = \{(x'_i, y'_i)\}_{i=1}^N$ be an independent “ghost” sample from the same distribution. By symmetry:

$$ \mathbb{E}_S[\mathcal{R}(f) - \hat{\mathcal{R}}_S(f)] = \mathbb{E}_{S,S'}[\hat{\mathcal{R}}_{S'}(f) - \hat{\mathcal{R}}_S(f)] \quad (29) $$

Introducing Rademacher variables $\sigma_i$ to randomly swap between $S$ and $S'$:

$$ \mathbb{E}_{S,S'}[\hat{\mathcal{R}}_{S'}(f) - \hat{\mathcal{R}}_S(f)] = \mathbb{E}_{S,S',\sigma}\left[\frac{1}{N}\sum_{i=1}^N \sigma_i(\ell(f(x'_i), y'_i) - \ell(f(x_i), y_i))\right] \quad (30) $$

Since the loss is bounded, this can be related to the Rademacher complexity. Applying concentration inequalities (McDiarmid) gives the high-probability bound. See [7] for the complete proof. □

This bound is often tighter than VC bounds for neural networks because it captures the geometric structure of the data and the function class. For example, for linear models with bounded $L_2$ norm, the Rademacher complexity decays with $1/\sqrt{N}$ independent of the dimension $d$, explaining why kernel methods and neural networks can generalize in high-dimensional spaces.

## 3.5 The Double Descent Phenomenon

Classical statistical learning theory suggests a U-shaped curve for test error as a function of model complexity: error decreases as bias decreases, then increases as variance increases. However, modern deep learning exhibits a “Double Descent” phenomenon. In the **Under-parameterized Regime**, the model is not complex enough to fit the data, resulting in high training and test error (bias dominates). In the **Critical Regime**, the model capacity is just enough to fit the training data (interpolation threshold). Here, the model is extremely sensitive to noise, and variance explodes, leading to poor generalization. Finally, in the **Over-parameterized Regime**, as capacity increases further, there are infinitely many solutions that fit the training data. The optimization algorithm (e.g., SGD) acts as an implicit regularizer, selecting the solution with the minimum norm (e.g., smoothest function), causing test error to decrease again, often below the minimum of the classical U-curve.

This phenomenon challenges traditional notions of model selection and emphasizes the role of implicit regularization. In Trustworthy AI, understanding this regime is crucial because over-parameterized models, while accurate, may be more susceptible to adversarial attacks or privacy leakage due to their capacity to memorize individual data points. A key lesson is that scale and capacity are not inherently bad for generalization; the training algorithm and implicit biases matter.
## 3.6 PAC Learning Framework

The Probably Approximately Correct (PAC) learning framework, introduced by Valiant (1984), provides a rigorous foundation for computational learning theory.

**Definition 3.9 (PAC Learnability).** A concept class $\mathcal{C}$ is PAC-learnable if there exists an algorithm $\mathcal{A}$ and a polynomial function $p(\cdot, \cdot, \cdot, \cdot)$ such that for every $\epsilon, \delta > 0$, every distribution $\mathcal{D}$ on $\mathcal{X}$, and every target concept $c \in \mathcal{C}$, given access to at least $m \ge p(1/\epsilon, 1/\delta, n, \text{size}(c))$ samples drawn i.i.d. from $\mathcal{D}$, $\mathcal{A}$ outputs a hypothesis $h$ satisfying:

$$P_{S \sim \mathcal{D}^m}[\mathcal{R}(h) \le \epsilon] \ge 1 - \delta \quad (31)$$

where $\mathcal{R}(h) = \mathbb{E}_{x \sim \mathcal{D}}[\mathbb{I}(h(x) \ne c(x))]$ is the true error (generalization error), $S$ is the training set of size $m$, and $n$ is the dimensionality of the input space.

The key elements are that the algorithm succeeds **Probably** (with probability $1 - \delta$), produces a hypothesis that is **Approximately** correct (with error at most $\epsilon$), and is **Correct** with respect to the true underlying concept.

**Theorem 3.6 (Sample Complexity of PAC Learning).** If $\mathcal{H}$ has VC dimension $d$, then for any $\epsilon, \delta > 0$, a sample of size:

$$m = O\left(\frac{d + \log(1/\delta)}{\epsilon}\right) \quad (32)$$

is sufficient for PAC learning. Furthermore, any PAC learning algorithm requires:

$$m = \Omega\left(\frac{d + \log(1/\delta)}{\epsilon}\right) \quad (33)$$

samples.

### 3.6.1 Agnostic PAC Learning

In the realizable setting, we assume $c \in \mathcal{C}$. The agnostic setting removes this assumption, competing with the best hypothesis in $\mathcal{H}$:

$$P[\mathcal{R}(h) \le \inf_{h' \in \mathcal{H}} \mathcal{R}(h') + \epsilon] \ge 1 - \delta \quad (34)$$

This is more realistic as we cannot guarantee the true function belongs to our hypothesis class.

## 3.7 Margin-Based Generalization Bounds

For classification problems, the margin of a classifier provides a more refined measure of confidence than just correctness.

**Definition 3.10 (Margin).** For a real-valued classifier $f: \mathcal{X} \to \mathbb{R}$ and label $y \in \{-1, +1\}$, the margin on example $(x, y)$ is:

$$\gamma(x, y) = y \cdot f(x) \quad (35)$$

A positive margin indicates correct classification; larger margins indicate higher confidence.

**Theorem 3.7 (Margin Bound).** Let $\mathcal{H}$ be a class of functions mapping to $[-1, 1]$. For any $\gamma > 0$, with probability at least $1 - \delta$:

$$\mathcal{R}_{0-1}(f) \le \hat{\mathcal{R}}_{\gamma}(f) + \frac{2}{\gamma} \mathfrak{R}_m(\mathcal{H}) + 3\sqrt{\frac{\log(2/\delta)}{2m}} \quad (36)$$

where $\hat{\mathcal{R}}_{\gamma}(f) = \frac{1}{m} \sum_{i=1}^{m} \mathbb{I}(y_i f(x_i) < \gamma)$ is the empirical margin loss, $\mathcal{R}_{0-1}(f)$ is the expected 0-1 loss, and $m$ is the sample size.
This bound explains why maximizing margins (as in SVMs) leads to better generalization. For neural networks, the implicit bias of gradient descent toward large margin solutions partially explains their generalization ability.

## 3.8 Algorithmic Stability

An alternative approach to generalization bounds relies on the stability of the learning algorithm rather than the complexity of the hypothesis class.

**Definition 3.11 (Uniform Stability).** An algorithm $\mathcal{A}$ is $\beta$-uniformly stable if for all datasets $S, S'$ differing in exactly one example:

$$ \sup_{(x,y)} |\ell(\mathcal{A}(S), (x, y)) - \ell(\mathcal{A}(S'), (x, y))| \le \beta \quad (37) $$

**Theorem 3.8 (Stability Bound).** If $\mathcal{A}$ is $\beta$-uniformly stable and $\ell \le M$, then with probability at least $1 - \delta$:

$$ \mathcal{R}(\mathcal{A}(S)) \le \hat{\mathcal{R}}(\mathcal{A}(S)) + 2\beta + (4m\beta + M)\sqrt{\frac{\ln(1/\delta)}{2m}} \quad (38) $$

where $m$ is the sample size, $M$ is the upper bound on the loss function, and $\beta$ is the stability parameter.

SGD with appropriate learning rates is known to be stable:

**Theorem 3.9 (SGD Stability).** For convex, L-Lipschitz loss functions, SGD with step size $\eta_t = 1/(Lt)$ run for $T$ iterations is $O(1/m)$-stable.

This provides generalization guarantees for deep learning without relying on explicit capacity measures.

## Exercises

1. **Bias-Variance Trade-off:** Consider a regression problem $y = \sin(2\pi x) + \epsilon$ where $\epsilon \sim N(0, 0.1)$.

(a) Generate a dataset of size $N = 10$.

(b) Fit polynomials of degree $d = 0, 1, \dots, 9$.

(c) Plot the training error and test error as a function of $d$.

(d) Decompose the error into bias and variance by repeating the experiment 100 times.

2. **VC Dimension:**

(a) Prove that the VC dimension of a linear classifier in $\mathbb{R}^d$ is $d + 1$.

(b) Prove that the VC dimension of the class of axis-aligned rectangles in $\mathbb{R}^2$ is 4.

(c) Construct a set of 3 points in $\mathbb{R}^2$ that cannot be shattered by axis-aligned rectangles.

3. **Rademacher Complexity:**

(a) Show that $\hat{\mathcal{R}}_S(\mathcal{H}) = \mathbb{E}_{\sigma}[\sup_{h \in \mathcal{H}} \frac{1}{N} \sum \sigma_i h(x_i)]$ satisfies the bounded difference inequality.

(b) Derive the Rademacher complexity for linear hypotheses with bounded $L_2$ norm.
4. **PAC Learning:**

(a) Prove that any finite hypothesis class $\mathcal{H}$ is PAC learnable with sample complexity
$m = O\left(\frac{\log |\mathcal{H}| + \log(1/\delta)}{\epsilon}\right)$.

(b) Implement the Consistent algorithm for learning axis-aligned rectangles.

(c) Verify empirically that the sample complexity matches the theoretical bound.

(d) Extend to the agnostic case and compare sample requirements.

5. **Margin Theory:**

(a) Train an SVM on a binary classification task with varying regularization.

(b) Compute the margin achieved by each model.

(c) Plot test accuracy vs. margin size and verify the theoretical relationship.

(d) Compare hard-margin and soft-margin SVM generalization.

6. **Algorithmic Stability:**

(a) Implement SGD with different learning rate schedules.

(b) Empirically measure stability by comparing models trained on datasets differing by
one sample.

(c) Verify that smaller learning rates lead to more stable algorithms.

(d) Compare stability of SGD vs. batch gradient descent.

7. **Double Descent:**

(a) Train models of increasing complexity on a fixed dataset (e.g., neural networks with varying widths).

(b) Plot training and test error as a function of model complexity.

(c) Identify the interpolation threshold where training error hits zero.

(d) Verify the double descent phenomenon: test error decreases again past the interpolation threshold.

8. **Generalization in Deep Learning:**

(a) Train a deep network with random labels ([36]).

(b) Compare training dynamics with true labels.

(c) Measure the effective capacity using a noise memorization metric.

(d) Discuss why traditional capacity bounds fail for deep networks.

9. **Concentration Inequalities:**

(a) Prove Hoeffding's inequality for bounded random variables.

(b) Use Hoeffding to derive a uniform convergence bound for finite hypothesis classes.

(c) Compare the tightness of Hoeffding vs. Bernstein bounds on empirical data.

(d) Apply McDiarmid's inequality to analyze the stability of cross-validation.
# 4 Adversarial Robustness

## 4.1 The Phenomenon of Adversarial Examples

The discovery that state-of-the-art deep neural networks are vulnerable to “adversarial examples”—inputs formed by applying small, often imperceptible perturbations to clean data that cause the model to make high-confidence errors—has shattered the illusion that these models learn human-like concepts. In the context of image classification, an adversary can add a specific noise pattern to an image of a panda, such that the modified image looks identical to the human eye but is classified by the network as a gibbon with 99.9% confidence. This vulnerability is not specific to computer vision; it pervades natural language processing, speech recognition, and reinforcement learning.

The existence of adversarial examples poses a severe security risk for safety-critical applications. In autonomous driving, a stop sign with a few malicious stickers could be misinterpreted as a speed limit sign, leading to catastrophic accidents. In financial fraud detection, sophisticated attackers could modify transaction patterns to evade detection. Therefore, understanding the mathematical nature of these vulnerabilities and developing robust defenses is a prerequisite for the deployment of AI in the real world.

## 4.2 High-Dimensional Geometry and Concentration

Early hypotheses suggested that adversarial examples were a result of “overfitting” or the extreme non-linearity of deep networks. However, [16] proposed the “Linearity Hypothesis”, arguing that the vulnerability arises from the model being too linear in high-dimensional spaces. This is a remarkable insight: neural networks are vulnerable not because they are too complex, but because they are too simple in the geometric structure they learn.

**Theorem 4.1 (Linearity Hypothesis).** Consider a linear model $f(x) = w^T x$. Let $\eta$ be a perturbation bounded in $L_\infty$ norm: $\|\eta\|_\infty \le \epsilon$. The change in the model's output is $w^T \eta$. To maximize this change under the $L_\infty$ constraint, the adversary should choose each component of $\eta$ to align with the sign of the corresponding weight:

$$ \eta = \epsilon \cdot \text{sign}(w), \quad \Delta = w^T \eta = \epsilon \sum_{i=1}^{d} |w_i| = \epsilon \|w\|_1 \quad (39) $$

where $\text{sign}(w)$ is the element-wise sign function, $d$ is the dimensionality of the input, and $\|w\|_1$ is the $L_1$ norm of the weight vector. If the weights are independent with typical magnitude $m$, then $\|w\|_1 \approx d \cdot m$. Thus, the output change scales linearly with the dimension $d$. In high-dimensional spaces (e.g., a 224 × 224 RGB image has $d \approx 150,000$), even if each weight is small ($m = O(1)$), the total effect can be huge. A perturbation of $\epsilon = 1/255$ per pixel (imperceptible) causes $\Delta \approx 600$, easily crossing any decision boundary.

**Extension to Neural Networks:** While real neural networks are nonlinear, if the local approximation around a data point is nearly linear (as is often the case when weights are not trained to be highly nonlinear), the same principle applies. The model's decision boundary can be expressed locally as a hyperplane, and adversarial perturbations along the normal direction to this hyperplane cause large changes in output.

More formally, adversarial examples are related to the **Concentration of Measure** phenomenon. In high-dimensional spaces, probability mass is not distributed uniformly; it concentrates in unexpected ways. For a unit sphere $S^{d-1}$, most of the measure is concentrated near the equator
defined by any fixed hyperplane. This means that if a classifier's decision boundary passes through the typical data region, a randomly chosen point is likely very close to the boundary (in Euclidean distance) even though the input space is enormous. The Isoperimetric Inequality formalizes this: if a set A covers at least half the measure of the sphere, then expanding A by a small distance $\epsilon$ covers almost the entire sphere. Conversely, for any classifier with non-trivial error rate $p > 0$, the set of misclassified points has measure at least $p$, and is thus at distance at most $O(\sqrt{\log(1/p)/d})$ from the correctly classified points. The curse of dimensionality means this distance is vanishingly small as $d$ grows.

## 4.3 Taxonomy of Adversarial Attacks

Adversarial attacks can be categorized based on the attacker's knowledge and goals.

<table><caption>Table 2: Taxonomy of Adversarial Attacks</caption><thead><tr><th>Dimension</th><th>Description</th></tr></thead><tbody><tr><td><strong>Knowledge</strong></td><td></td></tr><tr><td>White-box</td><td>Attacker has full access to model weights, architecture, and gradients.</td></tr><tr><td>Black-box</td><td>Attacker only has query access (probabilities or hard labels).</td></tr><tr><td>Gray-box</td><td>Attacker has partial knowledge (e.g., architecture but not weights).</td></tr><tr><td><strong>Goal</strong></td><td></td></tr><tr><td>Targeted</td><td>Misclassify input <i>x</i> as a specific target class <i>y</i><sub>target</sub>.</td></tr><tr><td>Untargeted</td><td>Misclassify input <i>x</i> as any class <i>y</i> ≠ <i>y</i><sub>true</sub>.</td></tr><tr><td><strong>Constraint</strong></td><td></td></tr><tr><td><i>L</i><sub>∞</sub></td><td>Maximum change to any single pixel is bounded (imperceptibility).</td></tr><tr><td><i>L</i><sub>2</sub></td><td>Euclidean distance is bounded.</td></tr><tr><td><i>L</i><sub>0</sub></td><td>Number of modified pixels is bounded (sparse attack).</td></tr><tr><td>Physical</td><td>Perturbations must be realizable in the physical world (e.g., stickers).</td></tr></tbody></table>

## 4.4 White-Box Attacks

In the white-box setting, the attacker has complete knowledge of the model architecture, parameters $\theta$, and can compute gradients $\nabla_x \ell(f_\theta(x), y)$. This represents the strongest threat model and provides upper bounds on attack effectiveness.

### 4.4.1 Theoretical Foundation: First-Order Adversaries

The core insight behind gradient-based attacks is that neural network loss landscapes are locally linear in the input space. For a differentiable loss function $\ell$, the first-order Taylor expansion around input $x$ gives:

$$ \ell(f_{\theta}(x + \delta), y) \approx \ell(f_{\theta}(x), y) + \langle \nabla_x \ell(f_{\theta}(x), y), \delta \rangle + O(\|\delta\|^2) \quad (40) $$

where $\langle \cdot, \cdot \rangle$ denotes the inner product, $\nabla_x$ is the gradient with respect to the input $x$, and $O(\|\delta\|^2)$ represents higher-order terms that are negligible for small $\delta$.
To maximize this linear approximation subject to $||\delta||_p \le \epsilon$, we solve:

$$ \delta^* = \arg\max_{||\delta||_p \le \epsilon} \langle g, \delta \rangle \quad \text{where} \quad g = \nabla_x \ell(f_\theta(x), y) \qquad (41) $$

where $|| \cdot ||_p$ is the $L_p$ norm.

The solution depends on the choice of $L_p$ norm constraint:

**Proposition 4.2 (Optimal First-Order Perturbation).** For gradient $g \in \mathbb{R}^d$ and constraint $||\delta||_p \le \epsilon$:

1. $L_\infty$ constraint: $\delta^* = \epsilon \cdot \text{sign}(g)$, achieving $\langle g, \delta^* \rangle = \epsilon ||g||_1$

2. $L_2$ constraint: $\delta^* = \epsilon \cdot \frac{g}{||g||_2}$, achieving $\langle g, \delta^* \rangle = \epsilon ||g||_2$

3. $L_1$ constraint: $\delta^* = \epsilon \cdot e_{i^*} \cdot \text{sign}(g_{i^*})$ where $e_{i^*} = \arg\max_i |g_i|$, achieving $\langle g, \delta^* \rangle = \epsilon ||g||_\infty$

*Proof.* We use Hölder's inequality: $|\langle g, \delta \rangle| \le ||g||_q ||\delta||_p$ where $\frac{1}{p} + \frac{1}{q} = 1$. Equality holds when $\delta$ is aligned with $g$ in the dual norm sense.

**Case 1 ($L_\infty$ constraint, $p = \infty$, $q = 1$):** We have $\langle g, \delta \rangle \le ||g||_1 ||\delta||_\infty \le \epsilon ||g||_1$. To achieve equality, set $\delta_i = \epsilon \cdot \text{sign}(g_i)$. Then:

$$ \langle g, \delta \rangle = \sum_{i=1}^{d} g_i \cdot \epsilon \cdot \text{sign}(g_i) = \epsilon \sum_{i=1}^{d} |g_i| = \epsilon ||g||_1 \qquad (42) $$

**Case 2 ($L_2$ constraint, $p = q = 2$):** By Cauchy-Schwarz, $\langle g, \delta \rangle \le ||g||_2 ||\delta||_2 \le \epsilon ||g||_2$. Equality holds when $\delta = \epsilon \frac{g}{||g||_2}$:

$$ \langle g, \delta \rangle = \left\langle g, \epsilon \frac{g}{||g||_2} \right\rangle = \frac{\epsilon}{||g||_2} ||g||_2^2 = \epsilon ||g||_2 \qquad (43) $$

**Case 3 ($L_1$ constraint, $p = 1$, $q = \infty$):** We have $\langle g, \delta \rangle \le ||g||_\infty ||\delta||_1 \le \epsilon ||g||_\infty$. To achieve equality, place all mass on the coordinate with largest $|g_i|$: let $i^* = \arg\max_i |g_i|$, set $\delta_{i^*} = \epsilon \cdot \text{sign}(g_{i^*})$ and $\delta_i = 0$ for $i \ne i^*$. Then $||\delta||_1 = \epsilon$ and:

$$ \langle g, \delta \rangle = g_{i^*} \cdot \epsilon \cdot \text{sign}(g_{i^*}) = \epsilon |g_{i^*}| = \epsilon ||g||_\infty \qquad (44) $$

□

### 4.4.2 Fast Gradient Sign Method (FGSM)

FGSM [16] is the canonical one-step attack for $L_\infty$ perturbations:

$$ x_{adv} = x + \epsilon \cdot \text{sign}(\nabla_x \ell(f_\theta(x), y)) \qquad (45) $$

where $x_{adv}$ is the adversarial example, $x$ is the original input, $\epsilon$ is the perturbation magnitude, and $\text{sign}(\cdot)$ is the element-wise sign function.

**Remark 4.1 (Geometric Interpretation).** FGSM moves in the direction that maximizes the linear approximation of the loss. The sign function projects onto the vertices of the $L_\infty$ ball, making each pixel change by exactly $\pm \epsilon$. This is optimal for the linearized problem but may be suboptimal for the true (nonlinear) loss.
**Proposition 4.3 (FGSM Loss Increase).** For a loss function with Lipschitz constant $L$ in $L_\infty$ norm, FGSM achieves:

$$ \ell(f_{\theta}(x_{adv}), y) - \ell(f_{\theta}(x), y) \geq \epsilon \|\nabla_x \ell\|_1 - \frac{L\epsilon^2 d}{2} \quad (46) $$

where $d$ is the input dimension.

*Proof.* By Taylor expansion around $x$:

$$ \ell(f_{\theta}(x_{adv}), y) = \ell(f_{\theta}(x), y) + \langle \nabla_x \ell, x_{adv} - x \rangle + O(\|x_{adv} - x\|^2) \quad (47) $$

For FGSM, $x_{adv} - x = \epsilon \cdot \text{sign}(\nabla_x \ell)$, so:

$$ \langle \nabla_x \ell, \epsilon \cdot \text{sign}(\nabla_x \ell) \rangle = \epsilon \sum_{i=1}^{d} |(\nabla_x \ell)_i| = \epsilon \|\nabla_x \ell\|_1 \quad (48) $$

For the second-order term, if $\ell$ has Lipschitz continuous gradients with constant $L$ in $L_\infty$ norm:

$$ |\ell(f_{\theta}(x_{adv}), y) - \ell(f_{\theta}(x), y) - \langle \nabla_x \ell, x_{adv} - x \rangle| \leq \frac{L}{2} \|x_{adv} - x\|_{\infty}^2 \cdot d \quad (49) $$

Since $\|x_{adv} - x\|_{\infty} = \epsilon$, we get the stated bound. □

The computational efficiency of FGSM (single forward-backward pass) makes it suitable for generating large-scale adversarial training data.

### 4.4.3 Projected Gradient Descent (PGD)

PGD [24] is the multi-step extension of FGSM that iteratively refines the adversarial perturbation:

$$ x^{t+1} = \Pi_{B_{\epsilon}(x)} (x^t + \alpha \cdot \text{sign}(\nabla_x \ell(f_{\theta}(x^t), y))) \quad (50) $$

where $\Pi_{B_{\epsilon}(x)}$ projects onto the $\epsilon$-ball: $\Pi_{B_{\epsilon}(x)}(z) = x + \text{clip}(z - x, -\epsilon, \epsilon)$, $x^t$ is the adversarial example at iteration $t$, and $\alpha$ is the step size.

<caption>**Algorithm 1 Projected Gradient Descent (PGD) Attack**</caption>

Input: $x, y, \theta, \epsilon, \alpha, T$
$x^0 \leftarrow x + \mathcal{U}(-\epsilon, \epsilon)$ {Random Start}
for $t = 1$ to $T$ do
$g \leftarrow \nabla_x \ell(f_{\theta}(x^{t-1}), y)$
$x^t \leftarrow \Pi_{B_{\epsilon}(x)}(x^{t-1} + \alpha \cdot \text{sign}(g))$
end for
return $x^T$

**Theorem 4.4 (PGD Convergence).** For an $L$-smooth loss function and step size $\alpha \le \frac{1}{L}$, PGD converges to a stationary point of the constrained maximization problem. Specifically, the squared norm of the gradient mapping decays as:

$$ \min_{t \le T} \left\| \frac{x^{t+1} - x^t}{\alpha} \right\|_2^2 \le \frac{2L(\ell(x^*) - \ell(x^0))}{T} \quad (51) $$

where $x^*$ is a global maximum.
**Remark 4.2** (Random Restarts). PGD with random restarts runs multiple independent attacks from different initializations and returns the best. This helps escape local maxima and provides stronger attacks. Empirically, 10-20 restarts often suffice for most images.

**Proposition 4.5** (Attack Strength Hierarchy). For identical perturbation budgets $\epsilon$:

$$ \text{Success}(\text{FGSM}) \le \text{Success}(\text{PGD}) \le \text{Success}(\text{PGD-Restarts}) \le \text{Success}(\text{C\&W}) \quad (52) $$

The gap between FGSM and PGD is larger for robust models trained with adversarial training.

### 4.4.4 Carlini & Wagner (C&W) Attack

The C&W attack [9] finds minimum-norm perturbations by reformulating the attack as an unconstrained optimization problem.

**Definition 4.1** (C&W Objective). The attack minimizes:

$$ \min_{\delta} \|\delta\|_2^2 + c \cdot f(x + \delta) \quad (53) $$

where $c > 0$ is a constant balancing the perturbation size and the misclassification success, and $f$ is a surrogate objective for misclassification:

$$ f(x') = \max(\max_{i \neq t} Z(x')_i - Z(x')_t, -\kappa) \quad (54) $$

Here $Z(x')$ are the logits (pre-softmax outputs), $t$ is the target class, and $\kappa \ge 0$ is a confidence parameter.

**Remark 4.3** (Change of Variables). To ensure $x+\delta \in [0, 1]^d$ (valid pixel range), C&W introduces:

$$ \delta = \frac{1}{2}(\tanh(w) + 1) - x \quad (55) $$

and optimizes over unconstrained $w \in \mathbb{R}^d$. This guarantees box constraints are always satisfied.

**Proposition 4.6** (C&W Optimality). For the $L_2$ attack, C&W finds perturbations that are on average 10× smaller than PGD perturbations for the same attack success rate. However, it requires ~10,000 optimization steps per image.

### 4.4.5 AutoAttack: Reliable Evaluation

AutoAttack [13] combines multiple attacks for reliable robustness evaluation:

1. **APGD-CE**: Auto-PGD with cross-entropy loss and adaptive step sizes

2. **APGD-DLR**: Auto-PGD with Difference of Logits Ratio loss

3. **FAB**: Fast Adaptive Boundary attack

4. **Square Attack**: Score-based black-box attack

**Theorem 4.7** (AutoAttack Completeness). AutoAttack provides a lower bound on adversarial accuracy that is tight up to 0.1% for most defenses tested on standard benchmarks. Any defense claiming higher robustness should be evaluated against AutoAttack.
## 4.5 Black-Box Attacks

In the black-box setting, the attacker cannot access model gradients or architecture. This is the more realistic threat model for deployed systems.

### 4.5.1 Transfer Attacks

Transfer attacks exploit the phenomenon that adversarial examples generated for one model often fool other models.

**Definition 4.2** (Adversarial Transferability). An adversarial example $x_{adv}$ generated against source model $f_s$ transfers to target model $f_t$ if:

$$f_s(x_{adv}) \neq y \implies f_t(x_{adv}) \neq y \qquad (56)$$

The transfer rate is $P(f_t(x_{adv}) \neq y | f_s(x_{adv}) \neq y)$, where P denotes probability.

**Theorem 4.8** (Transferability Conditions). Adversarial examples transfer more reliably when:

1. Source and target models have similar decision boundaries

2. The perturbation exploits input features rather than model-specific artifacts

3. Ensemble methods are used: $x_{adv} = \arg \max_{\|\delta\| \le \epsilon} \sum_{i=1}^{K} w_i \ell(f_i(x + \delta), y)$

### 4.5.2 Query-Based Attacks

Query-based attacks estimate gradients through model queries.

**Definition 4.3** (Zeroth-Order Gradient Estimation). The gradient can be approximated using finite differences:

$$\hat{g}_i = \frac{f(x + \mu e_i) - f(x - \mu e_i)}{2\mu} \qquad (57)$$

where $e_i$ is the i-th standard basis vector and $\mu > 0$ is the step size.

This requires $O(d)$ queries per gradient estimate where $d$ is input dimension—prohibitively expensive for images.

**Proposition 4.9** (Random Direction Gradient Estimation). A more efficient estimator uses random directions $u \sim N(0, I)$:

$$\hat{g} = \frac{d}{\mu} \cdot (f(x + \mu u) - f(x)) \cdot u \qquad (58)$$

This provides an unbiased estimate: $\mathbb{E}[\hat{g}] = \nabla f(x)$ with $O(1)$ queries per estimate.

### 4.5.3 Score-Based Attacks: Square Attack

Square Attack [5] uses random search without gradient estimation:

**Proposition 4.10** (Query Efficiency). Square Attack achieves comparable success rates to PGD with only $\sim 1000-5000$ queries, making it practical for attacking real-world APIs.
**Algorithm 2** NES (Natural Evolution Strategies) Attack

Input: $x, y, f, \epsilon, \alpha, T, n$
$\delta^0 \leftarrow 0$

for $t=1$ to $T$ do

Sample $u_1, \dots, u_n \sim \mathcal{N}(0, I)$

$\hat{g} \leftarrow \frac{1}{n\sigma} \sum_{i=1}^{n} (f(x + \delta^{t-1} + \sigma u_i) - f(x + \delta^{t-1} - \sigma u_i)) \cdot u_i$

$\delta^t \leftarrow \Pi_{B_\epsilon}(\delta^{t-1} + \alpha \cdot \text{sign}(\hat{g}))$

end for

return $x + \delta^T$

**Algorithm 3** Square Attack

Input: $x, y, f, \epsilon, T$

Initialize $\delta$ with random $\pm \epsilon$ values

for $t=1$ to $T$ do

Sample random square region $S$ of size $p \times p$

Sample new values $v \in \{-\epsilon, +\epsilon\}^{p \times p}$

$\delta' \leftarrow \delta$; set $\delta'_S \leftarrow v$

if $\ell(f(x + \delta'), y) > \ell(f(x + \delta), y)$ then

$\delta \leftarrow \delta' \{\text{Accept update}\}$

end if

end for

return $x + \delta$

## 4.6 Adversarial Training and Robust Optimization

The most effective defense against adversarial attacks is Adversarial Training. We formalize robustness as a min-max saddle point problem. The goal is to find model parameters $\theta$ that minimize the loss on the worst-case perturbations within the allowed set $S$.

$$ \theta^* = \arg\min_{\theta} \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \max_{\delta \in \mathcal{S}} \ell(f_{\theta}(x + \delta), y) \right] \quad (59) $$

where $S = \{\delta: \|\delta\|_p \le \epsilon\}$ is the set of allowed perturbations, $\mathcal{D}$ is the data distribution, and $\theta$ represents the model parameters. This formulation views training as a zero-sum game between the trainer (minimizer) and the attacker (maximizer).

### 4.6.1 Game-Theoretic Interpretation

**Definition 4.4 (Zero-Sum Game).** Adversarial training corresponds to finding a Nash equilibrium of the zero-sum game:

$$ (\theta^*, \delta^*) = \text{Nash} \left( \min_{\theta} \max_{\delta} \ell(f_{\theta}(x + \delta), y) \right) \quad (60) $$

At equilibrium, neither player can improve by unilateral deviation.

**Theorem 4.11 (Minimax Theorem).** For convex-concave objectives where $\ell(\cdot, \delta)$ is convex in $\theta$ and $\ell(\theta, \cdot)$ is concave in $\delta$:

$$ \min_{\theta} \max_{\delta} \ell(f_{\theta}(x + \delta), y) = \max_{\delta} \min_{\theta} \ell(f_{\theta}(x + \delta), y) \quad (61) $$

The order of optimization does not matter.
**Remark 4.4** (Non-Convexity in Practice). Neural network losses are non-convex in $\theta$, so the minimax theorem does not directly apply. Adversarial training uses alternating optimization: fix $\theta$, maximize over $\delta$ (PGD attack); fix $\delta^*$, minimize over $\theta$ (gradient descent).

### 4.6.2 Danskin's Theorem and Training Dynamics

To optimize the outer minimization via Gradient Descent, we need to compute the gradient of the value function $V(\theta) = \max_{\delta \in S} \ell(f_{\theta}(x + \delta), y)$. The challenge is that the max operator is not differentiable everywhere. Danskin's theorem provides a solution by showing that the gradient of the max is the gradient at the maximizing point.

**Theorem 4.12** (Danskin's Theorem). Let $\Phi: \Theta \times S \to \mathbb{R}$ be a continuous function where $S$ is a compact set. Define the value function:

$$V(\theta) = \max_{\delta \in S} \Phi(\theta, \delta) \qquad (62)$$

Let $\delta^*(\theta) = \arg \max_{\delta \in S} \Phi(\theta, \delta)$. If:

1. $\Phi$ is continuously differentiable in $\theta$ for each $\delta$

2. $\delta^*(\theta)$ is unique

Then $V(\theta)$ is differentiable and:

$$\nabla_{\theta} V(\theta) = \nabla_{\theta} \Phi(\theta, \delta^*(\theta)) \qquad (63)$$

*Proof Sketch.* By the envelope theorem from optimization theory. Consider a small perturbation $\theta' = \theta + \epsilon h$:

$$V(\theta') - V(\theta) = \max_{\delta} \Phi(\theta', \delta) - \max_{\delta} \Phi(\theta, \delta) \qquad (64)$$

$$= \Phi(\theta', \delta^*(\theta')) - \Phi(\theta, \delta^*(\theta)) \qquad (65)$$

By continuity of $\delta^*$ and differentiability of $\Phi$, taking the limit as $\epsilon \to 0$ gives the result. The key insight is that at the optimum, the derivative with respect to $\delta$ is zero (by first-order optimality conditions), so only the direct effect through $\theta$ remains. $\square$

**Remark 4.5** (Application to Adversarial Training). This theorem provides the theoretical justification for adversarial training: to update the model weights, we simply find the optimal adversarial example $\delta^*$ (using PGD) and then compute the gradient of the loss at that perturbed point. By Danskin's theorem, this is the gradient of the robust objective $\max_{\|\delta\| \le \epsilon} \ell(f_{\theta}(x + \delta), y)$ with respect to $\theta$.

### 4.6.3 TRADES: Trading Off Robustness and Accuracy

TRADES [37] decomposes the robust error into a natural error term and a boundary error term.

**Definition 4.5** (TRADES Objective). The TRADES algorithm minimizes a surrogate loss that balances natural accuracy and local Lipschitz continuity (robustness):

$$\mathcal{L}_{\text{TRADES}} = \ell(f_{\theta}(x), y) + \beta \cdot \max_{\|\delta\| \le \epsilon} D_{KL}(f_{\theta}(x) \| f_{\theta}(x + \delta)) \qquad (66)$$

where $\beta > 0$ controls the trade-off, $D_{KL}$ is the Kullback-Leibler divergence, and $\epsilon$ is the perturbation radius. The first term encourages the model to be accurate on clean data, while the second term (regularizer) pushes the decision boundary away from the data points by penalizing changes in the output distribution within the $\epsilon$-ball.
This formulation is motivated by a theoretical bound on the robust error, where the KL divergence serves as a differentiable proxy for the condition that the prediction should not change within the perturbation radius. Higher $\beta$ yields more robust but potentially less accurate models on clean data.

## 4.7 Certified Robustness via Randomized Smoothing

While PGD provides empirical robustness, it offers no guarantees. A stronger adversary might still find a loophole. Certified robustness aims to provide a mathematical proof that for a given input $x$, no perturbation within radius $R$ can change the label. Randomized smoothing is a scalable technique that converts any base classifier $f$ into a smoothed classifier $g$ that is certifiably robust in $L_2$ norm.

**Definition 4.6 (Smoothed Classifier).** Let $f: \mathbb{R}^d \to \mathcal{Y}$ be a base classifier (which need not be robust). The smoothed classifier $g$ is defined as the majority vote of $f$ under Gaussian noise:

$$g(x) = \arg \max_{c \in \mathcal{Y}} P_{\epsilon \sim \mathcal{N}(0, \sigma^2 I)}(f(x + \epsilon) = c) \quad (67)$$

where $\mathcal{N}(0, \sigma^2 I)$ is a multivariate Gaussian distribution with mean 0 and covariance $\sigma^2 I$, and $P$ denotes probability.

**Theorem 4.13 (Certification [12]).** Suppose we estimate that class $c_A$ has probability $p_A = P(f(x + \epsilon) = c_A)$ and the runner-up class has probability $p_B = \max_{c \neq c_A} P(f(x + \epsilon) = c)$. If $p_A > p_B$, then the smoothed classifier $g(x)$ is provably robust within an $L_2$ radius $R$ [12]:

$$R = \frac{\sigma}{2}(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)) \quad (68)$$

where $\Phi^{-1}$ is the inverse CDF of the standard normal distribution.

*Proof Sketch.* The key insight is that for any perturbation $\|\delta\|_2 \le R$, we need to show $P(f(x + \delta + \epsilon) = c_A) > P(f(x + \delta + \epsilon) = c_B)$ for all classes $c_B \neq c_A$, where $\epsilon \sim \mathcal{N}(0, \sigma^2 I)$.

Consider the worst-case perturbation $\delta$ with $\|\delta\|_2 = R$. By the Neyman-Pearson lemma, the optimal decision boundary for distinguishing between $\mathcal{N}(0, \sigma^2 I)$ and $\mathcal{N}(\delta, \sigma^2 I)$ is a hyperplane perpendicular to $\delta$. The perturbation $\delta$ shifts the Gaussian, and we need to compute how much probability mass crosses from class A to class B.

For a fixed direction (without loss of generality, take $\delta = R \cdot e_1$), let $Z \sim \mathcal{N}(0, \sigma^2)$ be the projection onto the first coordinate. At the original point $x$:

$$P(f(x + \epsilon) = c_A) = P(Z > t_A) = \Phi\left(\frac{-t_A}{\sigma}\right) \quad (69)$$

$$P(f(x + \epsilon) = c_B) = P(Z > t_B) = \Phi\left(\frac{-t_B}{\sigma}\right) \quad (70)$$

for some thresholds $t_A, t_B$. After perturbation by $\delta$, the Gaussian shifts by $R$:

$$P(f(x + \delta + \epsilon) = c_A) = \Phi\left(\frac{R - t_A}{\sigma}\right) \quad (71)$$

$$P(f(x + \delta + \epsilon) = c_B) = \Phi\left(\frac{R - t_B}{\sigma}\right) \quad (72)$$

For $P(f(x + \delta + \epsilon) = c_A) > P(f(x + \delta + \epsilon) = c_B)$, we need:

$$\Phi\left(\frac{R - t_A}{\sigma}\right) > \Phi\left(\frac{R - t_B}{\sigma}\right) \Rightarrow R < t_B - t_A \quad (73)$$
Setting $\Phi(-t_A/\sigma) = p_A$ and $\Phi(-t_B/\sigma) = p_B$ gives $t_A = -\sigma\Phi^{-1}(p_A)$ and $t_B = -\sigma\Phi^{-1}(p_B)$. Thus:

$$R < \sigma(\Phi^{-1}(p_B) - \Phi^{-1}(p_A)) = \frac{\sigma}{2}(\Phi^{-1}(p_A) - \Phi^{-1}(p_B)) \quad (74)$$

The factor of 1/2 arises from considering the worst-case perturbation direction. See [12] for the complete proof. □

## Exercises

### 1. FGSM vs PGD:

(a) Implement the Fast Gradient Sign Method (FGSM) and PGD on the MNIST dataset.

(b) Plot the robust accuracy as a function of $\epsilon$ for both attacks.

(c) Why is PGD considered a stronger attack than FGSM?

(d) Compare the running time of FGSM vs. PGD for the same perturbation budget.

### 2. Lipschitz Constant:

(a) Compute the Lipschitz constant of a single linear layer $f(x) = Wx$.

(b) Compute the Lipschitz constant of the ReLU activation function.

(c) Show that the Lipschitz constant of a deep network is upper bounded by the product of the spectral norms of its weight matrices.

(d) Implement spectral normalization and verify it constrains the Lipschitz constant.

### 3. Randomized Smoothing:

(a) Prove that if $f(x)$ is the base classifier, the smoothed classifier $g(x)$ is Lipschitz continuous.

(b) Calculate the certified radius for a point $x$ if $p_A = 0.99$ and $\sigma = 0.25$.

(c) Implement randomized smoothing certification and plot the certified accuracy vs. radius trade-off.

### 4. Adversarial Training:

(a) Implement adversarial training with PGD for CIFAR-10.

(b) Compare the clean accuracy and robust accuracy before and after adversarial training.

(c) Investigate the accuracy-robustness trade-off: plot clean accuracy vs. robust accuracy for different $\epsilon$ values during training.

(d) Examine what features the adversarially trained model learns by visualizing filters.

### 5. Transferability Analysis:

(a) Train three different architectures (ResNet, VGG, DenseNet) on CIFAR-10.

(b) Generate adversarial examples for each model.

(c) Test each set of adversarial examples on all three models.

(d) Construct a transferability matrix and analyze which model pairs have highest transfer rates.

### 6. Black-Box Attacks:

(a) Implement the Square Attack algorithm.
(b) Compare its query efficiency with zeroth-order gradient estimation methods.

(c) How does the attack success rate change with the number of queries?

7. Certified Defense Evaluation:

(a) Train a model with certified training (IBP or CROWN-IBP).

(b) Compare its certified accuracy with empirical PGD accuracy.

(c) Why might there be a gap between certified and empirical robustness?

8. FGSM and Variants:

(a) Implement the basic FGSM attack: $x' = x + \epsilon \cdot \operatorname{sign}(\nabla_x \ell)$.

(b) Implement targeted FGSM that forces misclassification to a specific class.

(c) Implement I-FGSM (iterative FGSM) with step size $\alpha$ and iterations $T$.

(d) Compare attack success rates and perturbation magnitudes across variants.

9. C&W Attack:

(a) Implement the Carlini & Wagner $L_2$ attack with variable $w$ and binary search over $c$.

(b) Compare with PGD in terms of perturbation size and attack success rate.

(c) Implement the $L_\infty$ variant and compare effectiveness.

(d) Test against a defended model and analyze the difference in required perturbation.

10. AutoAttack Benchmark:

(a) Evaluate a robust model using the AutoAttack benchmark.

(b) Compare accuracy under APGD-CE, APGD-T, FAB, and Square attacks.

(c) Analyze which attack is most effective for your model architecture.

(d) Implement a simple “robust” defense and test if AutoAttack breaks it.

11. Physical Adversarial Attacks:

(a) Implement the Expectation over Transformation (EOT) attack.

(b) Generate an adversarial patch that remains effective under affine transformations.

(c) Test robustness to printing and photographing the adversarial example.

(d) Analyze the trade-off between physical robustness and perturbation magnitude.

12. Adversarial Training Variants:

(a) Implement TRADES: trade-off between accuracy and robustness.

(b) Compare clean/robust accuracy of AT, TRADES, and MART.

(c) Implement Friendly Adversarial Training (FAT) with early stopping.

(d) Analyze the effect of perturbation budget scheduling during training.

4.8 Natural Distribution Shifts and Domain Adaptation

While adversarial perturbations represent worst-case distribution shifts, natural distribution
shifts arise from legitimate changes in the data-generating process. These are often more relevant
in practice.
### 4.8.1 Types of Natural Distribution Shift

**Definition 4.7** (Distribution Shift Taxonomy). Let $P_S(X, Y)$ be the source distribution and $P_T(X, Y)$ the target distribution. We distinguish between four primary types of shift. **Covariate Shift** occurs when the input distribution changes ($P_T(X) \neq P_S(X)$), but the conditional label distribution remains constant ($P_T(Y|X) = P_S(Y|X)$). **Label Shift** is the converse, where the marginal label distribution changes ($P_T(Y) \neq P_S(Y)$), but the class-conditional input distribution is preserved ($P_T(X|Y) = P_S(X|Y)$). **Concept Drift** refers to a fundamental change in the relationship between inputs and outputs ($P_T(Y|X) \neq P_S(Y|X)$). Finally, **Domain Shift** encompasses the general case where both marginal and conditional distributions differ.

### 4.8.2 Importance Weighting for Covariate Shift

Under covariate shift, the optimal predictor remains the same, but the empirical risk estimator is biased. We can correct this via importance weighting:

$$ \hat{R}_T(f) = \frac{1}{n} \sum_{i=1}^{n} \frac{P_T(x_i)}{P_S(x_i)} \ell(f(x_i), y_i) \qquad (75) $$

where $n$ is the number of samples, $P_T(x_i)$ and $P_S(x_i)$ are the target and source densities evaluated at $x_i$, and $\ell$ is the loss function.

The density ratio $w(x) = P_T(x)/P_S(x)$ can be estimated without estimating the densities directly using kernel mean matching or discriminative methods.

**Theorem 4.14** (Consistency Under Covariate Shift). If $P_T(Y|X) = P_S(Y|X)$ and the importance weights are correctly specified, then the importance-weighted empirical risk is an unbiased estimator of the target risk:

$$ \mathbb{E}_{P_S}[w(X)\ell(f(X), Y)] = \mathbb{E}_{P_T}[\ell(f(X), Y)] \qquad (76) $$

*Proof.* By definition of the importance weight $w(x) = P_T(x)/P_S(x)$ and the tower property of expectation:

$$ \mathbb{E}_{P_S}[w(X)\ell(f(X), Y)] = \mathbb{E}_{P_S}\left[\frac{P_T(X)}{P_S(X)}\ell(f(X), Y)\right] \qquad (77) $$

$$ = \iint \frac{P_T(x)}{P_S(x)} \ell(f(x), y) P_S(y|x) P_S(x) dy dx \qquad (78) $$

$$ = \iint \ell(f(x), y) P_S(y|x) P_T(x) dy dx \qquad (79) $$

Under the covariate shift assumption $P_S(Y|X) = P_T(Y|X)$:

$$ = \iint \ell(f(x), y) P_T(y|x) P_T(x) dy dx = \mathbb{E}_{P_T}[\ell(f(X), Y)] \qquad (80) $$

□

### 4.8.3 Domain Adversarial Training

Domain Adversarial Neural Networks (DANN) learn representations that are predictive of $Y$ but invariant to the domain $D$.

The architecture consists of:
* Feature extractor: $G_f: \mathcal{X} \to \mathcal{Z}$

* Label predictor: $G_y: \mathcal{Z} \to \mathcal{Y}$

* Domain classifier: $G_d: \mathcal{Z} \to \{S, T\}$

The objective combines supervised loss and adversarial domain loss:

$$ \min_{G_f, G_y} \max_{G_d} \mathbb{E}_{(x,y) \sim P_S} [\ell(G_y(G_f(x)), y)] - \lambda \mathbb{E}_{x \sim P_S \cup P_T} [\ell_d(G_d(G_f(x)), d)] \quad (81) $$

where $\lambda > 0$ is a hyperparameter balancing the classification and domain confusion objectives, $\ell$ is the task loss, and $\ell_d$ is the domain classification loss.

The Gradient Reversal Layer (GRL) enables end-to-end training by negating gradients from the domain classifier.

### 4.8.4 Invariant Risk Minimization (IRM)

IRM seeks representations such that the optimal classifier on top is invariant across environments.

**Definition 4.8 (Invariant Representation).** A representation $\Phi$ elicits an invariant predictor $w$ if $w$ is simultaneously optimal for all environments:

$$ w \in \arg \min_{\bar{w}} R^e(\bar{w} \circ \Phi) \quad \forall e \in \mathcal{E}_{train} \quad (82) $$

The IRM objective relaxes this to a penalty:

$$ \min_{\Phi, w} \sum_{e \in \mathcal{E}_{train}} R^e(w \circ \Phi) + \lambda \|\nabla_{w|w=1.0} R^e(w \circ \Phi)\|^2 \quad (83) $$

where $\mathcal{E}_{train}$ is the set of training environments, $R^e$ is the risk in environment $e$, $\Phi$ is the representation learner, $w$ is the linear classifier, and $\lambda$ is the regularization strength.

The gradient penalty encourages $w=1$ to be optimal in all environments, which happens when the representation captures invariant causal features.

### 4.8.5 Distributionally Robust Optimization (DRO)

DRO optimizes for the worst-case distribution within an uncertainty set:

$$ \min_{\theta} \sup_{Q \in \mathcal{U}} \mathbb{E}_Q [\ell(f_{\theta}(X), Y)] \quad (84) $$

where $\mathcal{U}$ is the uncertainty set of distributions, $Q$ is a distribution within that set, and $\theta$ are the model parameters.

Common uncertainty sets include:

* f-divergence ball: $\mathcal{U} = \{Q: D_f(Q \| P) \le \rho\}$

*Detailed Explanation:* The f-divergence family includes KL-divergence, $\chi^2$-divergence, and total variation distance. This uncertainty set contains all distributions $Q$ whose f-divergence from the empirical distribution $P$ is at most $\rho$. The choice of $f$ determines the geometry of the uncertainty set: KL-divergence corresponds to an exponential family, while $\chi^2$-divergence has computationally attractive quadratic structure. The radius $\rho$ controls
the robustness level—larger $\rho$ means protecting against more severe distribution shifts but potentially sacrificing nominal performance.

**Concrete Example:** For image classification with $\chi^2$-divergence and $\rho = 0.1$, if the empirical distribution assigns probability $p_i$ to each training example, the uncertainty set includes reweighted distributions where example weights $q_i$ satisfy $\sum_i (q_i - p_i)^2/p_i \le 0.1$. This allows the adversary to upweight or downweight training examples (modeling class imbalance or selection bias) but constrains the total reweighting. Training with DRO over this set makes the model robust to test distributions with similar imbalances.

* **Wasserstein ball:** $U = \{Q : W_p(Q, P) \le \rho\}$

**Detailed Explanation:** The Wasserstein distance measures the minimal “cost” of transporting probability mass from distribution $P$ to $Q$, where cost is determined by the underlying metric on the input space $\mathcal{X}$. For order $p = 1$ or $p = 2$, $W_p(Q, P)$ quantifies how much the data points must be moved (in expectation) to transform $P$ into $Q$. The Wasserstein ball with radius $\rho$ contains all distributions reachable by moving each data point by at most $\rho$ in the input space metric. This is particularly natural for image data where small pixel perturbations correspond to meaningful Wasserstein distance.

**Concrete Example:** For MNIST digit classification with $\ell_2$ metric and $\rho = 0.3$ (normalized pixel space), the Wasserstein ball around a training image of "7" includes all images obtainable by moving each pixel value by small amounts such that the total $\ell_2$ displacement is at most 0.3. This naturally models adversarial perturbations, brightness/contrast changes, and small geometric distortions. Wasserstein DRO with this uncertainty set automatically learns features robust to these perturbations without explicit adversarial training, and it has theoretical connections to adversarial training with $\ell_2$ attacks.

* **Group DRO:** $U = \text{conv}(\{P_1, \dots, P_k\})$ over predefined groups

**Detailed Explanation:** Group DRO partitions the data into $k$ predefined groups (e.g., demographic subgroups, domains, or difficulty strata) with empirical distributions $P_1, \dots, P_k$. The uncertainty set is the convex hull of these group distributions, meaning the adversary can choose any weighted mixture $Q = \sum_{i=1}^k \lambda_i P_i$ with $\lambda_i \ge 0$, $\sum_i \lambda_i = 1$. Unlike $f$-divergence or Wasserstein balls which are geometric, Group DRO is combinatorial—it explicitly optimizes for the worst-case group. The minimax optimization becomes $\min_{\theta} \max_{\lambda \in \Delta_k} \sum_{i=1}^k \lambda_i \mathbb{E}_{P_i}[\ell_{\theta}]$, which has a particularly clean solution: always upweight the group with the highest current loss.

**Concrete Example:** In medical diagnosis with patient groups defined by age (pediatric, adult, elderly) and metabolic status (type A, type B), yielding 6 groups total, Group DRO ensures the model performs well on the worst-performing subgroup. If the model initially achieves 95% accuracy on adults with type A status but only 85% on elderly with type B status, Group DRO will upweight the latter group during training, forcing the model to improve performance on this specific subgroup. This is crucial for healthcare applications where disparate performance across subgroups violates safety requirements. Unlike vanilla ERM which optimizes average performance, Group DRO provides robustness guarantees for every predefined group.

**Theorem 4.15 (DRO Duality).** For $\chi^2$-divergence uncertainty set, the robust optimization has the dual form:

$$ \min_{\theta} \sup_{Q: D_{\chi^2}(Q \| P) \le \rho} \mathbb{E}_Q[\ell] = \min_{\theta} \left\{ \mathbb{E}_P[\ell] + \sqrt{\rho \cdot \text{Var}_P[\ell]} \right\} \quad (85) $$

This shows DRO penalizes the variance of the loss, preferring solutions that perform uniformly well.
# 5 Mathematical Foundations of Algorithmic Fairness

## 5.1 The Philosophical and Mathematical Underpinnings

Algorithmic fairness is concerned with ensuring that machine learning models do not reproduce or exacerbate existing social inequalities. Unlike accuracy, which is a single scalar metric, fairness is a multi-dimensional concept with mutually incompatible definitions rooted in different philosophical traditions of justice. This complexity stems from the fundamental question: What does it mean for an algorithm to be “fair”?

The philosophical foundations of fairness in AI draw on multiple traditions of justice theory. *Rawlsian justice* emphasizes that inequalities should benefit the least advantaged members of society, suggesting that AI systems should be evaluated in terms of their impacts on specific subgroups rather than merely on aggregate outcomes. *Luck egalitarianism* distinguishes between inequalities arising from circumstances beyond individual control (morally arbitrary) and those arising from genuine choice (potentially acceptable). *Anti-subordination theories* focus on disrupting patterns of group-based disparities rather than merely achieving statistical parity.

These philosophical traditions translate into distinct mathematical formulations of fairness, each capturing different intuitions about what fair treatment means. The diversity of these definitions is not a bug but a feature—it reflects the genuine complexity of fairness as a normative concept. However, this diversity creates practical challenges, as impossibility theorems demonstrate that many intuitive fairness properties cannot be simultaneously satisfied.

## 5.2 Group Fairness: Statistical Parity and Beyond

Group fairness requires that the system’s behavior be similar across different demographic groups. Consider a binary classification setting with prediction $\hat{Y} \in \{0, 1\}$, true outcome $Y \in \{0, 1\}$, and protected attribute $A \in \{0, 1\}$ (extended naturally to multi-group settings).

**Definition 5.1 (Demographic Parity).** A classifier satisfies demographic parity (also called statistical parity) if:

$$P(\hat{Y} = 1 | A = 0) = P(\hat{Y} = 1 | A = 1) \qquad (86)$$

where $\hat{Y}$ is the predicted label and $A$ is the sensitive attribute.

Demographic parity requires that positive prediction rates be equal across groups regardless of other characteristics. This definition ensures that members of different groups receive positive outcomes at equal rates but does not account for whether group members are equally qualified.

**Definition 5.2 (Equalized Odds).** A classifier satisfies equalized odds if both true positive and false positive rates are equal across groups:

$$P(\hat{Y} = 1 | Y = y, A = 0) = P(\hat{Y} = 1 | Y = y, A = 1) \quad \text{for } y \in \{0, 1\} \qquad (87)$$

where $Y$ is the true label.

Equalized odds requires that error rates be the same across groups, conditioning on the true outcome. This is often considered more appropriate than demographic parity because it accounts for different qualification rates across groups.

**Definition 5.3 (Equal Opportunity).** A classifier satisfies equal opportunity if true positive rates are equal across groups:

$$P(\hat{Y} = 1 | Y = 1, A = 0) = P(\hat{Y} = 1 | Y = 1, A = 1) \qquad (88)$$

where the condition $Y = 1$ restricts the comparison to the qualified population.
Equal opportunity is a relaxation of equalized odds that focuses only on ensuring equal treatment of qualified individuals.

**Definition 5.4 (Calibration).** A classifier is calibrated if predicted probabilities equal actual outcome frequencies within each group:

$$P(Y = 1 | \hat{Y} = p, A = a) = p \quad \text{for all } a \in \{0, 1\}, p \in [0, 1] \qquad (89)$$

where $p$ is the predicted probability score.

Calibration ensures that risk estimates are equally accurate across groups, meaning that individuals with the same predicted score should have the same actual risk regardless of group membership.

## 5.3 Individual Fairness: The Metric Approach

Individual fairness, formalized by [14], requires that similar individuals receive similar treatment. The formal requirement is:

**Definition 5.5 (Individual Fairness).** A classifier $f$ satisfies individual fairness with respect to metrics $d_X$ and $d_Y$ if:

$$d_Y(f(x), f(x')) \le L \cdot d_X(x, x') \qquad (90)$$

for all $x, x' \in \mathcal{X}$, where $L$ is a Lipschitz constant, $d_X$ is a distance metric in the input space, and $d_Y$ is a distance metric in the output space.

For probabilistic classifiers, the output metric is typically:

$$d_Y(f(x), f(x')) = |P(\hat{Y} = 1 | X = x) - P(\hat{Y} = 1 | X = x')| \qquad (91)$$

where $P(\hat{Y} = 1 | X = x)$ is the predicted probability of the positive class for input $x$.

The central challenge in individual fairness is specifying the similarity metric $d_X$. This requires determining which features are relevant for similarity comparisons and how to weight different features.

## 5.4 Impossibility Results and Trade-offs

A fundamental challenge in achieving fairness is that many mathematically precise fairness definitions are mutually incompatible. The following theorems demonstrate that perfect fairness along multiple dimensions is impossible when groups have different base rates.

**Theorem 5.1 (Impossibility of Perfect Fairness).** If $P(Y = 1 | A = 0) \neq P(Y = 1 | A = 1)$ (different base rates), then no classifier can simultaneously satisfy:

1. Demographic Parity: $P(\hat{Y} = 1 | A = 0) = P(\hat{Y} = 1 | A = 1)$

2. Equalized Odds: $P(\hat{Y} = 1 | Y = y, A = 0) = P(\hat{Y} = 1 | Y = y, A = 1)$ for $y \in \{0, 1\}$

3. Calibration: $P(Y = 1 | \hat{Y} = 1, A = a)$ is independent of a

except in degenerate cases (e.g., constant predictors or perfect prediction).
*Proof.* We prove that Demographic Parity and Equalized Odds are incompatible when base rates differ ($p_0 \neq p_1$) and the predictor is not trivial (perfect or random).

Let $p_a = P(Y = 1|A = a)$ be the base rate for group $a$. Let $r_a = P(\hat{Y} = 1|Y = 1, A = a)$ be the True Positive Rate (TPR). Let $s_a = P(\hat{Y} = 1|Y = 0, A = a)$ be the False Positive Rate (FPR).

The overall positive prediction rate for group $a$ is:

$$P(\hat{Y} = 1|A = a) = r_a p_a + s_a (1 - p_a) \qquad (92)$$

**Assume Equalized Odds:** $r_0 = r_1 = r$ and $s_0 = s_1 = s$. Then the positive prediction rates are:

$$P(\hat{Y} = 1|A = 0) = r p_0 + s (1 - p_0) = s + (r - s) p_0 \qquad (93)$$

$$P(\hat{Y} = 1|A = 1) = r p_1 + s (1 - p_1) = s + (r - s) p_1 \qquad (94)$$

**Assume Demographic Parity:** $P(\hat{Y} = 1|A = 0) = P(\hat{Y} = 1|A = 1)$. Substituting the expressions above:

$$s + (r - s) p_0 = s + (r - s) p_1 \implies (r - s)(p_0 - p_1) = 0 \qquad (95)$$

Since we assume different base rates ($p_0 \neq p_1$), we must have $r = s$. The condition $TPR = FPR$ implies that the classifier has no predictive power (it is equivalent to random guessing). Thus, a non-trivial classifier cannot simultaneously satisfy Demographic Parity and Equalized Odds when base rates differ. Since it cannot satisfy the first two, it certainly cannot satisfy all three. $\square$

**Theorem 5.2** (Chouldechova's Impossibility Result [11]). For a binary classifier with different base rates across groups ($P(Y = 1|A = 0) \neq P(Y = 1|A = 1)$), it is impossible to simultaneously satisfy:

1. Equal positive predictive value: $P(Y = 1|\hat{Y} = 1, A = 0) = P(Y = 1|\hat{Y} = 1, A = 1)$

2. Equal false negative rate: $P(\hat{Y} = 0|Y = 1, A = 0) = P(\hat{Y} = 0|Y = 1, A = 1)$

3. Equal false positive rate: $P(\hat{Y} = 1|Y = 0, A = 0) = P(\hat{Y} = 1|Y = 0, A = 1)$

unless the classifier is perfect (error-free) on both groups.

**Proof Sketch.** The positive predictive value (precision) is:

$$PPV_a = P(Y = 1|\hat{Y} = 1, A = a) = \frac{TPR_a \cdot p_a}{TPR_a \cdot p_a + FPR_a \cdot (1 - p_a)} \qquad (96)$$

If $TPR_0 = TPR_1$ (equal FNR) and $FPR_0 = FPR_1$, then:

$$PPV_0 = PPV_1 \iff \frac{p_0}{p_0 + FPR/TPR \cdot (1 - p_0)} = \frac{p_1}{p_1 + FPR/TPR \cdot (1 - p_1)} \qquad (97)$$

This equality holds for all FPR/TPR ratios only if $p_0 = p_1$, contradicting the assumption. Thus, when base rates differ, equal error rates imply unequal predictive values. $\square$

This impossibility result has profound implications: it demonstrates that choices among fairness criteria cannot be avoided, and that claims to satisfy “fairness” without specifying which fairness criterion are incomplete.
## 5.5 Intersectionality and Multi-Group Fairness

Real-world fairness requires consideration of intersectional identities—individuals belong to multiple groups defined by different attributes. For attributes $A_1 \in \{0, 1\}$ and $A_2 \in \{0, 1\}$, there are four intersectional groups: $\{(0, 0), (0, 1), (1, 0), (1, 1)\}$.

**Definition 5.6 (Intersectional Demographic Parity).** A classifier satisfies intersectional demographic parity if:

$$P(\hat{Y} = 1 | A_1 = a_1, A_2 = a_2) = P(\hat{Y} = 1 | A_1 = a'_1, A_2 = a'_2) \quad (98)$$

for all values $a_1, a'_1, a_2, a'_2$ of the protected attributes $A_1$ and $A_2$.

The computational complexity of fairness constraints grows exponentially with the number of protected attributes and their cardinalities. For $k$ binary attributes, there are $2^k$ intersectional groups, making exact fairness intractable for large $k$.

## 5.6 Fairness Metrics and Evaluation

Translating abstract fairness definitions into measurable quantities requires comprehensive evaluation frameworks that account for statistical uncertainty and temporal dynamics.

### 5.6.1 Disparity Metrics

**Definition 5.7 (Demographic Parity Difference (DPD)).**

$$\text{DPD} = P(\hat{Y} = 1 | A = 1) - P(\hat{Y} = 1 | A = 0) \quad (99)$$

where $A = 1$ typically denotes the advantaged group and $A = 0$ the disadvantaged group. Values closer to zero indicate greater demographic parity.

**Definition 5.8 (Disparate Impact Ratio (DIR)).**

$$\text{DIR} = \frac{P(\hat{Y} = 1 | A = 0)}{P(\hat{Y} = 1 | A = 1)} \quad (100)$$

where the numerator is the selection rate for the disadvantaged group and the denominator is the selection rate for the advantaged group. The 80% rule considers $\text{DIR} < 0.8$ as prima facie evidence of adverse impact.

**Definition 5.9 (Equalized Odds Difference (EOD)).**

$$\text{EOD} = |\text{TPR}_{A=1} - \text{TPR}_{A=0}| + |\text{FPR}_{A=1} - \text{FPR}_{A=0}| \quad (101)$$

where $\text{TPR}_{A=a} = P(\hat{Y} = 1 | Y = 1, A = a)$ is the True Positive Rate for group $a$, and $\text{FPR}_{A=a} = P(\hat{Y} = 1 | Y = 0, A = a)$ is the False Positive Rate for group $a$.

### 5.6.2 Calibration Metrics

**Definition 5.10 (Expected Calibration Error (ECE)).**

$$\text{ECE} = \sum_{b=1}^{B} \frac{n_b}{N} |\text{acc}_b - \text{conf}_b| \quad (102)$$

where predictions are partitioned into $B$ bins by confidence level, $n_b$ is the number of samples in bin $b$, $N$ is the total number of samples, $\text{acc}_b$ is the accuracy in bin $b$, and $\text{conf}_b$ is the average confidence in bin $b$.
For fairness assessment, ECE should be computed separately for each protected group to reveal calibration disparities.

### 5.6.3 Statistical Considerations

Fairness metrics are estimates from finite samples and subject to statistical uncertainty. Confidence intervals should accompany point estimates:

$$ \widehat{DPD} \pm z_{\alpha/2} \cdot \text{SE}(\widehat{DPD}) \qquad (103) $$

where $\widehat{DPD}$ is the estimated demographic parity difference, $z_{\alpha/2}$ is the critical value from the standard normal distribution for significance level $\alpha$, and SE denotes the standard error.

For binary outcomes, the standard error of the difference in selection rates is:

$$ \text{SE}(\hat{p}_1 - \hat{p}_0) = \sqrt{\frac{\hat{p}_1(1 - \hat{p}_1)}{n_1} + \frac{\hat{p}_0(1 - \hat{p}_0)}{n_0}} \qquad (104) $$

where $\hat{p}_a$ is the sample selection rate for group a, and $n_a$ is the sample size for group a.

## 5.7 Algorithmic Techniques for Fairness

Recent advancements in trustworthy AI have formalized three primary intervention points for fairness: pre-processing, in-processing, and post-processing [29, 35].

### 5.7.1 Pre-processing Methods

Pre-processing methods fundamentally alter the training data distribution to remove statistical dependencies between sensitive attributes and outcomes before a model is ever trained. The most prominent technique, **Reweighing**, assigns importance weights to individual samples to enforce independence. Specifically, for an individual i with sensitive attribute $A_i$ and outcome $Y_i$, the weight is calculated as:

$$ w_i = \frac{P(A = A_i)P(Y = Y_i)}{P(A = A_i, Y = Y_i)} \qquad (105) $$

which effectively constructs a new dataset where A and Y are independent. Alternatively, **Fair Representation Learning** seeks to learn a projection of the data into a latent space Z where sensitive information is obfuscated while task-relevant information is preserved. This is typically formulated as an optimization problem $\min_Z \mathcal{L}_{\text{reconstruction}} + \lambda \mathcal{L}_{\text{fairness}}$, where the fairness penalty enforces orthogonality or independence between Z and A [10].

### 5.7.2 In-processing Methods

In-processing methods integrate fairness requirements directly into the model training procedure, often by solving a constrained optimization problem. The general formulation involves minimizing the empirical risk $\mathcal{L}(\theta)$ subject to a constraint $g_{\text{fairness}}(\theta) \le \epsilon$ that bounds the allowable fairness violation. Techniques like **Adversarial Debiasing** employ a minimax game where a predictor minimizes the task loss while an adversary attempts to reconstruct the sensitive attribute from the predictor's outputs or latent representations:

$$ \min_{\theta_f} \max_{\theta_a} \mathcal{L}_{\text{task}}(\theta_f) - \lambda \mathcal{L}_{\text{adversarial}}(\theta_f, \theta_a) \qquad (106) $$
This approach ensures that the learned representation contains no extractable information about the protected group. To solve these constrained problems, **Lagrangian Relaxation** is frequently used, converting the hard constraints into a primal-dual objective $min_{\theta} \max_{\lambda \ge 0} \mathcal{L}(\theta) + \lambda g_{\text{fairness}}(\theta)$, which can be optimized via alternating gradient descent integration principles from [18].

### 5.7.3 Post-processing Methods

Adjust model outputs to satisfy fairness criteria.

**Threshold Optimization:** Sets group-specific thresholds to achieve fairness:

$$ \hat{Y}_a = \mathbb{I}[f(X) > \tau_a] \quad \text{where } \tau_a \text{ chosen to satisfy fairness constraints} \quad (107) $$

where $\mathbb{I}[\cdot]$ is the indicator function, $f(X)$ is the model score, and $\tau_a$ is the group-specific threshold for group a.

**Calibration Adjustment:** Modifies predicted probabilities to ensure equal calibration across groups.

## 5.8 Causal Fairness and Counterfactual Reasoning

Causal approaches to fairness seek to identify and eliminate the causal effects of protected attributes on outcomes, distinguishing legitimate from illegitimate causal pathways. Unlike statistical fairness, which focuses on correlations, causal fairness requires that decisions are fair under interventions on the causal graph.

### 5.8.1 Motivation: Why Causality Matters for Fairness

Statistical fairness criteria can be satisfied by systems that are intuitively unfair, or violated by systems that are intuitively fair. Consider a hiring algorithm:

* A company uses education level to predict job performance.

* Education is correlated with race due to historical discrimination in educational access.

* A statistically fair classifier (satisfying demographic parity) might reject qualified candidates from a specific demographic to balance rates.

* A causal approach asks: “Would this person have been hired if their race had been different, holding their qualifications fixed?”

### 5.8.2 Counterfactual Fairness

**Definition 5.11 (Counterfactual Fairness [21]).** Let $\mathcal{M}$ be a structural causal model with observed variables $X$, sensitive attribute $A$, and exogenous variables $U$. A predictor $\hat{Y}$ is **counterfactually fair** if for any individual with characteristics $(X = x, A = a)$ and corresponding exogenous factors $U = u$:

$$ P(\hat{Y}_{A \leftarrow a}(u) = y | X = x, A = a) = P(\hat{Y}_{A \leftarrow a'}(u) = y | X = x, A = a) \quad (108) $$

for all values $a, a' \in \mathcal{A}$ and all outcomes $y$.
Here, $\hat{Y}_{A \leftarrow a}(u)$ denotes the counterfactual: “What would the prediction have been if A had been set to a, keeping the same individual (same U)?" The notation $A \leftarrow a$ represents the do-operator or intervention setting A to value a.

**Remark 5.1 (Interpretation).** Counterfactual fairness ensures that an individual's classification would not have changed if their sensitive attribute had been different, holding all non-descendant factors constant. This captures the intuition that a person should not be penalized for characteristics beyond their control.

### 5.8.3 Path-Specific Fairness

In many real-world scenarios, the effect of a sensitive attribute on the outcome may flow through multiple causal pathways, some of which may be considered legitimate and others discriminatory.

**Example 5.1 (Legitimate vs. Illegitimate Pathways).** Consider a loan approval model with the causal graph:

<figure><img src="image_3.png" /></figure>

* **Direct effect** ($A \to Y$, dashed): Direct discrimination—illegitimate.

* **Indirect through income** ($A \to I \to Y$): May reflect historical wage discrimination—potentially illegitimate.

* **Indirect through education** ($A \to E \to Y$): Complex—education differences may reflect both discrimination in access and genuine qualification differences.

**Definition 5.12 (Path-Specific Counterfactual Fairness).** A predictor is fair with respect to a set of causal paths $\Pi$ if the causal effect of the sensitive attribute $A$ on prediction $\hat{Y}$ along paths in $\Pi$ is zero:

$$ \mathrm{PSE}_{\Pi}(a \to a') = \mathbb{E}[\hat{Y}_{A \leftarrow a', \Pi}(u) - \hat{Y}_{A \leftarrow a, \Pi}(u)] = 0 \quad (109) $$

where the intervention affects only the designated pathways $\Pi$, and PSE stands for Path-Specific Effect.

### 5.8.4 Implementing Causal Fairness

To implement causal fairness in practice:

**Step 1: Specify the Causal Graph.** This requires domain expertise and may be contested. The graph encodes assumptions about how variables causally influence each other.

**Step 2: Identify Fair Pathways.** Determine which causal effects of the sensitive attribute are legitimate (resolving pathway) vs. illegitimate (discriminatory pathway).

**Step 3: Compute Counterfactual Features.** For each individual, compute what their features would have been under a different sensitive attribute value:

$$ X_{A \leftarrow a'}(u) = f_X(Pa_X \text{ with } A \text{ set to } a', U_X = u_X) \quad (110) $$
where $f_X$ is the structural equation for $X$, $P_{\hat{X}}$ are the parents of $X$ in the causal graph, and $U_X$ are the exogenous noise variables for $X$.

**Step 4: Train Fair Predictor.** Train a model using only:

* Features that are not descendants of $A$ in the causal graph, or

* Counterfactually-adjusted features that remove the effect of $A$

### 5.8.5 The Proxy Variable Problem

Even when the sensitive attribute $A$ is not directly used, the model may learn to predict $A$ from other features (proxies), leading to indirect discrimination.

**Definition 5.13 (Proxy Variable).** A variable $X$ is a **proxy** for sensitive attribute $A$ if:

1. $X$ is correlated with $A$: $I(X; A) > 0$

2. Using $X$ for prediction leads to disparate outcomes: $P(\hat{Y}|A = 0, X) \neq P(\hat{Y}|A = 1, X)$ in expectation

where $I(X; A)$ is the mutual information between $X$ and $A$.

**Example 5.2 (Common Proxies).**

* ZIP code as proxy for race (due to residential segregation)

* First name as proxy for gender or ethnicity

* LinkedIn connections as proxy for socioeconomic status

Causal analysis helps identify and address proxies by examining the causal structure. If $A \to X \to \hat{Y}$, then $X$ transmits the effect of $A$ to the prediction.

### 5.8.6 Challenges and Limitations

1. **Causal Graph Uncertainty:** The true causal graph is often unknown. Different assumptions lead to different fairness conclusions.

2. **Unobserved Confounders:** Hidden common causes between $A$ and $Y$ can make causal effects unidentifiable from observational data.

3. **Counterfactual Identifiability:** Computing counterfactuals requires knowledge of the structural equations $f_i$, which are typically unknown.

4. **Philosophical Concerns:** Some argue that counterfactuals of immutable attributes ("if this person's race had been different") are metaphysically problematic.

5. **Accuracy Trade-offs:** If the sensitive attribute contains legitimate predictive information through fair pathways, counterfactual fairness may significantly reduce accuracy.
## 5.9 Fairness in Modern AI Systems

Contemporary challenges in fairness include:

**Foundation Models:** Pre-trained models may encode biases that propagate to downstream tasks, requiring fairness interventions at multiple stages.

**Dynamic Systems:** ML systems that learn and adapt over time can exhibit fairness drift, requiring continuous monitoring.

**Multi-stakeholder Settings:** Different stakeholders may prioritize different fairness criteria, requiring principled approaches to trade-off resolution.

### Exercises

1. **Impossibility Results:**

(a) Prove that demographic parity and individual fairness can be incompatible. Consider a simple example with two groups having different base rates and show that no Lipschitz-continuous classifier can satisfy both constraints.

(b) Implement the Adult Census Income dataset and demonstrate the trade-off between demographic parity and equalized odds by plotting the Pareto frontier.

(c) Construct a concrete example where calibration and demographic parity cannot be simultaneously satisfied.

2. **Fairness Metrics Implementation:**

(a) Implement a comprehensive fairness evaluation library that computes DPD, DIR, EOD, calibration metrics with confidence intervals.

(b) Add support for intersectional analysis across multiple protected attributes.

(c) Implement statistical significance tests for fairness disparities using permutation tests and bootstrap confidence intervals.

3. **Individual Fairness:**

(a) Design a task-appropriate similarity metric for a generic dataset measuring creditworthiness that considers financial history while being insensitive to protected attributes.

(b) Implement the Lipschitz regularization approach and compare it against standard ERM.

(c) Investigate how the choice of similarity metric affects both fairness and accuracy.

4. **Algorithmic Interventions:**

(a) Implement the Reweighing pre-processing algorithm and evaluate its effectiveness on reducing demographic parity violations.

(b) Design an adversarial debiasing system using PyTorch that learns fair representations for image classification tasks.

(c) Compare pre-processing, in-processing, and post-processing approaches on the same dataset and analyze their relative strengths and limitations.

5. **Causal Fairness:**

(a) Construct a structural causal model for a hiring scenario with legitimate and illegitimate causal pathways.
(b) Implement counterfactual fairness using causal inference techniques and compare it to statistical fairness measures.

(c) Analyze the impact of hidden confounders on fairness assessment and mitigation.

6. Advanced Applications:

(a) Design a fair recommendation system that balances accuracy and demographic parity across user groups.

(b) Implement fairness-aware federated learning where different clients have different protected group distributions.

(c) Create a dynamic fairness monitoring system that detects and responds to fairness drift in deployed models.

7. Theoretical Case Analysis:

(a) Analyze a synthetic dataset $\mathcal{D}$ generated from a known structural causal model. Compute all fairness metrics, identify disparities, and propose mitigations.

(b) Examine the impact of base rate differences on fairness metrics using abstract distributions $P_0$ and $P_1$.

(c) Study a hypothetical medical dataset: balance fairness constraints with the clinical need for accurate predictions.

8. Intersectionality:

(a) Implement intersectional fairness metrics for combinations of race and gender.

(b) Show that satisfying fairness for individual attributes does not guarantee fairness for intersectional groups.

(c) Propose and implement a method to achieve fairness across exponentially many intersectional groups efficiently.

9. Theoretical Analysis:

(a) Prove that for $k$ protected groups, achieving exact demographic parity reduces to a system of $k-1$ linear constraints.

(b) Derive the sample complexity required to estimate demographic parity difference to within $\pm \epsilon$ with probability $1 - \delta$.

(c) Analyze the computational complexity of finding an optimal fair classifier under different fairness constraints.

5.10 Implementation Templates and Code Examples

5.10.1 Fairness-Constrained Optimization

```python
import torch
import torch.nn as nn

class FairClassifier nn.Module:
    def __init__(self, input_dim, hidden_dim, output_dim):
        super().__init__()
        self predictor = nn.Sequence(
            nn.Linear(input_dim, hidden_dim),
            nnigm.,
```
```python
nn.Linear(hidden_dim, output_dim),
nn.Sigmoid()
)

def forward(self, x):
    return self predictor(x)

def demographic_parity_loss(y_pred, sensitive_attr):
    """Differentiable demographic parity constraint."""
    group_0_idx = (sensitive_attr == 0) . nonzero(as_tuple = True) [0]
    group_1_idx = (sensitive_attr == 1) . nonzero(as_tuple = True) [0]

    if len(group_0_idx) == 0 or len(group_1_idx) == 0:
        return torch .tensor(0.0)

    rate_0 = y_pred [group_0_idx] .mean()
    rate_1 = y_pred [group_1_idx] .mean()

    return (rate_0 - rate_1) ** 2

def train_fair Classfier(model, train_loader, epochs=100,
    lambda_fair = 1.0):
    """Training loop with fairness constraint."""
    optimizer = torch .optim .Adam(model .parameters())
    criterion = nn .BCELoss()

    for epoch in range(epochs):
        for batch_x, batch_y, batch_a in train_loader:
            optimizer .zeroGrad()
            y_pred = model(batch_x)

            # Task loss + Fairness loss
task_loss = criterion(y_pred .squeeze() ,batch_y .float())
fair_loss = demographic_parity_loss(y_pred .squeeze() ,
    batch_a)
total_loss = task_loss + lambda_fair * fair_loss

total_loss .backward()
optimization.step()
```

<caption>Listing 1: Fair Classifier with Demographic Parity Constraint</caption>

5.10.2 Adversarial Debiasing Implementation

```python
class AdversarialDebiasing(nn.Module):
    def __init__(self, input_dim, hidden_dim, repr_dim):
        super().__init__()

    # Feature encoder: learns fair representations
    selfencoder = nn .Sequential(
        nn .Linear(input_dim, hidden_dim),
        nn .ReLU(),
        nn .Linear(hidden_dim, repr_dim)
    )

    # Task predictor: predicts target label from representation
    self predictor = nn .Sequential(
```
```python
nn.Linear(repr_dim, 1),
nn.Sigmoid()
)

# Adversary: tries to predict sensitive attribute
self.dis crim inator = nn.S e qu ial t i o n (
    nn.Linear(repr_dim, hidden_dim // 2),
    nnigmPred(),
    nnLinear(hidden_dim // 2, 1),
    nn.Sigmoid()
)

def forward(self, x):
    z = selfencoder(x) # Fair representation
    y pred = self predictor(z) # Task prediction
    a pred = selfdiscriminator(z) # Adversary prediction
    return y pred, a pred, z
```

<caption>Listing 2: Adversarial Debiasing Architecture</caption>

5.10.3 Comprehensive Fairness Evaluation

```python
import numpy as np
from scapy import stats

class FairnessEvaluator:
    def __init__(self, y_true, y_pred, y-Prob, sensitive_attr):
        self.y_true = y_true
        self.y_pred = y_pred
        self.y-Prob = y-Prob
        self.sensitive_attr = sensitive_attr

    def demographic_parityDifference(self):
        """Calculate DPD with 95% confidence interval."""
        rate_0 = self.y_pred(self.sensitive_attr == 0).mean()
        rate_1 = self.y_pred(self.sensitive_attr == 1).mean()
        n_0 = (self.sensitive_attr == 0).sum()
        n_1 = (self.sensitive_attr == 1).sum()

        dpd = rate_1 - rate_0
        se = nperATE rate_0 * (1 - rate_0) / n_0 + rate_1 * (1 - rate_1) / n_1

        return {
            'dpd': dpd,
            'ci_lower': dpd - 1.96 * se,
            'ci_lower': dpd + 1.96 * se,
            'p_value': 2 * (1 - stats .norm.cdf( abs(dpd / se)))
        }

    def comprehensive_report(self):
        """Generate comprehensive fairness report."""
        report = {
            'demographic_parity': self.demographic_parityDifference()
            'equalized_odds': self equalized_ odds_d if f er en ce (
            'calibration': self.calibration_analysis()
        }
```
```
36
37
38
39
40
41
42

# Summary with threshold-based violation detection
dpd_violation = abs(report['demographic_parity']['dpd']) > 0.1
report['summary'] = {
    'demographic_parity_violation': dpd_violation,
    'overall_fair': not dpd_violation
}
return report
```

<caption>Listing 3: Comprehensive Fairness Evaluation Class</caption>

## 5.11 Mechanisms for Fair Learning

Fairness interventions can be applied at three stages of the machine learning pipeline.

### 5.11.1 Pre-processing Methods

These methods modify the training data to remove bias before the model is trained.

* **Reweighing**: Assign weights $W(x, y)$ to samples to decorrelate $Y$ and $A$. For example, if group $A = 0$ has fewer positive outcomes than expected, we upweight the ($A = 0, Y = 1$) samples.

* **Learning Fair Representations (LFR)**: Map the input $x$ to a latent space $Z$ such that $Z$ retains information about $Y$ but loses information about $A$. This is often achieved via Adversarial Representation Learning, where an encoder tries to fool a discriminator that predicts $A$ from $Z$.

### 5.11.2 In-processing: Constrained Optimization

These methods modify the training objective to penalize unfairness. We formulate fairness as a constraint $g(\theta) \le c$.

$$ \min_{\theta} \mathcal{L}(\theta) \quad \text{s.t.} \quad |\mathbb{E}[f(x)|A=0] - \mathbb{E}[f(x)|A=1]| \le \epsilon \quad (111) $$

where $\mathcal{L}(\theta)$ is the loss function, $f(x)$ is the model prediction, and $\epsilon$ is the fairness tolerance. This constrained optimization problem is typically solved using the method of Lagrange multipliers. The Lagrangian is:

$$ \min_{\theta} \max_{\lambda} \mathcal{L}(\theta) + \lambda(g(\theta) - \epsilon) \quad (112) $$

where $\lambda$ is the Lagrange multiplier and $g(\theta)$ represents the fairness constraint function. The dual variable $\lambda$ acts as a dynamic penalty. If the model violates the fairness constraint, $\lambda$ increases, forcing the optimizer to prioritize fairness in the next step. The “Reductions Approach” ([3]) reduces this to a sequence of cost-sensitive classification problems.

### 5.11.3 Post-processing: Threshold Adjustment

If we have a fixed scoring model $R$, we can choose different decision thresholds $\tau_0, \tau_1$ for each group to satisfy Equalized Odds.

$$ \hat{Y} = \mathbb{I}(R > \tau_A) \quad (113) $$

where $\mathbb{I}(\cdot)$ is the indicator function, $R$ is the risk score, and $\tau_A$ is the group-specific threshold. For example, if group A has a lower score distribution, we might lower their threshold to equalize the
True Positive Rate. While mathematically optimal for a fixed predictor, this approach constitutes "disparate treatment" (using the sensitive attribute explicitly in the decision rule), which is often constrained by formalized operational policies despite its mathematical optimality.

## Exercises

1. **Impossibility Theorem:**

(a) Simulate a synthetic dataset where the base rates $P(Y = 1|A = 0)$ and $P(Y = 1|A = 1)$ are different.

(b) Train a logistic regression model.

(c) Calculate Demographic Parity, Equalized Odds, and Calibration metrics.

(d) Verify that you cannot satisfy all three simultaneously.

2. **Pre-processing:**

(a) Implement the Reweighing algorithm.

(b) Apply it to the Adult Income dataset.

(c) Compare the fairness metrics before and after reweighing.

3. **Individual Fairness:**

(a) Define a similarity metric for a generic employment dataset.

(b) Check if a standard classifier satisfies the Lipschitz condition with respect to this metric.
# 6 Privacy and Data Sovereignty

## 6.1 Differential Privacy Foundations

The gold standard for privacy-preserving data analysis is Differential Privacy (DP). Unlike anonymity, which focuses on removing identifiers (and is often reversible via linkage attacks), DP focuses on the stability of the algorithm's output.

### 6.1.1 Definition and Properties

**Definition 6.1** ((ε, δ)-Differential Privacy). A randomized mechanism $\mathcal{M}: \mathcal{D} \to \mathcal{R}$ is $(\epsilon, \delta)$-DP if for all adjacent datasets $D, D'$ (differing by exactly one element) and all measurable subsets $S \subseteq \mathcal{R}$:

$$P(\mathcal{M}(D) \in S) \le e^{\epsilon} P(\mathcal{M}(D') \in S) + \delta \quad (114)$$

where $P$ denotes probability, $\epsilon$ is the privacy budget, and $\delta$ is the failure probability.

The parameter $\epsilon$ (privacy budget) bounds the multiplicative difference in probabilities. A smaller $\epsilon$ implies stronger privacy (outputs are indistinguishable). The parameter $\delta$ allows for a small probability of failure (e.g., the mechanism accidentally outputting the training data). Typically, we require $\delta \ll 1/N$.

### 6.1.2 The Privacy Loss Random Variable

To analyze complex mechanisms, it is useful to define the privacy loss random variable $Z$ for an outcome $o \sim \mathcal{M}(D)$:

$$Z = \ln \frac{P(\mathcal{M}(D) = o)}{P(\mathcal{M}(D') = o)} \quad (115)$$

where $P(\mathcal{M}(D) = o)$ is the probability density of outcome $o$ under dataset $D$. $(\epsilon, \delta)$-DP ensures that $P(Z > \epsilon) \le \delta$.

## 6.2 Mechanisms for Differential Privacy

### 6.2.1 The Laplace Mechanism

For a function $f: \mathcal{D} \to \mathbb{R}^k$, the $L_1$-sensitivity is $\Delta_1 f = \max_{D,D'} \|f(D) - f(D')\|_1$. The Laplace Mechanism adds noise drawn from the Laplace distribution:

$$\mathcal{M}(D) = f(D) + (Y_1, \dots, Y_k) \quad \text{where} \quad Y_i \sim \text{Lap}(\Delta_1 f / \epsilon) \quad (116)$$

where Lap($b$) denotes the Laplace distribution with scale parameter $b$, and $\Delta_1 f$ is the $L_1$-sensitivity of function $f$.

*Proof.* The density of the Laplace distribution with scale $b$ is $h(y) = \frac{1}{2b} \exp(-|y|/b)$. For output $z \in \mathbb{R}^k$:

$$\frac{P(\mathcal{M}(D) = z)}{P(\mathcal{M}(D') = z)} = \frac{\prod_{i=1}^{k} \exp(-|z_i - f(D)_i|/b)}{\prod_{i=1}^{k} \exp(-|z_i - f(D')_i|/b)} \quad (117)$$

$$= \exp\left(\frac{1}{b} \sum_{i=1}^{k} (|z_i - f(D')_i| - |z_i - f(D)_i|)\right) \quad (118)$$
By the reverse triangle inequality, for any $z_i, a, b \in \mathbb{R}$:

$$|z_i - b| - |z_i - a| \le |a - b| \qquad (119)$$

Summing over all coordinates:

$$\sum_{i=1}^{k} (|z_i - f(D')_i| - |z_i - f(D)_i|) \le \sum_{i=1}^{k} |f(D)_i - f(D')_i| = \|f(D) - f(D')\|_1 \le \Delta_1 f \qquad (120)$$

Setting $b = \Delta_1 f / \epsilon$ yields:

$$\frac{P(\mathcal{M}(D) = z)}{P(\mathcal{M}(D') = z)} \le \exp\left(\frac{\Delta_1 f}{b}\right) = \exp(\epsilon) \qquad (121)$$

This holds for all $z$, hence $\mathcal{M}$ is $\epsilon$-DP (with $\delta = 0$). $\square$

### 6.2.2 The Gaussian Mechanism

For functions with high $L_1$ sensitivity but low $L_2$ sensitivity, the Gaussian mechanism is preferred. $\mathcal{M}(D) = f(D) + \mathcal{N}(0, \sigma^2 I)$. This satisfies $(\epsilon, \delta)$-DP if $\sigma \ge \frac{\Delta_2 f}{\epsilon} \sqrt{2 \ln(1.25/\delta)}$. The proof relies on the tail properties of the Gaussian distribution.

### 6.2.3 The Exponential Mechanism

For non-numeric queries (e.g., “What is the most common disease?”), we define a utility function $u(D, r)$ that scores each possible output $r \in \mathbb{R}$. The mechanism samples $r$ with probability proportional to $\exp(\frac{\epsilon u(D, r)}{2\Delta u})$.

## 6.3 Composition and Renyi Differential Privacy

A key property of DP is composition: the privacy guarantee holds even when multiple analyses are performed on the same data. **Basic Composition** states that if $\mathcal{M}_i$ is $\epsilon_i$-DP, then the sequence $(\mathcal{M}_1(D), \dots, \mathcal{M}_k(D))$ is $(\sum \epsilon_i)$-DP. **Advanced Composition** provides a tighter bound, showing that for $k$ mechanisms each being $\epsilon$-DP, the composition is roughly $(k\epsilon^2)$-DP. This quadratic improvement is crucial for iterative algorithms like SGD.

### 6.3.1 Renyi Differential Privacy (RDP)

RDP provides tighter composition bounds by tracking the Renyi Divergence between the output distributions.

**Definition 6.2** (($\alpha, \epsilon$)-RDP). A mechanism $\mathcal{M}$ is $(\alpha, \epsilon)$-RDP if for all adjacent $D, D'$:

$$D_{\alpha}(\mathcal{M}(D)\|\mathcal{M}(D')) \le \epsilon \qquad (122)$$

where $D_{\alpha}(P\|Q) = \frac{1}{\alpha-1} \ln \mathbb{E}_{x \sim Q}[(P(x)/Q(x))^{\alpha}]$ is the Renyi divergence of order $\alpha$.

RDP composes linearly. We can convert RDP back to $(\epsilon, \delta)$-DP at the end of the analysis.
**Algorithm 4** Differentially Private SGD (DP-SGD)

**Input:** Dataset $D$, Loss $\mathcal{L}$, Noise scale $\sigma$, Clip $C$, Learning rate $\eta$, Iterations $T$
**for** $t = 1$ **to** $T$ **do**

Sample batch $B_t$ with sampling probability $q = L/N$

**for** $i \in B_t$ **do**

$$g_t^{(i)} \leftarrow \nabla_{\theta_t} \mathcal{L}(x_i, y_i)$$

$$\bar{g}_t^{(i)} \leftarrow g_t^{(i)} / \max(1, \frac{\|g_t^{(i)}\|_2}{C}) \{\text{Per-sample Clipping}\}$$

**end for**

$$\tilde{g}_t \leftarrow \frac{1}{|B_t|} \left( \sum_i \bar{g}_t^{(i)} + \mathcal{N}(0, \sigma^2 C^2 I) \right) \{\text{Add Noise}\}$$

$$\theta_{t+1} \leftarrow \theta_t - \eta \tilde{g}_t$$

**end for**

## 6.4 Privacy in Deep Learning

### 6.4.1 DP-SGD Algorithm

Training neural networks with DP involves two modifications: clipping per-sample gradients to bound sensitivity, and adding Gaussian noise to the aggregated gradient.

The privacy cost is calculated using the “Moments Accountant” method, which tracks the RDP moments across iterations.

### 6.4.2 Privacy Amplification by Subsampling

A crucial property of DP-SGD is that the privacy guarantee is amplified by subsampling. If the batch is a random subsample of the dataset with sampling probability $q$, the privacy cost per iteration is reduced.

**Theorem 6.1** (Privacy Amplification by Subsampling). If $\mathcal{M}$ is an $(\epsilon, \delta)$-DP mechanism and we apply it to a uniformly random subsample with probability $q$, the resulting mechanism $\mathcal{M}'$ satisfies $(\epsilon', \delta')$-DP where $\epsilon' = \ln(1 + q(e' - 1))$ and $\delta' = q\delta$. For small $\epsilon, \epsilon' \approx q\epsilon$.

*Proof Sketch.* Let $\mathcal{M}'(D)$ denote applying $\mathcal{M}$ to a random subsample $S \subseteq D$ where each element is included independently with probability $q$. For adjacent datasets $D, D'$ differing in one element $x^*$:

$$P(\mathcal{M}'(D) \in T) = \sum_{S} P(S \text{ sampled from } D) \cdot P(\mathcal{M}(S) \in T) \quad (123)$$

$$= q \cdot P(S \ni x^*) \cdot P(\mathcal{M}(S) \in T) + (1 - q) \cdot P(S \ni x^*) \cdot P(\mathcal{M}(S) \in T) \quad (124)$$

When $x^* \notin S$, the distributions from $D$ and $D'$ are identical. When $x^* \in S$ (with probability $q$), we use the $(\epsilon, \delta)$-DP guarantee of $\mathcal{M}$:

$$P(\mathcal{M}'(D) \in T) \le (1 - q)P(\mathcal{M}'(D') \in T) + q(e'P(\mathcal{M}'(D') \in T) + \delta) \quad (125)$$

$$= P(\mathcal{M}'(D') \in T) \cdot (1 - q + qe') + q\delta \quad (126)$$

$$= P(\mathcal{M}'(D') \in T) \cdot (1 + q(e' - 1)) + q\delta \quad (127)$$

Thus we have $\epsilon' = \ln(1 + q(e' - 1))$ and $\delta' = q\delta$. $\square$

This amplification is critical for making DP-SGD practical: without it, the noise required for privacy would make training impossible.
### 6.4.3 The Moments Accountant

The Moments Accountant provides tight composition bounds for DP-SGD by tracking the moments of the privacy loss random variable $Z$. Define the $\lambda$-th moment as:

$$ \alpha_M(\lambda) = \max_{D \sim D'} \log \mathbb{E}_{o \sim \mathcal{M}(D)} [\exp(\lambda Z)] \quad (128) $$

where $Z = \log \frac{P(\mathcal{M}(D)=o)}{P(\mathcal{M}(D')=o)}$ is the privacy loss random variable, and the maximum is taken over all adjacent datasets $D, D'$.

The moments compose additively: for $k$ applications of mechanism $\mathcal{M}$, $\alpha_{k \times \mathcal{M}}(\lambda) = k \cdot \alpha_{\mathcal{M}}(\lambda)$. After computing the composed moments, we convert back to $(\epsilon, \delta)$-DP using the Chernoff bound. By Markov's inequality:

$$ P(Z > \epsilon) \le e^{-\lambda\epsilon} \mathbb{E}[e^{\lambda Z}] = e^{-\lambda\epsilon + \alpha(\lambda)} \quad (129) $$

Setting this equal to $\delta$ and solving for $\epsilon$:

$$ \epsilon = \min_{\lambda > 1} \left\{ \frac{\alpha(\lambda) - \log(1/\delta)}{\lambda - 1} \right\} \quad (130) $$

The optimization over $\lambda$ finds the tightest bound. In practice, we evaluate this for a range of $\lambda$ values and take the minimum.

For the Gaussian mechanism with $L_2$ sensitivity $\Delta$ and noise scale $\sigma$, the moment can be computed as:

$$ \alpha_G(\lambda) = \frac{\lambda \Delta^2}{2\sigma^2} \quad (131) $$

This formula shows that larger noise ($\sigma$) reduces the moment (better privacy), while larger sensitivity ($\Delta$) increases it (worse privacy).

### 6.4.4 PATE (Private Aggregation of Teacher Ensembles)

PATE trains an ensemble of “teacher” models on disjoint partitions of the private data. To predict on a new input, the teachers vote, and the noisy argmax of the vote is returned. A “student” model is then trained on the public data labeled by the teachers. This avoids exposing the private model weights directly.

<caption>**Algorithm 5 PATE: Student Training**</caption>

Input: Teacher ensemble $\{f_1, \dots, f_K\}$, Unlabeled public data $D_{pub}$, Noise scale $\sigma$
for $x \in D_{pub}$ do
  $n_c \leftarrow \sum_{k=1}^K \mathbb{I}(f_k(x) = c)$ for each class $c$ {Teacher votes}
  $\tilde{n}_c \leftarrow n_c + \text{Lap}(\sigma)$ {Add noise}
  $\tilde{y} \leftarrow \text{arg max}_c \tilde{n}_c$ {Noisy aggregation}
  Add $(x, \tilde{y})$ to student training set
end for
Train student model on labeled data

## 6.5 Secure Multi-Party Computation

Secure Multi-Party Computation (MPC) allows multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other.
### 6.5.1 Problem Formulation

Consider $n$ parties $P_1, \dots, P_n$, each holding private input $x_i$. The goal is to compute $f(x_1, \dots, x_n)$ such that two conditions are met: **Correctness**, meaning all parties learn the correct output $f(x_1, \dots, x_n)$; and **Privacy**, meaning no party learns anything about others' inputs beyond what can be inferred from the output.

**Definition 6.3 (Security Definition).** A protocol $\Pi$ securely computes $f$ if for every adversary $\mathcal{A}$ in the real protocol, there exists a simulator $\mathcal{S}$ in the ideal world such that:

$$ \mathrm{Real}_{\Pi, \mathcal{A}}(x_1, \dots, x_n) \approx_c \mathrm{Ideal}_{f, \mathcal{S}}(x_1, \dots, x_n) \qquad (132) $$

where $\approx_c$ denotes computational indistinguishability, meaning no polynomial-time algorithm can distinguish the two distributions with non-negligible probability.

### 6.5.2 Secret Sharing

Secret sharing is a fundamental building block for MPC. A $(t, n)$-threshold secret sharing scheme splits a secret $s$ into $n$ shares such that any $t$ or more shares can reconstruct $s$, while any fewer than $t$ shares reveal no information about $s$.

**Shamir's Secret Sharing:** To share secret $s \in \mathbb{F}_p$, choose random polynomial $q(x)$ of degree $t-1$ with $q(0) = s$:

$$ q(x) = s + a_1 x + a_2 x^2 + \dots + a_{t-1} x^{t-1} \qquad (133) $$

where $s$ is the secret, and $a_1, \dots, a_{t-1}$ are random coefficients from the field $\mathbb{F}_p$. Each party $i$ receives share $s_i = q(i)$. Reconstruction uses Lagrange interpolation:

$$ s = q(0) = \sum_{i \in S} s_i \cdot \prod_{j \in S, j \neq i} \frac{j}{j-i} \qquad (134) $$

for any set $S$ of $t$ parties.

**Additive Secret Sharing:** For 2-party computation, split $s$ as $s_1, s_2$ where $s_1 + s_2 = s \pmod{p}$. Addition is free: $(a_1 + b_1, a_2 + b_2)$ shares $a + b$.

### 6.5.3 Garbled Circuits

Garbled circuits enable secure two-party computation. Party 1 (garbler) encrypts a boolean circuit $C$ computing $f$, and Party 2 (evaluator) evaluates it without learning intermediate values.

For each wire $w$ in the circuit, the garbler creates two random keys $(k_w^0, k_w^1)$ representing bit values 0 and 1. For each gate with input wires $a, b$ and output wire $c$, the garbler creates a garbled gate table:

$$ \mathrm{Enc}_{k_a^{v_a}, k_b^{v_b}}(k_c^{g(v_a, v_b)}) \quad \text{for } v_a, v_b \in \{0, 1\} \qquad (135) $$

where $\mathrm{Enc}$ is a symmetric encryption scheme, $k_w^v$ is the key for wire $w$ having value $v$, and $g$ is the gate function.

The evaluator receives keys corresponding to input bits (via oblivious transfer for Party 2's inputs) and evaluates gate-by-gate, learning only the output.
### 6.5.4 Applications to Machine Learning

MPC enables privacy-preserving ML in several settings:

**Secure Inference:** A model owner and data owner can jointly compute $f(x)$ where the model owner learns nothing about $x$ and the data owner learns nothing about model parameters beyond the prediction.

**Secure Training:** Multiple data owners can train a joint model without sharing raw data. Each iteration involves secure aggregation of gradients.

**Challenges:**

* **Communication Overhead:** MPC protocols require multiple rounds of message exchanges between parties, introducing significant network latency that can make real-time applications impractical. For example, securely computing a single neural network forward pass might require $O(d \cdot L)$ communication rounds for $d$ input dimensions and $L$ layers, where each round incurs network latency (typically 10-100ms for internet connections). In practice, a ResNet-50 inference with MPC could take seconds to minutes instead of milliseconds, making it unsuitable for interactive applications like autonomous driving decision-making. The communication complexity scales with circuit depth—deeper computations require more sequential message passing. Optimizations like circuit pipelining and batching multiple evaluations can amortize costs, but fundamentally cannot eliminate the sequential dependency between computational layers.

* **Computational Complexity:** Cryptographic operations underlying MPC, particularly secure multiplication gates, are computationally expensive compared to plaintext operations. A secure multiplication requires homomorphic encryption operations or oblivious transfer protocols that are $10^3$ to $10^6$ times slower than native CPU multiplication. For instance, while a standard matrix multiplication $C = AB$ for $n \times n$ matrices takes $O(n^3)$ floating-point operations completing in microseconds on modern hardware, the secure version using garbled circuits requires generating and evaluating $O(n^3)$ encrypted gate tables, potentially taking minutes to hours for moderately sized matrices ($n \approx 1000$). The asymmetry between addition and multiplication costs means circuit optimization must carefully balance these operations—addition in additive secret sharing is essentially free (local addition of shares), while multiplication requires interaction between parties.

* **Non-linear Activation Functions:** Standard neural network activations like ReLU ($\max(0, x)$), sigmoid ($\sigma(x) = 1/(1 + e^{-x})$), and softmax require comparison or exponential operations that are extremely expensive to compute securely. The ReLU function $f(x) = \max(0, x)$ requires secure comparison to determine if $x > 0$, implemented via garbled circuits with depth $O(\log k)$ for $k$-bit precision, adding significant overhead to each layer. Practical MPC systems often approximate non-linear functions using low-degree polynomials (e.g., $ReLU(x) \approx x^2$ for $x$ near 0) or use specialized protocols like CrypTFlow2 [30] that combine different MPC techniques. Alternatively, some systems replace ReLU with quadratic activations that are MPC-friendly but may reduce model accuracy. The fundamental tension is that functions easy to compute in plaintext (comparisons, table lookups, transcendental functions) become bottlenecks in the encrypted domain.
### 6.5.5 Homomorphic Encryption

Homomorphic encryption (HE) allows computation on encrypted data. A fully homomorphic encryption scheme supports:

$$ \mathrm{Enc}(a) \oplus \mathrm{Enc}(b) = \mathrm{Enc}(a + b) \qquad (136) $$

$$ \mathrm{Enc}(a) \otimes \mathrm{Enc}(b) = \mathrm{Enc}(a \cdot b) \qquad (137) $$

where $\oplus$ and $\otimes$ are operations on ciphertexts that correspond to addition and multiplication on plaintexts.

The client encrypts input $x$, sends $\mathrm{Enc}(x)$ to the server, which computes $\mathrm{Enc}(f(x))$ and returns it. The client decrypts to obtain $f(x)$.

**Challenges:** FHE has high computational overhead (orders of magnitude slower than plaintext). Practical schemes like CKKS support approximate arithmetic on real numbers but accumulate noise that limits computation depth.

The privacy guarantee of PATE depends on the consensus among teachers. When teachers agree, the noise has little effect on the label, and privacy cost is low. When teachers disagree, more privacy budget is consumed. The Confident-GNMAX aggregation mechanism formalizes this:

$$ \tilde{y} = \begin{cases} \arg \max_c (n_c + \mathcal{N}(0, \sigma_2^2)) & \text{if } \max_c n_c + \mathcal{N}(0, \sigma_1^2) > T \\ \perp (\text{abstain}) & \text{otherwise} \end{cases} \qquad (138) $$

where $n_c$ is the vote count for class $c$, $\sigma_1, \sigma_2$ are noise scales, and $T$ is a threshold.

### 6.5.6 Local Differential Privacy

In the *local* model of DP, each user randomizes their own data before sending it to the aggregator. This provides stronger privacy guarantees (no trusted curator) but requires more noise.

**Definition 6.4** (Local Differential Privacy). A randomized mechanism $\mathcal{M}: \mathcal{X} \to \mathcal{Y}$ is $\epsilon$-locally differentially private if for all $x, x' \in \mathcal{X}$ and all $S \subseteq \mathcal{Y}$:

$$ P(\mathcal{M}(x) \in S) \le e^{\epsilon} P(\mathcal{M}(x') \in S) \qquad (139) $$

where $\epsilon$ is the privacy budget.

**Randomized Response** is the canonical LDP mechanism. For a binary attribute $b \in \{0, 1\}$:

$$ \mathcal{M}(b) = \begin{cases} b & \text{with probability } \frac{e^{\epsilon}}{1+e^{\epsilon}} \\ 1-b & \text{with probability } \frac{1}{1+e^{\epsilon}} \end{cases} \qquad (140) $$

The aggregator can estimate the true mean from noisy responses:

$$ \hat{p} = \frac{(1 + e^{\epsilon})\bar{y} - 1}{e^{\epsilon} - 1} \qquad (141) $$

where $\bar{y}$ is the empirical mean of the randomized responses.
## 6.6 Attacks on Privacy

### 6.6.1 Reconstruction Attacks

The Dinur-Nissim theorem states that if a mechanism answers $O(N)$ queries with error $o(\sqrt{N})$, an adversary can reconstruct the underlying database with high probability. This fundamental limit implies that we cannot answer an infinite number of queries accurately while preserving privacy.

**Theorem 6.2 (Dinur-Nissim Lower Bound).** Let $D \in \{0, 1\}^N$ be a database. Any mechanism that answers $c \cdot N$ linear queries with error at most $o(\sqrt{N})$ for each query enables reconstruction of $D$ with high probability.

*Proof Sketch.* Consider $c \cdot N$ random subset queries $S_1, \dots, S_{cN}$, where each query asks for $\sum_{i \in S_j} D[i]$. With high probability, the matrix $A$ defined by $A_{jk} = I(k \in S_j)$ has full column rank when $c$ is large enough. If we receive noisy answers $\tilde{a}_j = a_j + \text{noise}_j$ where $|\text{noise}_j| = o(\sqrt{N})$, we can solve the linear system $A \cdot D \approx \tilde{a}$ using least squares. The Gaussian elimination will recover $D$ exactly if the total error is small enough. □

### 6.6.2 Membership Inference Attacks (MIA)

MIA aims to determine if a specific sample $x$ was in the training set. The attack exploits the generalization gap: models tend to have lower loss (higher confidence) on training data than on test data.

$$ \mathcal{A}(x, f) = \mathbb{I}(\ell(f(x), y) < \tau) \qquad (142) $$

where $\mathbb{I}(\cdot)$ is the indicator function, $\ell$ is the loss function, and $\tau$ is a threshold. If the loss is below a threshold $\tau$, the attacker predicts “Member”. DP provides a theoretical upper bound on the success of any such attack, effectively closing the generalization gap.

**Theorem 6.3 (MIA Upper Bound under DP).** If model $f$ is trained using an $(\epsilon, \delta)$-DP algorithm, then for any membership inference attack $\mathcal{A}$:

$$ \text{Advantage}_{\mathcal{A}} = |P(\mathcal{A}(x) = 1 | x \in D) - P(\mathcal{A}(x) = 1 | x \notin D)| \le e^{\epsilon} - 1 + \delta \qquad (143) $$

### 6.6.3 Model Inversion Attacks

Model inversion attacks attempt to reconstruct training data or sensitive attributes from model access. Given a model $f$ trained on sensitive features $X$ to predict target $Y$, an attacker observing $f$ and knowing $Y$ attempts to infer $X$.

For a linear model $f(x) = w^T x$, if the attacker knows the output $y = f(x)$ and has access to the weights $w$, they can attempt to solve for $x$. For neural networks, gradient-based optimization can be used:

$$ x^* = \arg\min_x \|f(x) - y_{\text{target}}\|^2 + \lambda R(x) \qquad (144) $$

where $R(x)$ is a regularizer encouraging realistic inputs (e.g., total variation for images).

### 6.6.4 Attribute Inference Attacks

Given a trained model and partial knowledge of an individual's features, attribute inference attacks attempt to predict sensitive attributes. If model $f$ was trained on features $(X_1, X_2, \dots, X_d)$ and
an attacker knows $(x_2, \dots, x_d)$ and $y$, they can optimize:

$$ \hat{x}_1 = \arg\max_{x_1} P(Y = y | X_1 = x_1, X_2 = x_2, \dots) \qquad (145) $$

These attacks are particularly concerning when models inadvertently learn to predict sensitive attributes as features for the main task.

## 6.7 Exercises

1. **Laplace Mechanism:**

(a) Prove that the Laplace mechanism $M(x) = f(x) + Lap(\Delta f/\epsilon)$ satisfies $\epsilon$-DP.

(b) Compare the noise magnitude of Laplace vs. Gaussian mechanisms for the same $\epsilon, \delta$.

2. **DP-SGD:**

(a) Implement DP-SGD from scratch in PyTorch.

(b) Train a model on MNIST with $\epsilon = 1.0$.

(c) Plot the privacy loss curve using the Moments Accountant.

3. **Membership Inference:**

(a) Train a model on half of CIFAR-10 (members) and evaluate on the other half (non-members).

(b) Plot the distribution of loss values for members vs. non-members.

(c) Calculate the attack accuracy of a simple threshold-based MIA.

4. **Composition Theorems:**

(a) Prove the basic composition theorem: $k$ applications of $\epsilon$-DP give $(k\epsilon)$-DP.

(b) Implement and compare: basic composition, advanced composition, and Rényi DP composition.

(c) For $k = 100$ queries with $\epsilon = 0.1$ each, compute the total $\epsilon$ under each composition rule.

(d) Visualize how privacy budget grows with the number of queries.

5. **Local Differential Privacy:**

(a) Implement randomized response for binary attributes.

(b) Estimate the population mean from locally privatized data.

(c) Compare variance of estimates under local vs. central DP.

(d) Implement the RAPPOR protocol for frequency estimation.

6. **PATE Framework:**

(a) Train an ensemble of 100 “teacher” models on disjoint data partitions.

(b) Implement the noisy argmax aggregation mechanism.

(c) Train a “student” model using the aggregated labels.

(d) Compute the data-dependent privacy bound using the smooth sensitivity analysis.

7. **Model Inversion Attack:**
(a) Train a face recognition model on a subset of CelebA.

(b) Given only a class label (person ID), reconstruct a representative face.

(c) Compare reconstruction quality with and without regularization.

(d) Test if DP training reduces reconstruction quality.

## 8. Attribute Inference Attack:

(a) Train a classifier that uses but does not predict a sensitive attribute.

(b) Implement an attribute inference attack using the model's outputs.

(c) Measure attack success rate vs. baseline (predicting majority class).

(d) Test mitigation strategies: removing correlated features, adversarial debiasing.

## 9. Reconstruction Attack:

(a) Implement the Dinur-Nissim attack on a synthetic database.

(b) Query a counting query mechanism and attempt reconstruction.

(c) Verify that reconstruction fails when queries are answered with $O(\sqrt{N})$ noise.

(d) Demonstrate successful reconstruction with lower noise levels.

## 10. Privacy Amplification:

(a) Implement privacy amplification by subsampling.

(b) Compare privacy guarantees with and without subsampling.

(c) Verify the amplification bound experimentally.

(d) Implement privacy amplification by shuffling for the local model.
# 7 Explainability and Interpretability

## 7.1 Foundations of Explainable AI (XAI)

As machine learning models, particularly deep neural networks, become more complex, their decision-making processes become increasingly opaque. This “black box” nature poses significant challenges for trust, accountability, and debugging. Explainable AI (XAI) aims to make the internal logic of these systems transparent and understandable to humans.

We distinguish between two related but distinct concepts:

* **Interpretability:** The degree to which a human can understand the cause of a decision. A linear regression model with few features is intrinsically interpretable because the coefficients directly relate inputs to outputs.

* **Explainability:** The ability to provide a post-hoc description of why a model made a specific prediction. A deep neural network is not interpretable, but we can generate an explanation (e.g., a heatmap) to justify its output.

## 7.2 Taxonomy of XAI Methods

XAI methods can be categorized along several dimensions. **Intrinsic vs. Post-hoc** distinguishes between models that are interpretable by design (e.g., decision trees, linear models) and methods that analyze a trained black-box model without modifying its structure. **Global vs. Local** refers to the scope of the explanation: global methods describe the model's behavior across the entire input space, while local methods focus on justifying a specific prediction for a single input instance. Finally, **Model-Agnostic vs. Model-Specific** differentiates between methods that treat the model as a black box (requiring only input-output access, like LIME or SHAP) and those that exploit internal structures like gradients or attention weights (like Integrated Gradients).

## 7.3 Feature Attribution Methods

Feature attribution methods assign a “relevance” score to each input feature, indicating its contribution to the model’s prediction.

### 7.3.1 Shapley Values

Originating from cooperative game theory, Shapley values provide a unique solution to the problem of fairly distributing a “payout” (prediction) among “players” (features). For a model $f$ and an input $x$, the Shapley value $\phi_i$ for feature $i$ is defined as the average marginal contribution of feature $i$ across all possible coalitions of features:

$$ \phi_i(f, x) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(|N| - |S| - 1)!}{|N|!} [f_x(S \cup \{i\}) - f_x(S)] \quad (146) $$

where $N$ is the set of all features, $S$ is a subset of features not containing $i$, $|S|$ is the size of the subset, and $f_x(S)$ is the prediction function evaluated with only features in $S$ present.

Shapley values are the *only* attribution method that satisfies four desirable axioms. **Efficiency** requires that the sum of attributions equals the difference between the prediction and the
baseline ($\sum \phi_i = f(x) - \mathbb{E}[f(x)]$). **Symmetry** ensures that if two features contribute equally to all coalitions, they receive equal attribution. The **Dummy** axiom states that a feature that never changes the prediction receives zero attribution. Finally, **Additivity** guarantees that the attribution for a sum of two models is the sum of their individual attributions.

**Theorem 7.1 (Uniqueness of Shapley Values).** *The Shapley value is the unique attribution method satisfying Efficiency, Symmetry, Dummy, and Additivity.*

*Proof Sketch.* Consider the set of all $2^{|N|}$ coalitions. For each coalition $S$, define the characteristic function $v(S) = f_x(S)$. The four axioms impose a system of linear constraints on the attributions $\phi_i$. Efficiency gives one equation ($\sum_i \phi_i = v(N) - v(\emptyset)$). Symmetry and Dummy reduce the degrees of freedom by identifying features with equal contributions. One can show inductively that these constraints uniquely determine each $\phi_i$, and the resulting value is precisely the Shapley formula. The proof relies on showing that any other attribution satisfying these axioms must equal the Shapley value for all possible coalitional games. □

Exact computation is exponential in the number of features ($O(2^N)$). In practice, we use approximations like **KernelSHAP**, which casts the computation as a weighted linear regression problem, or **DeepSHAP**, which leverages the compositional structure of neural networks.

### 7.3.2 LIME (Local Interpretable Model-agnostic Explanations)

LIME explains a complex model $f$ by approximating it locally with an interpretable model $g$ (e.g., a sparse linear model). The objective is to minimize the following loss function:

$$ \xi(x) = \arg \min_{g \in \mathcal{G}} \mathcal{L}(f, g, \pi_x) + \Omega(g) \quad (147) $$

where $\mathcal{L}$ measures the fidelity of $g$ to $f$ in the neighborhood of $x$, $\pi_x$ is a proximity kernel (e.g., exponential kernel) that weights samples based on their distance to $x$, and $\Omega(g)$ penalizes the complexity of the explanation (e.g., number of non-zero coefficients). LIME generates a dataset of perturbed samples around $x$, queries the black box $f$ for labels, and trains $g$ on this weighted dataset. While powerful, LIME suffers from instability: small changes in the sampling can lead to different explanations.

### 7.3.3 Gradient-Based Methods

For differentiable models, we can use gradients to estimate feature importance. **Saliency Maps (Vanilla Gradients)** compute $M_i(x) = |\frac{\partial f(x)}{\partial x_i}|$, measuring the sensitivity of the output to infinitesimal changes in the input. However, it suffers from “saturation” (gradients can be zero even if the feature is important) and noise. **Integrated Gradients (IG)** [32] addresses the saturation problem by accumulating gradients along a straight path from a baseline $x'$ (usually a zero vector) to the input $x$:

$$ IG_i(x) = (x_i - x'_i) \int_{\alpha=0}^{1} \frac{\partial f(x' + \alpha(x - x'))}{\partial x_i} d\alpha \quad (148) $$

where $x$ is the input, $x'$ is the baseline, $\alpha$ is the interpolation parameter, and $\frac{\partial f}{\partial x_i}$ is the gradient of $f$ with respect to feature $i$. IG satisfies the axiom of **Completeness**: $\sum IG_i(x) = f(x) - f(x')$.

*Proof of Completeness.* Consider the path $\gamma(\alpha) = x' + \alpha(x - x')$ for $\alpha \in [0, 1]$. By the chain rule:

$$ \frac{d}{d\alpha} f(\gamma(\alpha)) = \sum_{i=1}^{n} \frac{\partial f}{\partial x_i}(\gamma(\alpha)) \cdot \frac{d\gamma_i}{d\alpha} = \sum_{i=1}^{n} \frac{\partial f}{\partial x_i}(\gamma(\alpha)) \cdot (x_i - x'_i) \quad (149) $$
where $\gamma(\alpha)$ is the path function. Integrating both sides from $\alpha = 0$ to $\alpha = 1$:

$$ \int_0^1 \frac{d}{d\alpha} f(\gamma(\alpha)) d\alpha = \int_0^1 \sum_{i=1}^n (x_i - x_i') \frac{\partial f}{\partial x_i}(\gamma(\alpha)) d\alpha \quad (150) $$

$$ f(\gamma(1)) - f(\gamma(0)) = \sum_{i=1}^{n} (x_i - x_i') \int_{0}^{1} \frac{\partial f}{\partial x_i}(\gamma(\alpha)) d\alpha \quad (151) $$

$$ f(x) - f(x') = \sum_{i=1}^{n} IG_i(x) \quad (152) $$

This follows from the fundamental theorem of calculus. □

## 7.4 Concept-Based Explanations

Feature attribution tells us where the model is looking (e.g., pixels), but not what it sees (e.g., “floppy ears”). Concept-based methods bridge this gap.

### 7.4.1 Concept Bottleneck Models (CBM)

CBMs enforce a structure where the input $x$ is first mapped to a set of human-interpretable concepts $c$, and then these concepts are used to predict the target $y$:

$$ x \xrightarrow{h} c \xrightarrow{g} y \quad (153) $$

where $x$ is the input, $c$ represents the concepts, $y$ is the target, $h$ is the concept mapping function, and $g$ is the prediction function. This architecture allows for **intervenability**: if the model predicts “Wolf” because it wrongly detected “Snow”, a human expert can correct the concept “Snow” to “Grass” and observe the updated prediction.

### 7.4.2 Testing with Concept Activation Vectors (TCAV)

TCAV quantifies the sensitivity of a prediction to a high-level concept (e.g., “striped”) even if that concept was not explicitly part of the training labels. It learns a vector $v_C$ in the activation space of a layer that separates examples of the concept from random examples. The conceptual sensitivity is then given by the directional derivative:

$$ S_{C,k}(x) = \nabla h_k(x) \cdot v_C \quad (154) $$

where $h_k(x)$ is the activation at layer $k$, and $v_C$ is the concept vector.

## 7.5 Evaluating Explanations

Evaluating XAI is notoriously difficult due to the lack of ground truth. Common metrics include **Fidelity**, which measures if the explanation accurately reflects the model’s behavior (e.g., by removing important features and checking if the prediction drops); and **Robustness**, which checks if similar inputs yield similar explanations (LIME often fails this). Additionally, **Sanity Checks** [2] are crucial: many saliency methods (like Guided Backprop) act merely as edge detectors and do not depend on the model parameters. It is crucial to verify that randomizing the model weights destroys the explanation.
## 7.6 Algorithmic Recourse and Counterfactual Explanations

While feature attribution explains why a decision was made, counterfactual explanations answer the question: “What would need to change for the outcome to be different?”

### 7.6.1 The Counterfactual Explanation Problem

**Definition 7.1 (Counterfactual Explanation).** Given a classifier $f: \mathcal{X} \to \{0, 1\}$, an input $x$ with $f(x) = 0$ (unfavorable outcome), a counterfactual explanation is an input $x'$ such that:

1. $f(x') = 1$ (desired outcome)

2. $x'$ is “close” to $x$ under some distance measure $d(x, x')$

The optimization problem is:

$$x^* = \arg \min_{x'} d(x, x') \quad \text{s.t.} \quad f(x') = 1 \qquad (155)$$

where $d(\cdot, \cdot)$ is a distance metric, $f$ is the classifier, and $x'$ is the counterfactual instance.

The choice of distance function $d$ is critical and encodes assumptions about actionability. Common choices include:

* $L_1$ norm: Promotes sparsity (few features change)

* $L_2$ norm: Smooth changes across features

* Weighted norms: Account for feature costs (e.g., changing age is impossible)

* Mahalanobis distance: Account for feature correlations

### 7.6.2 Wachter’s Method

[34] proposed solving the unconstrained optimization problem:

$$\min_{x'} \lambda(f(x') - 1)^2 + d(x, x') \qquad (156)$$

where $\lambda$ is a regularization parameter balancing validity and proximity. For differentiable models, this can be solved via gradient descent. The hyperparameter $\lambda$ balances validity (reaching the desired class) and proximity (staying close to $x$).

### 7.6.3 Actionability Constraints

Not all features can be changed (e.g., age, race, place of birth). We partition features into:

* **Immutable**: Cannot be changed under any circumstance ($x'_i = x_i$)

* **Actionable**: Can be changed by the individual

* **Increasing-only**: Can only increase (e.g., education level, years of experience)

The constrained optimization problem becomes:

$$\min_{x'} d(x, x') \quad \text{s.t.} \quad f(x') = 1, x'_i = x_i \forall i \in \mathcal{I}_{\text{immutable}}, x'_j \ge x_j \forall j \in \mathcal{I}_{\text{increasing}} \qquad (157)$$

where $\mathcal{I}_{\text{immutable}}$ is the set of immutable features and $\mathcal{I}_{\text{increasing}}$ is the set of increasing-only features.
### 7.6.4 DICE: Diverse Counterfactual Explanations

A single counterfactual may not be the only option. DICE ([26]) generates a diverse set of counterfactuals by adding a diversity term:

$$ \min_{\{x'_1, \dots, x'_k\}} \sum_{i=1}^{k} [\lambda_1 \text{yloss}(f(x'_i), 1) + d(x, x'_i)] - \lambda_2 \sum_{i \neq j} \text{dpp\_diversity}(x'_i, x'_j) \quad (158) $$

where $k$ is the number of counterfactuals, yloss is the loss function for the target class, dpp\_diversity is the diversity metric, and $\lambda_1, \lambda_2$ are hyperparameters.

### 7.6.5 Causal Counterfactuals

Standard counterfactual methods may suggest changes that violate causal relationships in the real world. For example, suggesting “lower your BMI without changing your diet or exercise” is meaningless.

**Definition 7.2 (Causally Grounded Counterfactual).** Given an SCM $\mathcal{M}$ with structural equations $V_i = f_i(Pa_i, U_i)$, a causally grounded counterfactual modifies only the exogenous variables or actionable root causes, then propagates changes through the causal graph:

$$ x'_{\text{downstream}} = f_{\text{downstream}}(x'_{\text{actionable}}, u) \quad (159) $$

where $x'_{\text{actionable}}$ are the modified actionable variables, $u$ represents exogenous variables, and $f_{\text{downstream}}$ propagates the changes.

This ensures that downstream features are updated consistently according to the causal model.

### 7.6.6 Recourse Robustness

A critical issue is that the model may change after the counterfactual is provided. If a user follows the recommended changes but the model has been retrained, they may not achieve the desired outcome.

**Definition 7.3 (Robust Recourse).** A counterfactual $x'$ provides $\epsilon$-robust recourse if:

$$ f_{\theta'}(x') = 1 \quad \forall \theta' \in \mathcal{B}(\theta, \epsilon) \quad (160) $$

where $\mathcal{B}(\theta, \epsilon)$ is the uncertainty set of model parameters with radius $\epsilon$.

Robust recourse can be achieved by optimizing:

$$ \min_{x'} d(x, x') \quad \text{s.t.} \quad \min_{\theta' \in \mathcal{B}(\theta, \epsilon)} f_{\theta'}(x') \geq 0.5 \quad (161) $$

where the constraint ensures the prediction remains valid under the worst-case parameter perturbation.

### 7.6.7 Algorithmic Recourse via Integer Programming

For tree-based models (Random Forests, Gradient Boosted Trees), counterfactual search can be formulated as a Mixed Integer Program (MIP).
For a single decision tree with leaves L and decision paths $P_\ell$ for each leaf $\ell$:

$$ \min_{x',z} d(x, x') \qquad (162) $$

$$ \text{s.t.} \quad \sum_{\ell \in L^+} z_{\ell} = 1 \quad (\text{reach exactly one positive leaf}) \qquad (163) $$

$$ x'_{j} \le u_{j,\ell} + M(1 - z_{\ell}) \quad \forall j, \ell \qquad (164) $$

$$ x'_{j} \ge l_{j,\ell} - M(1 - z_{\ell}) \quad \forall j, \ell \qquad (165) $$

$$ z_{\ell} \in \{0, 1\} \qquad (166) $$

where $z_\ell$ is a binary variable indicating if leaf $\ell$ is active, $L^+$ is the set of positive leaves, $u_{j,\ell}$ and $l_{j,\ell}$ are feature bounds, and $M$ is a large constant.

## Exercises

### 1. Shapley Values Implementation:

(a) Implement the exact Shapley value calculation for a toy model with $N = 4$ features.

(b) Implement the Monte Carlo approximation and plot the convergence of the estimates as the number of samples increases.

(c) Compare the results with the 'shap' library in Python.

### 2. LIME and Stability:

(a) Use LIME to explain a Random Forest classifier on the Iris dataset.

(b) Run LIME multiple times for the same instance with different random seeds. Quantify the stability of the explanations using the Jaccard similarity of the top-k features.

### 3. Gradient-Based Explanations:

(a) Train a simple CNN on MNIST.

(b) Implement Vanilla Gradients and Integrated Gradients from scratch.

(c) Visualize the explanations for a specific digit.

(d) Perform the “Model Parameter Randomization Test”: Randomize the weights of the top layer and check if the heatmap changes significantly.

### 4. Concept-Based Explanations:

(a) Implement TCAV for a pre-trained ImageNet classifier.

(b) Define concept directions for textures (striped, dotted, smooth).

(c) Measure the sensitivity of class predictions (e.g., “zebra”) to each concept.

(d) Compare TCAV scores across different classes to validate concept relevance.

### 5. Counterfactual Explanations:

(a) Implement Wachter’s method for generating counterfactuals.

(b) Add actionability constraints (immutable features, monotonic features).

(c) Generate diverse counterfactuals using the DiCE algorithm.

(d) Evaluate counterfactual quality using proximity, sparsity, and plausibility metrics.

### 6. Attention-Based Explanations:
(a) Train a Transformer model on a text classification task.

(b) Visualize attention weights for sample predictions.

(c) Test if attention weights are faithful explanations by perturbing high-attention tokens.

(d) Compare attention-based explanations with gradient-based methods on the same inputs.

7. Explanation Evaluation:

(a) Implement the “deletion” and “insertion” faithfulness metrics.

(b) Compare faithfulness scores for LIME, SHAP, and Integrated Gradients.

(c) Measure explanation stability under input perturbations.

(d) Conduct a user study to evaluate explanation comprehensibility.

8. Rule Extraction:

(a) Train a neural network on tabular data (e.g., Adult Census).

(b) Extract decision rules that approximate the network's behavior.

(c) Measure fidelity: how often do the rules agree with the network?

(d) Trade off rule complexity (number of rules, conditions) with fidelity.
# 8 Causal Inference and Machine Learning

## 8.1 The Ladder of Causation

Judea Pearl [27] distinguishes three levels of cognitive ability, known as the “Ladder of Causation”. The first level, **Association** (*P*(y|x)), involves observing correlations (“Seeing”)—asking how observing X changes belief in Y. This is the domain of standard statistics and most machine learning. The second level, **Intervention** (*P*(y|do(x))), involves acting (“Doing”)—asking what happens if we force X to take a value. The third and highest level, **Counterfactuals** (*P*(y_x|x', y')), involves imagining (“Why?”)—reasoning about hypothetical worlds to determine if X caused Y or what would have happened had we acted differently.

## 8.2 Structural Causal Models (SCM)

A Structural Causal Model is a tuple $\mathcal{M} = \langle U, V, F, P(U) \rangle$ where:

* $U = \{U_1, \dots, U_m\}$ is a set of exogenous (background) variables determined by factors outside the model.

* $V = \{V_1, \dots, V_n\}$ is a set of endogenous variables determined by variables in the model.

* $F = \{f_1, \dots, f_n\}$ is a set of structural equations $v_i = f_i(pa_i, u_i)$, where $pa_i \subseteq V \setminus \{v_i\}$ are the parents of $v_i$.

* $P(U)$ is a probability distribution over the exogenous variables.

The model implies a Causal Diagram (DAG) where arrows point from parents to children.

### 8.2.1 d-Separation

A path *p* is d-separated (blocked) by a set of nodes *Z* if it satisfies one of two conditions: (1) *p* contains a chain *i* → *m* → *j* or a fork *i* ← *m* → *j* such that the middle node *m* is in *Z*; or (2) *p* contains a collider *i* → *m* ← *j* such that the middle node *m* is NOT in *Z* and no descendant of *m* is in *Z*. If *X* and *Y* are d-separated by *Z*, they are conditionally independent given *Z* in any distribution compatible with the graph: $X \perp Y|Z$.

## 8.3 Interventions and the Do-Operator

The *do*-operator, denoted $do(X = x)$, represents an intervention that forces the variable $X$ to take the value $x$, regardless of the structural equation $f_X$. Graphically, this corresponds to removing all incoming arrows to $X$. The interventional distribution $P(Y|do(X = x))$ is generally different from the observational distribution $P(Y|X = x)$.

### 8.3.1 The Back-Door Criterion

A set of variables $Z$ satisfies the Back-Door Criterion relative to an ordered pair $(X, Y)$ if:

1. No node in $Z$ is a descendant of $X$.

2. $Z$ blocks every path between $X$ and $Y$ that contains an arrow into $X$ (back-door paths).
If Z satisfies the Back-Door Criterion, we can identify the causal effect via the Adjustment Formula:

$$P(Y = y | do(X = x)) = \sum_{z} P(Y = y | X = x, Z = z) P(Z = z) \quad (167)$$

where Z is the set of variables satisfying the Back-Door Criterion.

## 8.4 The Do-Calculus

When the Back-Door Criterion is not applicable (e.g., due to unobserved confounders), we can use the rules of do-calculus to transform interventional probabilities into observational ones. Let $G_{\bar{X}}$ denote the graph with arrows into X removed, and $G_{\bar{X}}$ denote the graph with arrows out of X removed. The three rules are:

* Rule 1 (Insertion/deletion of observations): $P(y|do(x), z, w) = P(y|do(x), w)$ if $(Y \perp Z|X, W)_{G_{\bar{X}}}$.

* Rule 2 (Action/observation exchange): $P(y|do(x), do(z), w) = P(y|do(x), z, w)$ if $(Y \perp Z|X, W)_{G_{\bar{X}Z}}$.

* Rule 3 (Insertion/deletion of actions): $P(y|do(x), do(z), w) = P(y|do(x), w)$ if $(Y \perp Z|X, W)_{G_{\bar{X}Z(W)}}$, where $Z(W)$ is the set of Z-nodes that are not ancestors of any W-node in $G_{\bar{X}}$.

**Proof Sketch of Rule 1.** Rule 1 says we can ignore observed variables Z that are conditionally independent of Y given (X, W) in the manipulated graph $G_{\bar{X}}$ (with arrows into X removed). Under intervention do(x), the distribution of Y depends only on causal paths from X to Y. If $Z \perp Y|(X, W)$ in $G_{\bar{X}}$, then Z provides no additional information about Y beyond what (X, W) already provide. By the definition of conditional independence in probability, we have $P(y|do(x), z, w) = P(y|do(x), w)$. The removal of arrows into X in $G_{\bar{X}}$ reflects that we’ve already intervened on X, so its parents no longer matter. □

**Proof Sketch of Rule 2.** Rule 2 allows exchanging an intervention do(z) for an observation z when Z is conditionally independent of Y given (X, W) in the graph $G_{\bar{X}Z}$ (arrows into X removed, arrows out of Z removed). Removing arrows out of Z corresponds to treating Z as if it were intervened upon (its value doesn’t affect its children). If under this manipulation $Z \perp Y|(X, W)$, then whether we set Z by intervention or observe it makes no difference to the distribution of Y. This is because the paths from Z to Y are already blocked by (X, W), so the mechanism that generates Z is irrelevant. □

**Proof Sketch of Rule 3.** Rule 3 allows removing an intervention do(z) entirely when Z is conditionally independent of Y given (X, W) in $G_{\bar{X}Z(W)}$ (arrows into X and into nodes in Z(W) removed). This graph reflects a scenario where we’ve intervened on both X and Z. If $Z \perp Y|(X, W)$ in this graph, then Z has no causal effect on Y beyond what’s already captured by (X, W). Therefore, the intervention on Z is redundant and can be removed. The notation $\bar{Z}(W)$ denotes the removal of incoming arrows to the nodes in Z(W). □

Shpitser and Pearl (2006) proved that these three rules are complete: if a causal effect is identifiable, it can be derived using these rules.
## 8.5 Counterfactuals

A counterfactual query asks: “Given that we observed $X = x$ and $Y = y$, what would $Y$ have been if $X$ had been $x'$?” This is denoted as $P(Y_{x'} = y'|X = x, Y = y)$. Computing counterfactuals involves three steps:

1. **Abduction:** Use the evidence $E = \{X = x, Y = y\}$ to update the distribution of exogenous variables $P(U) \to P(U|E)$.

2. **Action:** Modify the model $\mathcal{M}$ by replacing the equation for $X$ with $X = x'$, creating a sub-model $\mathcal{M}_{x'}$.

3. **Prediction:** Compute the probability of $Y = y'$ in the modified model $\mathcal{M}_{x'}$ using the updated posterior $P(U|E)$.

## 8.6 Causal Fairness

Standard fairness metrics (like Demographic Parity) are based on correlations. Causal fairness defines fairness in terms of the causal graph.

**Definition 8.1 (Counterfactual Fairness).** A predictor $\hat{Y}$ is counterfactually fair if for any individual defined by features $X = x$ and sensitive attribute $A = a$:

$$P(\hat{Y}_{A \leftarrow a}(U) = y | X = x, A = a) = P(\hat{Y}_{A \leftarrow a'}(U) = y | X = x, A = a) \quad (168)$$

where $\hat{Y}_{A \leftarrow a}(U)$ denotes the potential outcome of the predictor under the intervention $A \leftarrow a$, given the background variables $U$.

This means the prediction would not have changed if the individual's sensitive attribute had been different, keeping all other “non-descendant” factors constant.

## 8.7 Exercises

1. **Simpson's Paradox:**

(a) Construct a dataset where $P(Y = 1|T = 1) > P(Y = 1|T = 0)$ but $P(Y = 1|do(T = 1)) < P(Y = 1|do(T = 0))$.

(b) Draw the causal graph and identify the confounder.

(c) Calculate the Average Treatment Effect (ATE) using the adjustment formula.

2. **Do-Calculus:**

(a) Prove Rule 1 of the do-calculus using d-separation.

(b) Given the “Front-Door” graph $X \to Z \to Y$ with an unobserved confounder $U$ affecting $X$ and $Y$, prove that $P(y|do(x))$ is identifiable and derive the formula.

3. **Counterfactuals:**

(a) Consider a linear SCM: $X = U_X, Y = \beta X + U_Y$.

(b) Given observation $X = 1, Y = 2$, calculate the counterfactual $Y_{X=0}$.

(c) How does the result change if the relationship is non-linear?

4. **Causal Discovery:**
(a) Implement the PC algorithm for learning causal graphs from observational data.

(b) Generate synthetic data from a known SCM and test if PC recovers the correct skeleton.

(c) Compare with score-based methods (GES) and continuous optimization (NOTEARS).

(d) Discuss the identifiability assumptions required by each method.

**5. Instrumental Variables:**

(a) Explain why naive regression fails when there is unmeasured confounding.

(b) Implement Two-Stage Least Squares (2SLS) for a simple model with one instrument.

(c) Verify the validity assumptions: relevance ($Cov(Z, X) \neq 0$) and exclusion restriction.

(d) Compare 2SLS estimates with naive OLS on simulated data with known ground truth.

**6. Causal Effect Estimation:**

(a) Implement propensity score matching for ATE estimation.

(b) Compare with Inverse Probability Weighting (IPW) and Doubly Robust estimation.

(c) Use the IHDP benchmark dataset to evaluate bias and variance of different estimators.

(d) Implement CATE estimation using causal forests or BART.

**7. Counterfactual Fairness Implementation:**

(a) Build a causal graph for a hiring scenario with features: education, experience, gender, and qualifications.

(b) Identify which features are descendants of the protected attribute.

(c) Train a counterfactually fair classifier that only uses non-descendants.

(d) Compare accuracy and fairness metrics with an unconstrained classifier.

**8. Mediation Analysis:**

(a) Decompose the total effect into direct and indirect effects for a simple mediation model $X \to M \to Y$.

(b) Derive the natural direct effect (NDE) and natural indirect effect (NIE).

(c) Implement the mediation formula and test on simulated data.

(d) Discuss when mediation effects are identifiable under unmeasured confounding.
# 9 Federated Learning

## 9.1 Introduction to Decentralized Learning

Federated Learning (FL) is a distributed machine learning paradigm where multiple clients (e.g., mobile devices, hospitals) collaboratively train a model under the coordination of a central server, without sharing their raw training data. The core principle is “bring the code to the data, not the data to the code.”

This paradigm primarily addresses **Data Privacy and Sovereignty** by design. Unlike centralized training where all data is collected in one location, creating a single point of failure, FL ensures data remains distributed. Each client stores its own data locally and only shares model gradients or weight updates with the central server [35]. This architectural principle enables compliance with rigorous data localization requirements and privacy standards without exposing raw records to external entities. For instance, in a medical context, hospitals can collaborate to train a disease prediction model without ever exchanging patient records, thus maintaining institutional data sovereignty. However, privacy is not absolute—gradients can leak information about training data through inversion attacks, necessitating additional protections like differential privacy.

Additionally, FL offers significant **Communication Efficiency**. In many settings, transmitting entire datasets is prohibitive due to bandwidth, energy, or storage constraints. FL transmits only model updates, which are proportional to the model size rather than the dataset size. For a model with $d$ parameters, each communication round exchanges $O(d)$ values, a strict lower bound compared to transferring $O(n)$ data samples. Further optimizations like gradient compression and quantization can reduce communication costs by orders of magnitude, making distributed training viable even over constrained networks [29].

## 9.2 Federated Optimization Algorithms

The goal is to minimize the global objective function:

$$ \min_{w} F(w) = \sum_{k=1}^{K} p_k F_k(w) \quad \text{where} \quad F_k(w) = \frac{1}{n_k} \sum_{i \in \mathcal{D}_k} \ell(w; x_i, y_i) \qquad (169) $$

where $K$ is the number of clients, $p_k = n_k/n$ is the weight of client $k$, $F_k(w)$ is the local loss function, $\mathcal{D}_k$ is the local dataset, and $\ell$ is the per-sample loss.

### 9.2.1 Federated Averaging (FedAvg)

FedAvg is the standard algorithm for FL. It combines local SGD on clients with model averaging on the server.

### 9.2.2 Handling Statistical Heterogeneity (FedProx)

In real-world settings, data is Non-IID (Independent and Identically Distributed). For example, one user may only take photos of cats, while another only takes photos of dogs. This “client drift” or “data heterogeneity” causes local models to diverge significantly from the global optimum, as different clients optimize their local losses toward different solutions. This is a fundamental challenge that distinguishes federated learning from distributed learning on homogeneous data.
**Algorithm 6 Federated Averaging (FedAvg)**

**Server:** Initialize $w_0$
**for** round $t = 1$ to $T$ **do**
  Server selects a subset of clients $S_t \subseteq \{1, \dots, K\}$
  Server broadcasts $w_t$ to all $k \in S_t$
  **for** client $k \in S_t$ **in parallel** **do**
    $w_{t+1}^k \leftarrow$ ClientUpdate($k, w_t$)
  **end for**
  Server aggregates: $w_{t+1} \leftarrow \sum_{k \in S_t} \frac{n_k}{\sum_{j \in S_t} n_j} w_{t+1}^k$
**end for**
**Function** ClientUpdate($k, w$):
  $\mathcal{B} \leftarrow$ (split local data $\mathcal{D}_k$ into batches)
  **for** local epoch $e = 1$ to $E$ **do**
    **for** batch $b \in \mathcal{B}$ **do**
      $w \leftarrow w - \eta \nabla \ell(w; b)$
    **end for**
    **end for**
    **return** $w$

FedProx addresses this by adding a proximal regularization term to the local objective:

$$ \min_{w} F_k(w) + \frac{\mu}{2} \|w - w_t\|^2 \qquad (170) $$

where $w_t$ is the global model from the previous round, and $\mu$ is the proximal term coefficient. This term acts as a regularizer that encourages local updates to stay within a neighborhood of the global model, preventing excessive client drift. The hyperparameter $\mu > 0$ controls the strength of this constraint. When $\mu$ is large, clients are forced to make only small local updates, stabilizing convergence. When $\mu$ is small, clients have more freedom to optimize their local objectives. FedProx can be interpreted as a primal-dual method where we implicitly handle the heterogeneity through this proximal term.

### 9.2.3 Convergence Analysis

Understanding the convergence of federated algorithms is crucial for practical deployment. We analyze FedAvg under different assumptions.

**Assumption 9.1 (Smoothness).** Each local objective $F_k$ is $L$-smooth:

$$ \|\nabla F_k(w) - \nabla F_k(w')\| \le L \|w - w'\| \quad \forall w, w' \qquad (171) $$

where $L$ is the Lipschitz constant of the gradient.

**Assumption 9.2 (Bounded Variance).** The stochastic gradients have bounded variance:

$$ \mathbb{E}[\|\nabla F_k(w; \xi) - \nabla F_k(w)\|^2] \le \sigma_k^2 \qquad (172) $$

where $\xi$ represents the randomness in the mini-batch, and $\sigma_k^2$ is the variance bound.

**Assumption 9.3 (Bounded Heterogeneity).** The gradient dissimilarity across clients is bounded:

$$ \frac{1}{K} \sum_{k=1}^{K} \|\nabla F_k(w) - \nabla F(w)\|^2 \le \sigma_g^2 \qquad (173) $$

where $\sigma_g^2$ bounds the dissimilarity between local and global gradients.
**Theorem 9.1 (FedAvg Convergence).** Under Assumptions 1-3, for convex objectives, FedAvg with learning rate $\eta = O(1/\sqrt{TKE})$ achieves:

$$ \frac{1}{T} \sum_{t=1}^{T} \mathbb{E}[\|\nabla F(w_t)\|^2] \le O \left( \frac{1}{\sqrt{TKE}} + \frac{E^2 \sigma_g^2}{T} \right) \quad (174) $$

where $T$ is the total number of rounds, $K$ is the number of participating clients, and $E$ is the number of local epochs.

The second term captures the effect of client drift due to heterogeneity. It grows with $E$, creating a tension: more local computation ($E$) reduces communication but increases drift.

## 9.3 Personalized Federated Learning

When client data distributions are heterogeneous, a single global model may be suboptimal for individual clients. Personalized FL learns models tailored to each client while still leveraging collaborative learning.

### 9.3.1 Local Fine-Tuning

The simplest approach: train a global model via FedAvg, then fine-tune locally on each client's data:

$$ w_k^* = w_{global} - \eta \sum_{t=1}^{T_{local}} \nabla F_k(w_k^{(t)}) \quad (175) $$

where $w_{global}$ is the trained global model, $\eta$ is the learning rate, and $T_{local}$ is the number of fine-tuning steps.

### 9.3.2 Personalized Layers

Decompose the model into shared base layers $\phi$ and personal head layers $\psi_k$:

$$ f_k(x) = \psi_k(\phi(x)) \quad (176) $$

where $\phi$ is the shared feature extractor and $\psi_k$ is the client-specific head. Only $\phi$ is federated; each $\psi_k$ remains local. This is effective when feature extraction generalizes but final predictions are client-specific.

### 9.3.3 MAML-based Personalization

Per-FedAvg uses Model-Agnostic Meta-Learning (MAML) to find a global model that adapts quickly to each client. Rigorously, for each client $k$, we split local data into support $D_k^{sup}$ and query $D_k^{qry}$ sets:

$$ \min_{w} \sum_{k=1}^{K} \mathcal{L}(w - \alpha \nabla \mathcal{L}(w; D_k^{sup})); D_k^{qry} \quad (177) $$

where $\alpha$ is the inner loop learning rate. The global model is optimized so that one gradient step on the support set yields good performance on the query set. This creates models that personalize efficiently.
### 9.3.4 Mixture of Experts

Train multiple global models (experts) and learn a client-specific mixture:

$$f_k(x) = \sum_{j=1}^{M} \pi_{kj} f_j(x) \qquad (178)$$

where $f_j$ are the expert models and $\pi_{kj}$ are the mixing coefficients for client $k$.

## 9.4 Communication Efficiency

Communication is often the bottleneck in FL. Several techniques reduce communication costs.

### 9.4.1 Gradient Compression

**Quantization:** Reduce gradient precision from 32-bit floats to lower bit representations.

$$Q(g) = \|g\|_2 \cdot \operatorname{sign}(g) \cdot \xi \qquad (179)$$

where $g$ is the gradient vector, and $\xi$ is a random binary vector with $\xi_i \sim \text{Bernoulli}(|g_i|/\|g\|_\infty)$. This stochastic quantization is unbiased: $\mathbb{E}[Q(g)] = g$.

**Sparsification:** Only communicate top-$k$ gradient components:

$$\text{Top}_k(g) = g \odot \mathbb{I}(|g| \ge |g|_{(k)}) \qquad (180)$$

where $\odot$ denotes element-wise multiplication, and $|g|_{(k)}$ is the $k$-th largest magnitude element. Combined with error feedback (accumulating dropped components), this preserves convergence.

**Low-Rank Approximation:** Approximate gradient matrices with low-rank decompositions:

$$G \approx UV^T \qquad (181)$$

where $G$ is the gradient matrix, $U \in \mathbb{R}^{m \times r}$, $V \in \mathbb{R}^{n \times r}$, and $r$ is the rank of the approximation. For rank $r \ll \min(m, n)$, this reduces communication from $O(mn)$ to $O((m + n)r)$.

## 9.5 Privacy and Security in FL

While FL offers better privacy than centralized training, it is not perfectly secure.

### 9.5.1 Gradient Inversion Attacks

Gradients contain information about the training data. In “Deep Leakage from Gradients” (DLG), an attacker (the server) tries to reconstruct the private input $x$ and label $y$ by optimizing dummy data $x'$, $y'$ to match the received gradient $\nabla w$:

$$x^*, y^* = \arg \min_{x', y'} \| \nabla W(x', y') - \nabla W_{\text{real}} \|^2 \qquad (182)$$

where $\nabla W_{\text{real}}$ is the observed gradient and $(x', y')$ are the dummy input and label. This optimization can surprisingly recover pixel-perfect images from gradients in deep networks.
### 9.5.2 Secure Aggregation

To prevent the server from inspecting individual updates, Secure Aggregation (SecAgg) uses Multi-Party Computation (MPC). Clients add random masks to their updates such that the masks cancel out when summed:

$$ \sum_k (w^k + r_k) = \sum w^k + \sum r_k = \sum w^k \quad (\text{if } \sum r_k = 0) \qquad (183) $$

where $w^k$ is the update from client $k$, and $r_k$ are random masks designed to sum to zero. Common protocols use pairwise masking based on Diffie-Hellman key exchange.

## 9.6 Robustness to Byzantine Attacks

Malicious clients may send corrupted updates to poison the global model (e.g., to induce a backdoor). Standard averaging is sensitive to outliers. Robust aggregation rules replace the mean with robust statistics:

* **Krum:** Selects the update that is closest to its $n - f - 2$ neighbors.

* **Coordinate-wise Median:** Takes the median of each coordinate of the gradient vector.

* **Trimmed Mean:** Discards the largest and smallest values for each coordinate before averaging.

## 9.7 Exercises

### 1. FedAvg and Non-IID Data:

(a) Simulate a FL setting with 10 clients using the MNIST dataset.

(b) Create a pathological Non-IID split where each client has data from only 2 digits.

(c) Compare the test accuracy of FedAvg with $E = 1$ vs. $E = 5$ local epochs. Explain the trade-off between communication efficiency and convergence stability.

### 2. Gradient Inversion:

(a) Implement the DLG attack ([38]) in PyTorch.

(b) Attempt to recover an image from a ResNet-18 gradient.

(c) Investigate how the attack success depends on the batch size and the model depth.

### 3. Backdoor Attacks:

(a) Implement a “pixel pattern” backdoor attack where a client inserts a trigger into their training images and flips the label.

(b) Measure the “Attack Success Rate” (ASR) on the global model.

(c) Test if Coordinate-wise Median aggregation defends against this attack.

### 4. FedProx Implementation:

(a) Implement FedProx with proximal term $\frac{\mu}{2}\|w - w_t\|^2$ in PyTorch.

(b) Compare convergence with FedAvg on highly non-IID data (Dirichlet($\alpha = 0.1$) partition).
(c) Study the effect of the proximal parameter $\mu$ on convergence speed and final accuracy.

(d) Analyze client drift by measuring the distance between local and global models during training.

## 5. Differential Privacy in FL:

(a) Implement DP-FedAvg by adding Gaussian noise to clipped model updates.

(b) Compute the privacy budget $(\epsilon, \delta)$ using the moments accountant.

(c) Plot the privacy-accuracy trade-off for different noise scales $\sigma$.

(d) Compare user-level and sample-level DP guarantees.

## 6. Secure Aggregation:

(a) Implement a simplified secure aggregation protocol using Shamir's secret sharing.

(b) Demonstrate that the server cannot see individual updates but can compute the aggregate.

(c) Analyze the communication overhead compared to plain FedAvg.

(d) Test robustness to client dropout during the aggregation protocol.

## 7. Personalized Federated Learning:

(a) Implement FedPer: train shared lower layers globally, personalized upper layers locally.

(b) Compare with full fine-tuning and MAML-based personalization.

(c) Evaluate on CIFAR-10 with heterogeneous label distributions across clients.

(d) Measure both global test accuracy and per-client personalized accuracy.

## 8. Byzantine-Robust Aggregation:

(a) Implement Byzantine attacks: random updates, label flipping, model replacement.

(b) Compare robustness of FedAvg, Krum, Coordinate-wise Median, and Trimmed Mean.

(c) Determine the maximum fraction of Byzantine clients each aggregation can tolerate.

(d) Implement FLAME (filtering via model similarity) and evaluate against adaptive attacks.
# 10 Safe Reinforcement Learning

## 10.1 The Alignment Problem in RL

Reinforcement Learning (RL) agents are optimization machines. They will exploit any loophole in the reward function to maximize their score, often leading to unintended and potentially harmful behavior. This phenomenon is known as “Reward Hacking” or “Specification Gaming” [4].

**Example 10.1** (The Coast Runners Effect). In a boat racing game, an agent trained to maximize points found that it could achieve a higher score by spinning in circles and collecting respawning power-ups indefinitely, rather than finishing the race. This satisfied the literal reward function but violated the designer's intent.

Other alignment issues include:

* **Negative Side Effects:** An agent cleaning a room might break a vase because the reward function didn't explicitly penalize breaking things.

* **Reward Tampering:** The agent might modify its own code or the environment to artificially inflate the reward signal.

## 10.2 Constrained Markov Decision Processes (CMDP)

To enforce safety constraints (e.g., “do not crash”), we extend the standard MDP framework to Constrained MDPs. A CMDP is a tuple $\langle S, A, P, R, C, \gamma, d \rangle$, where:

* $C(s, a)$ is a cost function (e.g., $C(s, a) = 1$ if the action is unsafe, 0 otherwise).

* $d$ is a safety threshold (e.g., expected cost must be $\le 0.1$).

The optimization problem becomes:

$$ \max_{\pi} J_R(\pi) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \right] \quad \text{s.t.} \quad J_C(\pi) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t C(s_t, a_t) \right] \le d \quad (184) $$

where $J_R$ is the expected return, $J_C$ is the expected cost, $\gamma$ is the discount factor, and $d$ is the safety threshold.

### 10.2.1 Lagrangian Relaxation

We can solve this using the method of Lagrange multipliers. We define the Lagrangian:

$$ L(\pi, \lambda) = J_R(\pi) - \lambda(J_C(\pi) - d) \quad (185) $$

where $\lambda \ge 0$ is the Lagrange multiplier. The problem becomes a min-max game: $\min_{\lambda} \max_{\pi} L(\pi, \lambda)$. We can update $\pi$ using policy gradients and $\lambda$ using gradient descent (dual ascent).
### 10.2.2 Constrained Policy Optimization (CPO)

CPO [1] is a trust-region method (like TRPO) that explicitly enforces constraints at every update step. It solves a quadratic programming problem to find the best policy update that stays within the trust region and satisfies the safety constraints.

The CPO update is derived as follows. Let $\pi_k$ be the current policy. TRPO maximizes the surrogate objective:

$$L_{\pi_k}(\pi) = \mathbb{E}_{s \sim d^{\pi_k}, a \sim \pi} \left[ \frac{\pi(a|s)}{\pi_k(a|s)} A^{\pi_k}(s, a) \right] \quad (186)$$

where $\pi_k$ is the current policy, $d^{\pi_k}$ is the state visitation distribution, and $A^{\pi_k}$ is the advantage function, subject to a KL constraint: $\bar{D}_{KL}(\pi_k \| \pi) \le \delta$.

CPO adds the safety constraint in linearized form:

$$\max_{\theta} g^T(\theta - \theta_k) \quad (187)$$

$$\text{s.t.} \quad \frac{1}{2}(\theta - \theta_k)^T H (\theta - \theta_k) \le \delta \quad (188)$$

$$c + b^T(\theta - \theta_k) \le 0 \quad (189)$$

where $g$ is the gradient of the objective, $H$ is the Fisher information matrix, $c$ is the constraint violation, $b$ is the gradient of the constraint, and $\delta$ is the trust region size.

*Solution via KKT Conditions.* The Lagrangian for the CPO problem is:

$$\mathcal{L}(\theta, \lambda, \nu) = g^T(\theta - \theta_k) - \frac{\lambda}{2}(\theta - \theta_k)^T H(\theta - \theta_k) - \nu(c + b^T(\theta - \theta_k)) \quad (190)$$

where $\lambda$ and $\nu$ are the dual variables for the trust region and safety constraints, respectively. Taking the derivative with respect to $\theta$ and setting to zero:

$$g - \lambda H(\theta - \theta_k) - \nu b = 0 \implies \theta - \theta_k = \frac{1}{\lambda} H^{-1}(g - \nu b) \quad (191)$$

where the update direction is a linear combination of the objective gradient and constraint gradient, scaled by the inverse Fisher matrix. The KKT complementary slackness conditions are: (1) $\lambda \ge 0$, $\nu \ge 0$; (2) if the trust region constraint is active, $\lambda > 0$; (3) if the safety constraint is active, $\nu > 0$ and $c + b^T(\theta - \theta_k) = 0$. The optimal $\lambda, \nu$ are found by solving the dual problem or using a line search that ensures both constraints are satisfied. When the safety constraint is violated ($c > 0$), the update is primarily driven by the constraint gradient $b$ (recovery step). When safe ($c \le 0$), the update can optimize the reward while staying within the safe region. $\square$

The solution involves projecting onto the feasible region using the KKT conditions.

## 10.3 Safe Exploration

In standard RL, agents explore by taking random actions. In safety-critical domains (e.g., autonomous driving), random exploration is unacceptable.

### 10.3.1 Safety Layers via Control Barrier Functions

A Control Barrier Function (CBF) $h: S \to \mathbb{R}$ defines the safe set $C = \{s: h(s) \ge 0\}$.
**Definition 10.1** (Control Barrier Function). For a dynamical system $\dot{s} = f(s)+g(s)a$, a function $h$ is a CBF if there exists $\alpha > 0$ such that:

$$ \sup_a \left[ \frac{\partial h}{\partial s}(f(s) + g(s)a) \right] \geq -\alpha h(s) \quad \forall s \in \mathcal{C} \qquad (192) $$

where $h(s)$ is the barrier function, $\alpha$ is a class $\mathcal{K}$ function parameter, and the condition ensures the system can remain in the safe set $\mathcal{C}$.

*Forward Invariance.* The CBF condition ensures that the safe set $\mathcal{C} = \{s: h(s) \geq 0\}$ is forward invariant. If we choose an action satisfying the CBF constraint, then:

$$ \dot{h}(s) = \frac{\partial h}{\partial s}(f(s) + g(s)a) \geq -\alpha h(s) \qquad (193) $$

where $\dot{h}(s)$ is the time derivative of the barrier function along the system trajectory. This is a differential inequality. For any $s_0 \in \mathcal{C}$ (i.e., $h(s_0) \geq 0$), the solution satisfies:

$$ h(s(t)) \geq h(s_0)e^{-\alpha t} \geq 0 \quad \forall t \geq 0 \qquad (194) $$

where $s_0$ is the initial state and the inequality guarantees forward invariance of the safe set. Thus, starting from the safe set, the system remains in the safe set for all time. The exponential term $e^{-\alpha t}$ allows $h$ to decay, but it can never become negative as long as we enforce the CBF constraint at each step. $\square$

The safety layer solves a QP at each timestep:

$$ a^* = \arg \min_a \|a - a_{NN}\|^2 \qquad (195) $$

$$ \text{s.t.} \quad \frac{\partial h}{\partial s}(f(s) + g(s)a) \geq -\alpha h(s) \qquad (196) $$

where $a_{NN}$ is the nominal action and the constraint enforces the CBF condition.

### 10.3.2 Lyapunov-Based Safe Learning

A Lyapunov function $V: S \to \mathbb{R}_{\geq 0}$ certifies stability if $V(s) = 0$ only at the equilibrium and $\dot{V}(s) < 0$ elsewhere.

**Theorem 10.1** (Lyapunov Stability). If there exists a continuously differentiable function $V$ such that:

1. $V(s^*) = 0$ at the equilibrium $s^*$

2. $V(s) > 0$ for all $s \neq s^*$

3. $\dot{V}(s) = \nabla V(s)^T (f(s) + g(s)\pi(s)) < 0$ for all $s \neq s^*$

then the system is asymptotically stable under policy $\pi$.

Safe Lyapunov Learning jointly learns a policy $\pi$ and Lyapunov function $V$ such that the Lyapunov conditions are satisfied, ensuring stability throughout training.
### 10.3.3 Shielding

A shield is a verified backup policy that intervenes when the primary policy would violate safety constraints.

**Definition 10.2 (Shield).** Given a primary policy $\pi$ and a set of unsafe states $\mathcal{U}$, a shield $\sigma$ modifies actions:

$$ \sigma(\pi)(s) = \begin{cases} \pi(s) & \text{if safe}(s, \pi(s)) \\ \pi_{backup}(s) & \text{otherwise} \end{cases} \qquad (197) $$

where $\pi_{backup}$ is a verified safe policy and $\text{safe}(s, a)$ is a safety check.

## 10.4 Value Alignment and Inverse RL

Instead of manually specifying a potentially flawed reward function, we can try to learn the reward function from human behavior.

### 10.4.1 Inverse Reinforcement Learning (IRL)

Given a set of expert demonstrations $\mathcal{D} = \{(s_i, a_i)\}$, IRL aims to find a reward function $R$ under which the expert's behavior is optimal.

**Maximum Entropy IRL** assumes the expert acts according to:

$$ P(\tau) \propto \exp \left( \sum_t R(s_t, a_t) \right) \qquad (198) $$

where $\tau$ is a trajectory and $R$ is the reward function. The objective is to maximize the likelihood of demonstrations while preferring “simple” reward functions:

$$ \max_{R} \mathbb{E}_{\tau \sim \mathcal{D}}[\log P(\tau|R)] - \lambda \|R\| \qquad (199) $$

where $\mathcal{D}$ is the dataset of expert demonstrations and $\lambda$ is a regularization coefficient.

**Feature Matching IRL** assumes $R(s) = w^T \phi(s)$ and finds weights such that the expected feature counts match between expert and learned policy:

$$ \mathbb{E}_{\pi^*}[\phi(s)] = \mathbb{E}_{\pi_w}[\phi(s)] \qquad (200) $$

where $\phi(s)$ are the state features, $\pi^*$ is the expert policy, and $\pi_w$ is the learned policy.

### 10.4.2 Preference Learning

Rather than demonstrations, we can learn from preferences over trajectory pairs.

**Definition 10.3 (Bradley-Terry Model).** Given trajectory pairs $(\tau_1, \tau_2)$ and human preference $\tau_1 \succ \tau_2$, the Bradley-Terry model assumes:

$$ P(\tau_1 \succ \tau_2) = \frac{\exp(\sum_t R(s_t^1, a_t^1))}{\exp(\sum_t R(s_t^1, a_t^1)) + \exp(\sum_t R(s_t^2, a_t^2))} \qquad (201) $$

where $\tau_1 \succ \tau_2$ denotes that trajectory $\tau_1$ is preferred over $\tau_2$.

The reward function is learned by maximizing the likelihood of observed preferences.
### 10.4.3 Reinforcement Learning from Human Feedback (RLHF)

RLHF is the technique used to align Large Language Models (like ChatGPT).

1. **Supervised Fine-Tuning (SFT):** Train a supervised policy on expert demonstrations.

2. **Reward Model Training:** Collect comparison data (human prefers response A over B) and train:

$$ \mathcal{L}_{RM} = -\mathbb{E}_{(x,y_w,y_l)\sim D}[\log \sigma(R_{\theta}(x, y_w) - R_{\theta}(x, y_l))] \quad (202) $$

where $\sigma$ is the sigmoid function, $y_w$ is the preferred response, and $y_l$ is the rejected response.

3. **Policy Optimization:** Use PPO to maximize the reward while staying close to the SFT policy:

$$ \max_{\pi} \mathbb{E}_{x\sim D, y\sim\pi}[R_{\theta}(x, y)] - \beta D_{KL}([\|\pi\|\pi_{SFT}]) \quad (203) $$

where $\pi_{SFT}$ is the supervised fine-tuned policy and $\beta$ controls the KL penalty.

### 10.4.4 Direct Preference Optimization (DPO)

DPO bypasses explicit reward modeling by directly optimizing the policy from preferences:

$$ \mathcal{L}_{DPO}(\pi_{\theta}; \pi_{ref}) = -\mathbb{E}\left[\log \sigma\left(\beta \log \frac{\pi_{\theta}(y_w|x)}{\pi_{ref}(y_w|x)} - \beta \log \frac{\pi_{\theta}(y_l|x)}{\pi_{ref}(y_l|x)}\right)\right] \quad (204) $$

where $\pi_{ref}$ is the reference policy, $\beta$ is the implicit KL coefficient, and $\sigma$ is the sigmoid function. This is mathematically equivalent to RLHF with the optimal reward function under specific assumptions, but is computationally simpler.

## 10.5 Reward Hacking and Specification Gaming

A fundamental challenge in RL is that agents optimize the specified reward, which may not capture the true objective.

**Definition 10.4 (Reward Hacking).** Reward hacking occurs when an agent achieves high reward through unintended means that do not align with the designer's goals.

Examples include a robot tasked with “move fast” that learns to be very tall and fall over, a game-playing agent that exploits bugs in the game physics, or a recommendation system that manipulates users to increase engagement metrics.

**Mitigations:** To address these issues, several strategies are employed:

* **Reward shaping:** Adds auxiliary rewards to guide learning towards desired behaviors.

**Detailed Explanation:** Reward shaping modifies the original sparse reward $R(s, a)$ by adding a potential-based shaping function $F(s, s') = \gamma\Phi(s') - \Phi(s)$, where $\Phi: S \to \mathbb{R}$ is a potential function encoding domain knowledge. This transformation preserves optimal policies (by the policy invariance theorem) while providing denser learning signals. The key insight is that $F$ encodes an admissible heuristic that guides the agent toward rewarding states without changing which policies are optimal. Careful design of $\Phi$ can dramatically accelerate learning in sparse-reward environments.

**Concrete Example:** In robotic navigation to a goal location $s_g$, the sparse reward $R(s, a) = \mathbb{1}[s = s_g]$ provides no guidance. Define $\Phi(s) = -\|s - s_g\|$ (negative distance to goal).
Then $F(s, s') = -\gamma \|s' - s_g\| + \|s - s_g\|$ rewards moving closer to the goal at each step. For a grid world with goal at (5, 5), moving from (3, 3) to (4, 4) receives shaped reward $F = -0.9 \cdot \sqrt{2} + 2\sqrt{2} \approx 1.55$, accelerating learning while preserving the optimal path.

* **Constrained RL:** Explicitly constrains undesirable behaviors using cost functions.

**Detailed Explanation:** Constrained RL formulates safety as constraint satisfaction in the CMDP framework: maximize $E[\sum_t \gamma^t r_t]$ subject to $E[\sum_t \gamma^t c_i(s_t, a_t)] \le d_i$ for cost functions $c_1, \dots, c_k$. This separates the objective (reward maximization) from safety requirements (constraint satisfaction), making specifications clearer. The Lagrangian relaxation approach introduces dual variables $\lambda_i$ and optimizes $E[\sum_t \gamma^t (r_t - \sum_i \lambda_i c_i(s_t, a_t))]$, adaptively adjusting $\lambda_i$ to meet constraints. Unlike reward shaping, this guarantees constraint satisfaction rather than merely encouraging it.

**Concrete Example:** In autonomous driving, the reward function optimizes travel time: $r_t = v_t$ (velocity). Safety constraints prevent collisions: $c_1(s, a) = \mathbb{1}[\text{distance to obstacle} < 2m]$ with threshold $d_1 = 0.05$ (allowing 5% near-miss rate during training). Another constraint limits acceleration for passenger comfort: $c_2(s, a) = |a_t - a_{t-1}|$ with $d_2 = 0.3$. CPO algorithms solve this constrained optimization, ensuring the learned policy is both fast and safe, even when high speeds conflict with safety.

* **Iterated amplification:** Recursively decomposes complex tasks to reduce specification error.

**Detailed Explanation:** Iterated amplification addresses reward specification in complex domains where direct reward engineering is infeasible. The key idea: train an agent $A_1$ on a simplified task with a trusted reward, then use human+$A_1$ (human assisted by $A_1$'s suggestions) to provide supervision for more complex subtasks, training $A_2$. Recursively, $A_n$ is trained using human+$A_{n-1}$ oversight. This “bootstraps” capability while maintaining alignment, as each step is overseen by the amplified human-agent system. The process converges when $A_n$ matches the capability of human+$A_{n-1}$, ideally preserving alignment throughout.

**Concrete Example:** For training a code review AI: $A_1$ learns to check syntax errors (easy for humans to verify). Human+$A_1$ (human using syntax checker) reviews more complex code for logic bugs, training $A_2$. Human+$A_2$ (human using syntax and logic checkers) reviews architectural issues, training $A_3$. After several iterations, $A_n$ performs comprehensive code review. At each stage, the human provides meaningful oversight because $A_{n-1}$ handles routine checks, allowing focus on higher-level issues. This decomposes the intractable task “review code perfectly” into manageable supervised learning problems.

* **AI safety via debate:** Uses adversarial processes where agents argue for different actions to help a human judge identify reward hacking.

**Detailed Explanation:** In debate-based AI safety, two agents with opposing incentives present arguments for different answers to a question or different actions in a situation. A human judge evaluates the debate and selects the more convincing argument. The key insight: even if individual arguments are too complex for the human to verify directly, adversarial debate incentivizes each agent to find flaws in the opponent's reasoning. This works when “verification is easier than generation”—it's hard to construct a correct proof, but errors can be efficiently identified by an adversary. Training via debate makes agents optimize for defensible, robust decisions rather than exploiting judge biases.

**Concrete Example:** To decide whether to approve a loan application, Agent A argues “Approve: applicant has stable income history” while Agent B argues “Reject: applicant has high debt-to-income ratio masked by recent debt consolidation.” In cross-examination, Agent B reveals that Agent A cherry-picked income data from a temporary bonus period.