Certifying ResNet robustness with the Lipschitz constant: where the state of the art stands

These are working notes surveying how the Lipschitz constant is used to certify the robustness of image classifiers, with an eye on residual networks. Corrections are welcome.

From a Lipschitz bound to a certified radius

Let $f\colon \mathbb{R}^d \to \mathbb{R}^K$ be a classifier that assigns logits to the $K$ classes, and predict $\hat{y}(x) = \arg\max_i f_i(x)$. An adversarial example is a point $x'$ close to $x$ with $\hat{y}(x') \neq \hat{y}(x)$. We would like a certificate: a radius $r$ such that no perturbation of $\ell_2$-norm below $r$ can change the prediction.

The Lipschitz constant delivers exactly this. Suppose $f$ is $L$-Lipschitz in the $\ell_2$ norm, i.e.

Write the margin at $x$ as $m(x) = f_i(x) - \max_{j \neq i} f_j(x)$ for the predicted class $i$. Each pairwise difference $f_i - f_j$ is $\sqrt{2}\,L$- Lipschitz, so the decision cannot flip until some competitor catches up:

So a tight value of $L$ and a large margin together buy a large certified radius. Everything below is about getting $L$ — or a usable surrogate for it — without making the bound so loose that the certificate is worthless.

Why the naive bound collapses, especially for ResNets

For a feed-forward network with $1$-Lipschitz activations, the chain rule gives the classic product bound

the product of the layers’ spectral norms. It is trivial to compute (a few steps of power iteration per layer) but can be loose by many orders of magnitude, because it assumes every layer stretches in the same direction at once. The global constant it targets is also pessimistic: the local Lipschitz constant near a given input is usually far smaller.

Residual connections make this worse. A residual block computes

and stacking $B$ such blocks multiplies these factors. The $1 + \operatorname{Lip}(g)$ terms compound, so for a deep ResNet the product bound explodes. Hu, Leino, Wang and Fredrikson made exactly this point in Unlocking Deterministic Robustness Certification on ImageNet (NeurIPS 2023): fast ways of bounding the Lipschitz constant of a conventional ResNet are so loose that certified training barely works — which motivated their LiResNet, a residual design whose branch is linear enough to admit a tight bound.

Computing $L$ exactly is not a way out: Virmaux and Scaman (NeurIPS 2018) showed the exact Lipschitz constant of a ReLU network is NP-hard to compute, and introduced AutoLip/SeqLip as tractable estimates.

Estimating the constant more tightly

Between the trivial product bound and the intractable exact value sits a spectrum of tighter estimators:

• LipSDP (Fazlyab, Robey, Hassani, Morari, Pappas, NeurIPS 2019) treats the activations as slope-restricted nonlinearities and encodes them with incremental quadratic constraints, producing a genuine upper bound via a semidefinite program. It is much tighter than SeqLip, but the SDP scales poorly in width and does not directly cover large convolutional ResNets.
• Gram iteration (Delattre et al., 2023) gives fast, accurate bounds on the spectral norm of convolutional layers specifically — a practical ingredient for the product-style bounds above.
• Local bounds trade the global constant for the Lipschitz constant on a neighbourhood of $x$, which is what the certificate actually needs and is often dramatically smaller.
• CLEVER (Weng et al., 2018) estimates a local constant via extreme-value theory. Useful as a diagnostic, but it is an estimate, not an upper bound — it does not certify.

The pragmatic state of the art: build the network 1-Lipschitz

The most successful deterministic approach today sidesteps estimation altogether: constrain the network so that $L = 1$ by construction, then read the certified radius straight off the margin as $m(x)/\sqrt{2}$. If every linear map is norm-preserving (orthogonal) and every activation is $1$-Lipschitz (e.g. GroupSort/MaxMin), the whole network is exactly $1$-Lipschitz.

The line of work here is now fairly mature:

• Orthogonal convolutions — Skew Orthogonal Convolutions (SOC; Singla & Feizi, ICML 2021) and Cayley-parameterized convolutions make convolutional layers exactly orthogonal.
• Almost-Orthogonal Layers (AOL; Prach & Lampert, ECCV 2022) relax orthogonality to a cheap rescaling that still guarantees $1$-Lipschitzness.
• SDP-based Lipschitz Layers (SLL; Araujo, Havens, Delattre, Allauzen, Hu, ICLR 2023) unify AOL-style constraints with an SDP view, giving expressive $1$-Lipschitz residual blocks.
• Sandwich layers (Wang & Manchester, ICML 2023) give a direct parameterization of Lipschitz-bounded networks — no projection step needed.
• GloRo Nets (Leino, Wang, Fredrikson, ICML 2021) fold the global-Lipschitz certificate into training by adding a “bottom” logit for the non-robust case.
• LiResNet (Hu et al., 2023) scales this to deep residual networks and, for the first time, to non-trivial deterministic certificates on ImageNet.

Prach et al. benchmarked these fairly in 1-Lipschitz Layers Compared: Memory, Speed, and Certifiable Robustness (CVPR 2024); the frontier keeps moving, with 2025 work such as Block Reflector Orthogonal layers pushing certified accuracy further. Here the “Lipschitz estimation” problem disappears — the modelling cost is paid up front in the architecture, and the trade-off is some clean accuracy.

A minimal illustration of the ingredient the product bound rests on — a layer’s spectral norm by power iteration:

import torch

def spectral_norm(weight: torch.Tensor, iters: int = 20) -> float:
    """Largest singular value of a (flattened) weight matrix — one layer's
    contribution to the global Lipschitz product bound."""
    W = weight.reshape(weight.shape[0], -1)
    v = torch.randn(W.shape[1])
    for _ in range(iters):
        u = W @ v
        u = u / u.norm()
        v = W.T @ u
        v = v / v.norm()
    return (u @ (W @ v)).item()   # ≈ ‖W‖₂

The other road: randomized smoothing

For very large ResNets — ImageNet-scale — the dominant scalable certificate is randomized smoothing (Cohen, Rosenfeld, Kolter, ICML 2019). Instead of bounding $L$ for the base network, one certifies a smoothed classifier

The class-probability map of $\hat{g}$ is Lipschitz after a Gaussian transformation, which yields a certified $\ell_2$ radius

with $\underline{p_A}, \overline{p_B}$ estimated by sampling. The certificate is probabilistic (it holds with high confidence) and the sampling is expensive, but it is architecture-agnostic and scales where SDPs and orthogonal constraints do not. Recent variants such as SPLITZ (2024) combine a Lipschitz bound on part of the network with smoothing on the rest to tighten the radius.

Verifiers, and where things stand

A third, complementary strand does not change the network at all: bound- propagation verifiers such as auto_LiRPA and $\alpha,\beta$-CROWN propagate linear relaxations through the layers to certify (or falsify) robustness of a fixed trained model. These win the VNN-COMP benchmarks and give tight local certificates, at higher per-input cost than reading off a global $L$.

Put together, the landscape is:

The open problem that ties them together is the gap between clean and certified accuracy: on CIFAR-10 the best deterministic certificates are now strong, but on ImageNet certified accuracy still trails clean accuracy by a wide margin. For residual networks specifically, the tension is between the expressive power that residual connections provide and the loose global Lipschitz bounds they induce — which is exactly the corner of the problem I find most interesting.

References (starting points)

• Szegedy et al., Intriguing properties of neural networks, 2013.
• Virmaux & Scaman, Lipschitz regularity of deep neural networks, NeurIPS 2018.
• Weng et al., Evaluating the robustness of neural networks (CLEVER), 2018.
• Fazlyab et al., Efficient and accurate estimation of Lipschitz constants (LipSDP), NeurIPS 2019.
• Cohen, Rosenfeld & Kolter, Certified adversarial robustness via randomized smoothing, ICML 2019.
• Leino, Wang & Fredrikson, Globally-robust neural networks (GloRo), ICML 2021.
• Singla & Feizi, Skew orthogonal convolutions (SOC), ICML 2021.
• Prach & Lampert, Almost-orthogonal layers (AOL), ECCV 2022.
• Araujo et al., A unified algebraic perspective on Lipschitz neural networks (SLL), ICLR 2023.
• Wang & Manchester, Direct parameterization of Lipschitz-bounded networks (Sandwich), ICML 2023.
• Hu et al., Unlocking deterministic robustness certification on ImageNet (LiResNet), NeurIPS 2023.
• Prach et al., 1-Lipschitz layers compared, CVPR 2024.

← Back to notes