Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspective

Designing neural networks with bounded Lipschitz constant is a promising way to obtain certifiably robust classifiers against adversarial examples. However, the relevant progress for the important \ell_\infty perturbation setting is rather limited, and a principled understanding of how to design expressive \ell_\infty Lipschitz networks is still lacking. In this paper, we bridge the gap by studying certified \ell_\infty robustness from a novel perspective of representing Boolean functions. We derive two fundamental impossibility results that hold for any standard Lipschitz network: one for robust classification on finite datasets, and the other for Lipschitz function approximation. These results identify that networks built upon norm-bounded affine layers and Lipschitz activations intrinsically lose expressive power even in the two-dimensional case, and shed light on how recently proposed Lipschitz networks (e.g., GroupSort and \ell_\infty -distance nets) bypass these impossibilities by leveraging order statistic functions.