A LAW OF ROBUSTNESS FOR TWO-LAYER NEURAL NETWORKS WITH ARBITRARY WEIGHTS

This paper addresses a fundamental question in the theory of deep learning: what is the relationship between the robustness of a neural network (measured by its Lipschitz constant) and its ability to interpolate noisy data? Specifically, it investigates whether a 'law of robustness'—which suggests that fitting noisy labels requires a high Lipschitz constant—holds for two-layer networks even when the network weights are allowed to be arbitrarily large.

Previous work established this law for networks with polynomially bounded weights. However, because unbounded weights make standard parameter-space covering arguments impossible, the author shifts the focus to function-space covering. The core of the proof is a 'rigidity lemma,' which demonstrates that for continuous piecewise-linear activations (like ReLU), the coefficients of the network's kink hyperplanes are controlled by the Lipschitz constant of the realized function. This allows the author to bound the complexity of the function class based on the number of kinks rather than the magnitude of the weights, enabling the use of metric entropy techniques to derive the lower bound.

The author proves that for two-layer networks with arbitrary weights, fitting noisy data with noise level sigma squared forces the Lipschitz constant to be at least of the order of the square root of (n / m), where n is the number of samples and m is the width of the network, up to a logarithmic factor. This result holds for any continuous piecewise-linear activation. Furthermore, the author provides a 'realized-kink-count' version of this law, showing that the bound depends on the number of distinct kink hyperplanes actually used by the network, regardless of how many redundant hidden units are present in the architecture.

This work provides a theoretical foundation for understanding the trade-off between model capacity and robustness. By proving that the law holds even for networks with arbitrary weights, the paper confirms that the requirement for high Lipschitz constants is an intrinsic property of the architecture's ability to fit noise, rather than an artifact of weight constraints. This clarifies the limits of interpolation in overparameterized models and provides a rigorous basis for why robust models generally require a larger number of neurons relative to the number of data points.