Fractal Gadgets for Neural Networks: The Complexity of the Narrow Regime

Olivier Bournez, Johanne Cohen, Laura Cohen +1

We study the verification problem for deep narrow ReLU neural networks: given a network of bounded width computing a piecewise-affine map on [0,1], does some input satisfy a prescr…