Skip to content

robust

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

\[ 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
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.