The Cheeger-Coarea Bounds of ReLU Networks under Uniform Distributions: Generalisation, Double Descent, and Adversarial Robustness

Classical generalisation bounds for deep neural networks rely on parameter-dependent capacity measures, which become loose in the overparameterised regime. To resolve this, we establish a geometric framework by restricting our analysis to uniform probability distributions on bounded, flat manifolds, assuming a strictly curved optimal target boundary. Within this setting, we reframe Continuous Piecewise Affine ReLU networks as discrete spatial estimators, mapping their decision boundaries to the space of functions of Bounded Variation ($BV(\mathcal{M})$) and modelling classification regions as Caccioppoli sets. This isolates statistical capacity from ambient parameter counts, bounding it instead by the geometric surface tension (unweighted perimeter $P$) of the decision boundary. Utilising multi-scale Dudley chaining, we derive a generalisation bound scaling as $\mathcal{O}(P \cdot n^{-1/(d-1)})$ alongside a geometric $L^1$ algorithmic stability metric, identifying $d=3$ as the critical dimension separating classical parametric convergence from high-dimensional geometric penalties. Consequently, for $d > 3$, we formalise Double Descent as a combinatorial-isoperimetric phase transition: approximating the curved target exhausts the finite polyhedral facet budget, forcing highly irregular boundaries, whereas overparameterisation provides the combinatorial surplus necessary for geometric relaxation. Because bounding this spatial perimeter guarantees strict topological $L^1$ pre-compactness, the discrete empirical boundaries are prohibited from fractal degeneration, $\Gamma$-converging in the $L^1(\mathcal{M}, \mathcal{H}^d)$ topology to the optimal intrinsic Cheeger bottleneck $h(\mathcal{M})$. Because the uniform measure aligns the continuous perimeter with the discrete graph cut, bounding this limit via the empirical Fiedler eigenvalue ($\lambda_2$) establishes a spectral sandwich for the generalisation gap: $\Omega(\lambda_2 \cdot n^{-1/(d-1)}) \le \text{Gap} \le \mathcal{O}(\sqrt{\lambda_2} \cdot n^{-1/(d-1)})$. For margin $\gamma$ and minority class mass $\beta \in (0, 1/2]$, this projects to an algebraic capacity window $c_1 \gamma \beta \sqrt{\lambda_2} \le L(\mathcal{W}) \le c_2 \gamma \beta (1-\beta)$, prohibiting pure noise memorisation. Finally, subsuming Adversarial Robustness into this framework via the Federer-Fleming Coarea Formula yields the Inverse Perimeter Scaling, proving that noise interpolation collapses the expected adversarial radius to zero. Projecting the Cheeger ceiling onto the discrete graph establishes that maximum certifiable robustness obeys an $\mathcal{O}(\lambda_2^{-1})$ scaling, governed by the dataset's spectral entanglement.