Monday, February 10, 2025, 10:00
RICAM, SP2, 416-2

Towards an understanding of the complexity of ReLU neural networks

Deep neural networks with recti ed linear units (ReLU) as activation functions have been proven to be
powerful tools for solving various machine-learning problems. Despite being actively used in practice due
to their empirical advances, the theoretical understanding of these neural networks remains incomplete.
Expressivity, the ability of a xed neural network architecture to represent certain classes of continuous
piecewise-linear functions, is commonly used as a measure of the complexity of ReLU neural networks.
However, it has been shown that, depending on the machine-learning problem, the notion of complexity
may include di erent aspects that are not covered by the above de nition of expressivity.

In this talk, we look into the conditions for the optimal representation of continuous-piecewise linear
(CPWL) functions as a linear combination of max functions with ane-linear arguments. The observa-
tions obtained by computing those conditions highlight the limitation of expressivity provided by com-
binatorial approaches. Also, we look into practical challenges in classi cation problems, where current
de nitions of expressivity fail to adequately capture the complexity of decision boundaries and explain
the overcon dence exhibited in unbounded linear regions or the vulnerability to adversarial attacks.