Max-Total-Flow Generalization Bounds for DAG-Structured ReLU Deep Neural Networks

Understanding generalization in over-parameterized neural networks remains a fundamental challenge. While recent path-norm frameworks address general directed acyclic graph (DAG) networks with skip connections, branching, and merging, they require computing astronomically large path-norms that render generalization bounds vacuous in practice. In this study, a new perspective is proposed by interpreting Karush–Kuhn–Tucker (KKT) optimality conditions as a flow conservation law over the DAG. At a KKT point, the squared Frobenius norms of weight matrices define non-negative flows on edges that satisfy classical conservation equations at every interior node. Using flow decomposition, we prove that at every KKT point the total parameter norm is bounded in terms of the longest source-to-sink path length $T_G$ of the DAG $G$ and the regularization parameter $\lambda$. Combining this norm control with a held-out validation set and a change-of-measure argument under a Gaussian perturbation of the weights with noise level $ϵ$, we show that, with probability at least $1-\delta$, the validation loss of the trained network exceeds its expected training loss by at most $O(\sqrt{\ln (1/\delta )/r}+\sqrt{T_G/({ϵ}^2\lambda n)})$, for $n$ training and $r$ validation samples. The results cover binary and multi-class classification and regression, and extend to Leaky ReLU activations.