Shrink & Cert

Certified robustness as bi-level optimization — deterministic certificates at first-order cost.

Certified Training as Bi-level Optimization

Most certified-training methods trade away a large amount of clean accuracy, or a large amount of compute, for a guarantee. Shrink & Cert reformulates the problem as bi-level optimization: the inner problem shrinks the per-layer Lipschitz bounds of the network, the outer problem minimizes the task loss on the shrunk network. The two objectives are optimized jointly rather than as a penalty bolted onto standard training.

Because the Lipschitz reduction is expressed as a proximal step, the whole procedure stays at first-order cost — the same order of compute as ordinary SGD training, with no inner adversarial loop and no randomized-smoothing sampling at inference.

What It Gives You

  • Deterministic certificates under both l2 and l-infinity perturbation. The certified radius is a bound, not an empirical estimate and not a probabilistic guarantee.
  • Results on CIFAR-10 and ImageNet.
  • Certification at inference costs a forward pass; there is nothing to sample.

CertViT applies the same per-layer Lipschitz machinery to models that are already trained, and reports where that stops working: certified accuracy is non-vacuous only for the tiny variants.

Equal contribution with Kavya Gupta. Published at the AdvML Frontiers Workshop, ICML 2023.