![Thumbnail](/bitstream/handle/20.500.11850/677199/Expressivity.pdf.jpg?sequence=5&isAllowed=y)
Open access
Author
Date
2024Type
- Doctoral Thesis
ETH Bibliography
yes
Altmetrics
Abstract
The vulnerability of neural networks to adversarial examples is a major reliability concern, impeding their deployment in safety-critical applications. To address this, verification methods have emerged to analyze local robustness, often relying on convex relaxations to over-approximate the network's behavior. To get networks that are amenable to certification, specialized training methods have been designed aiming to train both accurate and certifiably robust networks. However, these training methods remain ineffective in all but the simplest settings and thus training certified neural networks remains despite significant effort an open challenge. This raises questions regarding the expressivity of certified neural networks, particularly their ability to approximate given functions. In this thesis, we investigate the expressivity of ReLU neural networks under convex relaxations. Our results show that while certified networks exist, their expressivity is limited compared to standard networks. Specifically, we show that ReLU networks certified with interval-bound-propagation (IBP) can approximately encode continuous functions on compact domains and are hence universal. This universality result directly implies the universality of ReLU networks certified by more precise convex relaxations. Further, we show that single hidden layer ReLU networks are not universal approximators when analyzed using IBP, showcasing a fundamental limitation. Aiding to that, we can show that even the most precise single-neuron convex relaxation cannot exactly encode simple multivariate monotone and convex piecewise linear functions exactly. This impossibility result is surprising as ReLU networks naturally express the class of piecewise linear functions. As before, this impossibility result directly generalizes to all less precise convex relaxations. These results however do not separate different single-neuron convex relaxations by expressivity. To address this, we present a series of results, demonstrating that more precise relaxations enable certified networks to encode a broader class of functions or offer increased flexibility when encoding the same function. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000677199Publication status
publishedExternal links
Search print copy at ETH Library
Publisher
ETH ZurichSubject
Adversarial Robustness; Certified Robustness; Trustworthy AI; Universal ApproximationOrganisational unit
03948 - Vechev, Martin / Vechev, Martin
More
Show all metadata
ETH Bibliography
yes
Altmetrics