A law of robustness for two-layers neural networks

Abstract

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\le 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.

18 pages, 3 figures. V2: improved Theorem 4 (weaker version of the Conjecture with $n$ replaced by $d$) from ReLU with no bias term in V1, to arbitrary non-linearities (even data-dependent) in V2

References in corpus (1)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

Cited by in corpus (7)

• Large-time asymptotics in deep learning
• Dense Hopfield Networks in the Teacher-Student Setting
• Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization
• A Law of Robustness for Weight-bounded Neural Networks
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes
• Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective