A law of robustness for two-layers neural networks
This addresses a foundational problem in machine learning by establishing theoretical limits on robustness for neural networks, which is incremental as it builds on existing robustness studies.
The paper investigates the trade-off between neural network size and robustness, proposing a conjecture that for two-layer networks, perfect data fitting requires the Lipschitz constant to scale with the square root of the number of datapoints divided by neurons, implying overparametrization is needed for robustness. They provide partial proofs and experimental evidence supporting this claim.
We initiate the study of the inherent tradeoffs between the size of a neural network and its robustness, as measured by its Lipschitz constant. We make a precise conjecture that, for any Lipschitz activation function and for most datasets, any two-layers neural network with $k$ neurons that perfectly fit the data must have its Lipschitz constant larger (up to a constant) than $\sqrt{n/k}$ where $n$ is the number of datapoints. In particular, this conjecture implies that overparametrization is necessary for robustness, since it means that one needs roughly one neuron per datapoint to ensure a $O(1)$-Lipschitz network, while mere data fitting of $d$-dimensional data requires only one neuron per $d$ datapoints. We prove a weaker version of this conjecture when the Lipschitz constant is replaced by an upper bound on it based on the spectral norm of the weight matrix. We also prove the conjecture in the high-dimensional regime $n \approx d$ (which we also refer to as the undercomplete case, since only $k \leq d$ is relevant here). Finally we prove the conjecture for polynomial activation functions of degree $p$ when $n \approx d^p$. We complement these findings with experimental evidence supporting the conjecture.