On Lipschitz Explosion in Deep Neural Networks with Normalization: Consequences for Optimization and Adversarial Robustness

Ashkan Soleymani, Reyhaneh Hosseinpourkhoshkbari, Hadi Daneshmand, Patrick JailletarXiv 2026 · arXiv

TL;DR

This paper reveals a surprising paradox: normalization layers (like Batch Norm), designed to stabilize training, can cause a network's sensitivity to perturbations—its Lipschitz constant—to explode exponentially with depth. This "Lipschitz explosion" makes standard theoretical guarantees for optimization, generalization, and robustness practically useless for deep normalized networks.

What Problem Does This Paper Address?

In deep learning, we often rely on architectural stabilizers like residual connections and normalization layers (Batch Norm, Layer Norm) to make training deep models feasible. Theoretically, many of our guarantees for these models—such as how fast they optimize or how robust they are to adversarial attacks—depend on the Lipschitz constant ($L$). This constant measures how much the output changes relative to a small change in the input or the parameters.

The common assumption is that if we control the norm of each individual layer, the total Lipschitz constant of the network will remain manageable. This paper challenges that assumption. The authors ask: Can a network look stable at every layer and still be exponentially unstable as a whole? They prove that for networks with normalization layers, the answer is a resounding "yes."

Methods

The authors provide a rigorous theoretical framework to prove that both input Lipschitzness (sensitivity to data changes) and parameter Lipschitzness (sensitivity to weight changes) can grow exponentially with depth $m$, even when layer-wise weights are strictly controlled (e.g., orthogonal matrices with norm $\le 1$).

Their core technique involves a rank-separation mechanism. They construct a "witness pair" of inputs: one that is low-rank and another nearby that is full-rank but nearly rank-deficient. They show that normalization layers amplify the separation between these two trajectories as they pass through the network.

To address the optimization challenges posed by this explosion, they introduce a new, relaxed stationarity concept called Probabilistic Goldstein Stationarity (PGS). Unlike standard notions that require polynomial time in $L$ (which is now exponential in depth), they provide a randomized algorithm that finds PGS points with complexity independent of $L$.

Datasets

The authors validate their theory using three standard image datasets:

  • MNIST
  • Fashion-MNIST
  • CIFAR-10

These datasets are used to demonstrate that natural images have an approximate low-rank structure, making them particularly susceptible to the rank-creating perturbations predicted by their theory.

Key Insights and Ideas

  • The Normalization Paradox: Normalization is intended to prevent gradients from vanishing or exploding, but it creates a "worst-case" instability that is invisible to local, layer-wise checks.
  • Rank Matters More Than Magnitude: The most "dangerous" perturbations aren't necessarily the largest ones in terms of norm. Instead, perturbations that introduce new singular directions (increasing the rank of the input representation) are amplified exponentially by normalization layers.
  • Geometry of Vulnerability: As shown in Figure 1, i.i.d. Gaussian noise (which is rank-creating) can fool a model even when the change is invisible to humans. Conversely, noise restricted to the image's original subspace can be much larger in magnitude without causing a misclassification.
Figure 1: We study the effect of different noise structures on the robustness of a multilayer neural network with normalization layers. Above, we add standard i.i.d. Gaussian noise; below, we instead apply noise restricted to the subspace of the original image. In the noisy images, red indicates positive values and blue indicates negative values. As depicted, even though the structured noise in the same subspace as the original image changes the image much more meaningfully (here, from a human perspective, making the 5 look more like an 8 as also observed in the noise pattern) the model still correctly classifies the image with high confidence. In contrast, under pixel-wise noise, despite the change being barely noticeable from a human perspective, the model is completely fooled and misclassifies the image with relatively high confidence. Our theoretical analysis predicts this phenomenon: the original image is low-rank, while i.i.d. Gaussian pixel noise makes the noisy image full-rank but nearly rank-deficient. Due to this relationship between the original image and the noisy one, normalization layers can amplify their separation across layers, causing neural networks’ vulnerability to noise. This separation and vulnerability do not arise when Gaussian noise is added within the same subspace as the original image, even at a much higher magnitude.
  • Vacuous Certificates: Because the Lipschitz constant grows exponentially, standard "dimension-free" bounds for generalization and robustness become vacuous (useless) as networks get deeper.

Key Results

  • Theoretical Explosion: The authors prove that $Lip(F_m) \ge C e^{\gamma m}$. This means the sensitivity grows exponentially with depth $m$, and by extension, with the parameter dimension $d$.
  • Empirical Validation: Experiments confirm that while generic random pairs of inputs don't show this explosion, specific "witness" pairs designed to exploit rank-separation exhibit the predicted exponential growth (see Figure 2).
Figure 2: Empirical validation of Lipschitz explosion. The constructed witness pair (X0, Y0) and its random rotations (QX0, QY0) grow exponentially with depth, while the median and 95th percentile over generic random local pairs remain nearly flat.
  • Adversarial Impact: The theory predicts, and experiments confirm, that rank-creating perturbations cause significantly sharper drops in accuracy and confidence than perturbations of the same energy that stay within the input's original singular subspace.

Limitations and Future Work

  • Linear vs. Non-linear: The primary lower bounds are established for linear activations to show that the explosion is a byproduct of normalization itself, not the activation function. While they extend some results to ReLU in the appendix, a broader study of different non-linearities remains for future work.
  • Average-case vs. Worst-case: The explosion is a worst-case phenomenon. As Figure 2b shows, generic random perturbations don't always trigger this explosion. Bridging the gap between this theoretical worst-case and typical training behavior is a key next step.
  • New Stability Notions: The authors suggest that we need new stability notions and analysis tools that better capture the behavior of modern normalized architectures, as Lipschitz-based tools are clearly insufficient for very deep models.

Summary updated

Abstract

Can a network look stable at every layer and still be exponentially unstable as a whole? The Lipschitz constant of a neural network is a basic stability quantity appearing in optimization guarantees, generalization bounds, and robustness certificates. Deep networks naturally admit two such notions, input Lipschitzness, measuring sensitivity to data perturbations, and parameter Lipschitzness, measuring sensitivity to weight perturbations. We prove that, for deep networks with normalization layers, with batch normalization as the canonical example, both Lipschitz constants can grow exponentially with depth and hence with parameter dimension, even under strong per-layer norm control such as $\|W_\ell\|_2\le 1$, and already for linear activations. Thus, a mechanism widely used to stabilize training can create severe worst-case instabilities that are invisible locally, i.e., from layerwise norm bounds alone. Parameter-Lipschitz explosion turns Lipschitz-dependent nonsmooth optimization guarantees into exponential-in-dimension bounds for deep normalized networks, while input-Lipschitz explosion makes worst-case Lipschitz-based generalization and robustness certificates vacuous. The latter also yields a concrete rank-separation mechanism for adversarial vulnerability. The theory predicts that perturbations introducing new singular directions should be amplified much more strongly than perturbations at the same noise level that remain within the input's original singular subspace. Experiments on MNIST, Fashion-MNIST, and CIFAR-10 support this prediction, showing that rank-creating perturbations cause substantially sharper drops in accuracy, confidence, and margins than same-subspace perturbations.
BibTeX
@misc{soleymani2026lipschitz,
  author = {Ashkan Soleymani and Reyhaneh Hosseinpourkhoshkbari and Hadi Daneshmand and Patrick Jaillet},
  title = {{On Lipschitz Explosion in Deep Neural Networks with Normalization: Consequences for Optimization and Adversarial Robustness}},
  year = {2026},
  eprint = {2611.08775},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08775},
}
Figure