## `eigenkit.orthogonal.torch.robust`

Certified robustness for networks with a known Lipschitz constant.

If a network `$f = h \circ g$` has a feature map `$g$` that is `$L$`-Lipschitz in the L2 norm, and its head `$h$` is linear with rows `$w_k$`, then the logit gap `$z_p - z_j$` between the predicted class `$p$` and any other class `$j$` changes by at most `$L \, \lVert w_p - w_j \rVert \, \lVert \delta \rVert$` under an input perturbation `$\delta$`. So no perturbation of norm below

```math
r = \min_{j \ne p} \frac{z_p - z_j}{L \, \lVert w_p - w_j \rVert}
```

can change the prediction: `$r$` is a certified radius. The tools here compute it, train towards it (`cert_ce`), and build the pieces that keep `$L$` known: `LLNHead` (unit-norm rows), `MaxMin` (a 1-Lipschitz activation that keeps the norm) and `lipschitz_bound` (an upper bound on `$L$` for a chain of layers). An orthogonal adapter keeps every singular value of the weight it rotates, so it leaves `lipschitz_bound` unchanged.

Numerical contracts. Each function documents the exact torch operations it runs, and the tests pin them bit for bit.

Example

```python
import torch

from eigenkit.orthogonal.torch import LLNHead, certified_accuracy, certified_radius

head = LLNHead(16, 3)
logits = head(torch.randn(8, 16))
cert = certified_radius(logits, head.get_weight(), L=1.0)
labels = torch.randint(0, 3, (8,))
certified_accuracy(cert.pred == labels, cert.radius, eps=0.1)
```

### `Certificate`

Bases: `NamedTuple`

The prediction, the top-1 margin and the certified radius of every row.

Attributes:

| Name     | Type     | Description                                                                            |
| -------- | -------- | -------------------------------------------------------------------------------------- |
| `pred`   | `Tensor` | The predicted class of each row, long.                                                 |
| `margin` | `Tensor` | The gap between the two largest logits, float64.                                       |
| `radius` | `Tensor` | The certified L2 radius, float64; inf when no other class can overtake the prediction. |

### `LLNHead`

Bases: `Module`

A linear head with unit-norm rows (last-layer normalisation).

The rows `$w_k$` of the weight are normalised at every call, so the certificate can use the distances `$\lVert w_p - w_j \rVert$` directly. The bias cancels in every logit difference, so the certificate does not see it.

Numerical contract: `F.linear(h, F.normalize(self.linear.weight, dim=1), self.linear.bias)`. The parameters are `linear.weight` and `linear.bias`.

Parameters:

| Name           | Type  | Description                   | Default    |
| -------------- | ----- | ----------------------------- | ---------- |
| `in_features`  | `int` | The number of input features. | *required* |
| `out_features` | `int` | The number of classes.        | *required* |

#### `forward(h)`

Apply the head.

Parameters:

| Name | Type     | Description                | Default    |
| ---- | -------- | -------------------------- | ---------- |
| `h`  | `Tensor` | Features (B, in_features). | *required* |

Returns:

| Type     | Description                             |
| -------- | --------------------------------------- |
| `Tensor` | torch.Tensor: Logits (B, out_features). |

#### `get_weight()`

The weight with unit-norm rows, `F.normalize(self.linear.weight, dim=1)`.

Returns:

| Type     | Description                                         |
| -------- | --------------------------------------------------- |
| `Tensor` | torch.Tensor: A (out_features, in_features) tensor. |

### `MaxMin`

Bases: `Module`

The MaxMin activation: sort the channels within disjoint pairs.

It is 1-Lipschitz and keeps the norm of its input, because it only permutes values. It is not distance-preserving: it maps `(1, 0)` and `(0, 1)` to the same point (Anil, Lucas & Grosse, ICML 2019). It acts on dim 1.

Two pairings are in use and give different functions:

- `"adjacent"` (GroupSort) pairs channels `$2k$` and `$2k + 1$` and writes the minimum first. Numerical contract: `g = x.reshape(b, c // 2, 2, *rest)`, `lo = torch.minimum(g[:, :, 0], g[:, :, 1])`, `hi = torch.maximum(...)`, then `torch.stack((lo, hi), dim=2).reshape(x.shape)`.
- `"halves"` (BRONet's MinMax) pairs channel `$k$` with `$k + C/2$` and writes the maximum of each pair in the first half. Numerical contract: `a, b = torch.split(x, c // 2, dim=1)`, `index = a > b`, then `torch.cat([torch.where(index, a, b), torch.where(index, b, a)], dim=1)`.

Parameters:

| Name      | Type      | Description                                  | Default      |
| --------- | --------- | -------------------------------------------- | ------------ |
| `pairing` | `Pairing` | "adjacent" or "halves". Default: "adjacent". | `'adjacent'` |

#### `forward(x)`

Apply the activation.

Parameters:

| Name | Type     | Description                          | Default    |
| ---- | -------- | ------------------------------------ | ---------- |
| `x`  | `Tensor` | A tensor (B, C, ...) with an even C. | *required* |

Returns:

| Type     | Description                                  |
| -------- | -------------------------------------------- |
| `Tensor` | torch.Tensor: The output, of the shape of x. |

Raises:

| Type         | Description  |
| ------------ | ------------ |
| `ValueError` | If C is odd. |

### `cert_ce(logits, y, head_weight, L, eps, tau=4.0)`

A certification-aware cross-entropy.

Every wrong logit is raised by the most a perturbation of norm `eps` could raise it against the true class, `$L \cdot \mathrm{eps} \cdot \lVert w_y - w_j \rVert$`, and the result is scored with a cross-entropy at temperature `1/tau`. Minimising it pushes the margins beyond `eps`.

Numerical contract: `d = (head_weight[y].unsqueeze(1) - head_weight.unsqueeze(0)).norm(dim=-1)`, `z = logits + L * eps * d`, then `F.cross_entropy(tau * z, y)`. The row of the true class has `d = 0`.

Parameters:

| Name          | Type     | Description                                              | Default    |
| ------------- | -------- | -------------------------------------------------------- | ---------- |
| `logits`      | `Tensor` | Logits (B, K).                                           | *required* |
| `y`           | `Tensor` | The labels (B,).                                         | *required* |
| `head_weight` | `Tensor` | The head weight (K, D), in the graph if the head trains. | *required* |
| `L`           | `float`  | The Lipschitz constant of the feature map.               | *required* |
| `eps`         | `float`  | The radius to train for.                                 | *required* |
| `tau`         | `float`  | The scale of the logits. Default: 4.0.                   | `4.0`      |

Returns:

| Type     | Description                       |
| -------- | --------------------------------- |
| `Tensor` | torch.Tensor: The loss, a scalar. |

### `certified_accuracy(correct, radius, eps)`

The fraction of rows that are correct and certified beyond `eps`.

Numerical contract: `float(correct.float().mean())` for `eps == 0`, which is the plain accuracy, and `float((correct & (radius > eps)).float().mean())` otherwise.

Parameters:

| Name      | Type     | Description                                 | Default    |
| --------- | -------- | ------------------------------------------- | ---------- |
| `correct` | `Tensor` | A boolean tensor, pred == labels.           | *required* |
| `radius`  | `Tensor` | The certified radii, from certified_radius. | *required* |
| `eps`     | `float`  | The L2 radius to certify.                   | *required* |

Returns:

| Name    | Type    | Description                    |
| ------- | ------- | ------------------------------ |
| `float` | `float` | The certified accuracy at eps. |

### `certified_radius(logits, head_weight, L)`

The certified L2 radius of every row of `logits`, for a feature map with Lipschitz constant `L` and a linear head with weight `head_weight`.

Numerical contract, in float64 on the CPU: `z = logits.double()`, `d = head_distances(head_weight)`, `pred = z.argmax(1)`, `gap = z.gather(1, pred[:, None]) - z`, `dist = d[pred]`, `r = gap / (L * dist.clamp_min(1e-300))`; then `r` is set to `inf` on the predicted class and wherever `dist == 0` (a class with the same row can never overtake the prediction), and the radius is `r.min(1).values`. The margin is the difference of the two largest logits, from `z.topk(2, dim=1)`.

Parameters:

| Name          | Type     | Description                                                     | Default    |
| ------------- | -------- | --------------------------------------------------------------- | ---------- |
| `logits`      | `Tensor` | Logits (B, K), with K >= 2.                                     | *required* |
| `head_weight` | `Tensor` | The head weight (K, D), such as LLNHead.get_weight().           | *required* |
| `L`           | `float`  | The Lipschitz constant of the feature map in front of the head. | *required* |

Returns:

| Name          | Type          | Description                                             |
| ------------- | ------------- | ------------------------------------------------------- |
| `Certificate` | `Certificate` | The prediction, the margin and the radius of every row. |

### `head_distances(head_weight)`

The distances `$\lVert w_i - w_j \rVert$` between the rows of a head weight, in float64.

Numerical contract: `w = head_weight.detach().double()`, then `torch.cdist(w, w, compute_mode="donot_use_mm_for_euclid_dist")`. The direct differences keep small distances exact; the default mode switches to a matrix product above 25 rows, which can shrink a small distance and so overstate a certified radius.

Parameters:

| Name          | Type     | Description             | Default    |
| ------------- | -------- | ----------------------- | ---------- |
| `head_weight` | `Tensor` | The head weight (K, D). | *required* |

Returns:

| Type     | Description                                   |
| -------- | --------------------------------------------- |
| `Tensor` | torch.Tensor: The (K, K) matrix of distances. |

### `lipschitz_bound(model)`

An upper bound on the L2 Lipschitz constant of a chain of layers.

The bound is the product of a bound for every layer of an `nn.Sequential` (nested ones are flattened): the largest singular value of the weight of an `nn.Linear`, an `LLNHead` (its normalised weight) or an `OrthogonalAdapter` (its rotated weight); for an `nn.Conv2d`, that of the weight read as a matrix `(out, in·kh·kw)`, times `$\sqrt{k_h k_w}$`, which bounds the convolution for any stride and dilation with `"zeros"` padding, and with `"circular"` padding no wider than `dilation * (kernel_size - 1) / 2` on each axis (wider circular padding, `"reflect"` and `"replicate"` feed a pixel to one kernel offset more than once and raise a `ValueError`); 1 for the orthogonal modules and for `MaxMin`, `ReLU`, `LeakyReLU` (slope at most 1), `Tanh`, `Sigmoid`, `Flatten` and `Identity`. The singular values are computed with `sigma_max` in float64, on the weight matrix or its transpose, whichever has fewer rows. A 1x1 convolution and a linear layer are bounded exactly.

An orthogonal adapter keeps every singular value of the weight it rotates, so adapting a chain leaves its bound unchanged.

Parameters:

| Name    | Type     | Description                          | Default    |
| ------- | -------- | ------------------------------------ | ---------- |
| `model` | `Module` | An nn.Sequential, or a single layer. | *required* |

Returns:

| Name    | Type    | Description |
| ------- | ------- | ----------- |
| `float` | `float` | The bound.  |

Raises:

| Type         | Description                                                                                                                                       |
| ------------ | ------------------------------------------------------------------------------------------------------------------------------------------------- |
| `ValueError` | If a layer is not one of the above, or a convolution pads with "reflect", "replicate", or "circular" wider than dilation * (kernel_size - 1) / 2. |

### `sigma_max(w)`

The largest singular value of a matrix, through its Gram matrix.

Exact and differentiable. Numerical contract: `torch.linalg.eigvalsh(w @ w.t()).amax().clamp_min(0).sqrt()`.

Parameters:

| Name | Type     | Description      | Default    |
| ---- | -------- | ---------------- | ---------- |
| `w`  | `Tensor` | A matrix (m, n). | *required* |

Returns:

| Type     | Description                    |
| -------- | ------------------------------ |
| `Tensor` | torch.Tensor: A scalar tensor. |
