A Law of Robustness for Weight-bounded Neural Networks

Understand

Robustness of deep neural networks against adversarial perturbations is a pressing concern motivated by recent findings showing the pervasive nature of such vulnerabilities.

• One method of characterizing the robustness of a neural network model is through its Lipschitz constant, which forms a robustness certificate.
• A natural question to ask is, for a fixed model class (such as neural networks) and a dataset of size $n$, what is the smallest achievable Lipschitz constant among all models that fit the dataset? Recently, (Bubeck et al., 2020) conjectured that when using two-layer networks with $k$ neurons to fit a generic dataset, the smallest Lipschitz constant is $\Omega(\sqrt{\frac{n}{k}})$.
• This implies that one would require one neuron per data point to robustly fit the data.