Deep neural networks are increasingly deployed in applications involving critical decision-making, yet their vulnerability to adversarial perturbations raises important concerns regarding their reliability. This has motivated the need for methods that can rigorously assess and certify the robustness of such models.

In this thesis, we study the robustness of feedforward neural networks with ReLU activation functions. For ReLU networks, the robustness problem can be reformulated as a Mixed-Integer Linear Programming problem (MILP) , enabling the computation of maximum perturbations using state-of-the-art solvers. However, due to the computational complexity of MILP, approximate methods based on algorithmic bound propagation are often employed to obtain certified lower bounds on robustness.

We analyze neural network models trained on a smaller and bigger dataset respectively. The models for the respective datasets have architectures ranging from zero to five hidden layers. For each model, we compute the maximum admissible perturbation using an exact MILP solver, and compare it with three approximation methods: forward pass, forward-backward pass and FastLin. Additionally, we investigate the influence of different norm constraints on the robustness estimate.

The results show a consistent relationship between model complexity and the tightness of robustness bounds: more advanced models yield larger (less conservative) estimates of the maximum perturbation. Furthermore, the gap between approximate and exact methods increases with network depth, indicating that simpler methods become less accurate for deeper architectures. The choice of norm also significantly affects the bounds, with the L-infinity norm giving the smallest robustness bounds.

These findings all align with theoretical expectations, as approximate methods introduce layer-wise relaxations that accumulate with increasing network depth. Consequently, using such methods on deeper networks lead to looser bounds.

A limitation of this study is the relatively small scale of the models and datasets used. Future work could extend the analysis to larger and more complex models, as well as additional datasets, to further investigate the scalability and accuracy of robustness estimation methods.