Effective Certification of Monotone Deep Equilibrium Models
  Monotone Operator Equilibrium Models (monDEQs) represent a class of models
combining the powerful deep equilibrium paradigm with convergence guarantees.
Further, their inherent robustness to adversarial perturbations makes
investigating their certifiability a promising research direction.
Unfortunately, existing approaches are either imprecise or severely limited in
scalability. In this work, we propose the first scalable and precise monDEQ
verifier, based on two key ideas: (i) a novel convex relaxation enabling
efficient inclusion checks, and (ii) non-trivial mathematical insights
characterizing the fixpoint operations at the heart of monDEQs on sets rather
than concrete inputs. An extensive evaluation of our verifier on the
challenging $\ell_\infty$ perturbations demonstrates that it exceeds
state-of-the-art performance in terms of speed (two orders of magnitude) and
scalability (an order of magnitude) while yielding 25% higher certified
accuracies on the same networks.
