On the Correctness of Automatic Differentiation for Neural Networks with
  Machine-Representable Parameters
Recent work has shown that forward- and reverse- mode automatic
differentiation (AD) over the reals is almost always correct in a
mathematically precise sense. However, actual programs work with
machine-representable numbers (e.g., floating-point numbers), not reals. In
this paper, we study the correctness of AD when the parameter space of a neural
network consists solely of machine-representable numbers. In particular, we
analyze two sets of parameters on which AD can be incorrect: the incorrect set
on which the network is differentiable but AD does not compute its derivative,
and the non-differentiable set on which the network is non-differentiable. For
a neural network with bias parameters, we first prove that the incorrect set is
always empty. We then prove a tight bound on the size of the non-differentiable
set, which is linear in the number of non-differentiabilities in activation
functions, and give a simple necessary and sufficient condition for a parameter
to be in this set. We further prove that AD always computes a Clarke
subderivative even on the non-differentiable set. We also extend these results
to neural networks possibly without bias parameters.
Wonyeol Lee, Sejun Park, Alex Aiken
# On the Correctness of Automatic Differentiation

###### Abstract

Recent work has shown that automatic differentiation over the reals is almost always correct in a mathematically precise sense. However, actual programs work with _machine-representable numbers_ (e.g., floating-point numbers), not reals. In this paper, we study the correctness of automatic differentiation when the parameter space of a neural network consists solely of machine-representable numbers. For a neural network _with bias parameters_, we prove that automatic differentiation is correct at all parameters where the network is differentiable. In contrast, it is incorrect at all parameters where the network is non-differentiable, since it never informs non-differentiability. To better understand this non-differentiable set of parameters, we prove a tight bound on its size, which is linear in the number of non-differentiabilities in activation functions, and provide a simple necessary and sufficient condition for a parameter to be in this set. We further prove that automatic differentiation always computes a Clarke subderivative, even on the non-differentiable set. We also extend these results to neural networks possibly without bias parameters.

Machine-Representable Parameters, Automatic Differentiation, Neural Networks, Machine-Representable Parameters

## 1 Introduction

Automatic differentiation refers to various algorithms that compute the derivative of a function represented by a program. Diverse practical systems for automatic differentiation have been developed for general-purpose programs (Baydin et al., 2016; Hascoet & Pascual, 2013; Maclaurin et al., 2015; Pearlmutter & Siskind, 2008; Revels et al., 2016; Slusanschi & Dumitrel, 2016; Walther & Griewank, 2012), and particularly for machine-learning programs (Bergstra et al., 2010; Collobert et al., 2011; Jia et al., 2014; Seide & Agarwal, 2016; Tokui et al., 2019; van Merrienboer et al., 2018), including TensorFlow (Abadi et al., 2016), PyTorch (Paszke et al., 2017), and JAX (Frostig et al., 2018). The development of such automatic differentiation systems has been a driving force of the rapid advances in deep learning (and machine learning in general) in the past 10 years (Baydin et al., 2017; Goodfellow et al., 2016; LeCun et al., 2015; Schmidhuber, 2015).

Recently, the correctness of automatic differentiation has been actively studied for various types of programs. For programs that only use differentiable functions, automatic differentiation is correct _everywhere_, i.e., it computes the derivative of a given program at all inputs (Abadi & Plotkin, 2020; Barthe et al., 2020; Brunel et al., 2020; Elliott, 2018; Huot et al., 2020; Krawiec et al., 2022; Radul et al., 2023; Smeding & Vakar, 2023; Vakar, 2021). On the other hand, for programs that use non-differentiable functions (e.g., \(\mathrm{ReLU}^{1}\)), automatic differentiation can be incorrect at some inputs (Bolte & Pauwels, 2020; Griewank & Walther, 2008; Lee et al., 2020).

There are two cases where automatic differentiation is incorrect. The first case is when the function \(f\) represented by a given program is differentiable at some \(x\), but automatic differentiation returns a value different from the derivative of \(f\) at \(x\). For instance, consider a program2 that represents the identity function, defined as \(\mathrm{ReLU}(x)-\mathrm{ReLU}(-x)\). If automatic differentiation uses zero as a "derivative" of \(\mathrm{ReLU}\) at \(x=0\), as is standard (e.g., in TensorFlow and PyTorch), it returns zero for this program at \(x=0\) while the true derivative is one. The second case is when \(f\) is non-differentiable at some \(x\), but automatic differentiation returns some finite value and does not signal the information about the non-differentiability of \(f\) at \(x\). For example, \(\mathrm{ReLU}(x)\) represents a function that is non-differentiable at \(x=0\), but automatic differentiation outputs some real number for this program at \(x=0\). Although automatic differentiation can be incorrect, recent works show that for a large class of programs using non-differentiable functions, automatic differentiation is correct _almost everywhere_, i.e., it is incorrect at most on a Lebesgue measure-zero subset of the input domain of a program (Bolte & Pauwels, 2020;
Lee et al., 2020; Lew et al., 2021; Mazza & Pagani, 2021).

These prior works, however, have a limitation: they consider automatic differentiation over the real numbers, but in practice, inputs to a program are always _machine-representable numbers_ such as \(32\)-bit floating-point numbers. Since the set of machine-representable numbers is countable (and usually finite), it is always a Lebesgue measure-zero subset of the real numbers. Hence, automatic differentiation could be incorrect on _all_ machine-representable inputs according to prior works, and this is indeed possible. Consider a program3 for a function from \(\mathbb{R}\) to \(\mathbb{R}\), defined as

Footnote 3: Inspired by Bolte & Pauwels (2020b); Mazza & Pagani (2021).

\[\sum_{c\in\mathbb{H}}\Big{[}\lambda x+\Big{(}\frac{1}{|\mathbb{H}|}-\lambda \Big{)}\Big{(}\mathrm{ReLU}(x-c)-\mathrm{ReLU}(-x+c)\Big{)}\Big{]},\]

where \(\mathbb{H}\subseteq\mathbb{R}\) is a finite set of machine-representable numbers and \(\lambda\in\mathbb{R}\setminus\{1\}\) is an arbitrary constant. Then, the program represents the affine function \(x\mapsto x+a\) for \(a=(\lambda-\frac{1}{|\mathbb{H}|})\times\sum_{c\in\mathbb{H}}c\), but automatic differentiation incorrectly computes its derivative at any \(x\in\mathbb{H}\) as \(\lambda\) (the arbitrarily chosen value) if zero is used as a "derivative" of \(\mathrm{ReLU}\) at \(0\) as before.4

Footnote 4: We can even make automatic differentiation return different values at different \(x\in\mathbb{H}\), by using a different \(\lambda_{i}\) for each \(c_{i}\in\mathbb{H}\). Similarly, we can also construct a program such that at all machine-representable numbers \(\mathbb{H}\), the program is non-differentiable and automatic differentiation returns arbitrary values.

Given these observations, we raise the following questions: for a program that represents a neural network, at which machine-representable inputs to the program (i.e., parameters to the network) can automatic differentiation be incorrect, and how many such inputs can there be? In this work, we tackle these questions and present the first theoretical results. In particular, we study the two sets of machine-representable parameters of a neural network on which automatic differentiation is incorrect: the _incorrect set_, on which the network is differentiable but automatic differentiation does not compute its derivative, and the _non-differentiable set_, on which the network is non-differentiable.

**Summary of results.** We focus on neural networks consisting of alternating analytic pre-activation functions (e.g., fully-connected and convolution layers) and pointwise continuous activation functions (e.g., \(\mathrm{ReLU}\) and \(\mathrm{Sigmoid}\)). The first set of our results (SS3) is for such networks _with bias parameters_ at every layer, and is summarized as follows.

* We prove that the incorrect set is _always empty_, not only over machine-representable parameters but also over real-valued ones. To our knowledge, this is the first result showing that the incorrect set can be empty for a class of neural networks using possibly non-differentiable functions; prior works only bounded the measure of this set.
* On the other hand, the non-differentiable set can be non-empty. We give a tight bound on its density over all machine-representable parameters, which has the form \(n/|\mathbb{H}|\) where \(n\) is the _total number of non-differentiable points_ in activation functions. This result implies that in practice, the non-differentiable set often has a low density, especially if we use high-precision parameters (e.g., use \(32\)-bit floating-point numbers for \(\mathbb{H}\), where \(|\mathbb{H}|\approx 2^{32}\)).
* To better describe the non-differentiable set, we provide a simple, easily verifiable _necessary and sufficient condition_ for a parameter to be in the non-differentiable set. Given that deciding the differentiability of a neural network is NP-hard in general (Bolte et al., 2022), our result is surprising: having bias parameters is sufficient to efficiently decide the differentiability.
* Given that the non-differentiable set can be non-empty, a natural question arises: what does automatic differentiation compute on this set? We prove that automatic differentiation _always computes a Clarke subderivative_ (a generalized derivative) even on the non-differentiable set. That is, automatic differentiation is an efficient algorithm for computing a Clarke subderivative in this case.

The second set of our results (SS4) extends the above results to neural networks possibly _without bias parameters_ at some layers, and is summarized as follows.

* As we observed in the \(\mathrm{ReLU}(x)-\mathrm{ReLU}(-x)\) example, the incorrect set can be non-empty in this case. Thus, we prove tight bounds on the density of both the incorrect and non-differentiable sets, which have the form \(n^{\prime}/|\mathbb{H}|\) where \(n^{\prime}\) is linear in the total number of non-differentiable points in activation functions as well as the total number of boundary points in activation functions' zero sets.
* We provide simple, easily verifiable sufficient conditions on parameters under which automatic differentiation computes the standard derivative or a Clarke subderivative.

Our theoretical results carry two main practical implications: automatic differentiation for neural networks is correct on most machine-representable parameters, and it is correct more often with bias parameters. For networks with bias parameters at all layers, our results further provide an exact characterization of when automatic differentiation is correct and what it computes. We remark that our results may not be directly applicable to neural networks with non-analytic pre-activation functions or non-pointwise activation functions. We discuss this and related limitations in SS5.

**Organization.** We first introduce notation and the problem setup (SS2). We then present our main results for neural networks with bias parameters (SS3) and extend them to neural networks possibly without bias parameters (SS4). We conclude the paper with discussion (SS5).
## 2 Problem Setup

### Notation and Definitions

We use the following notation and definitions. Let \(\mathbb{N}\) and \(\mathbb{R}\) be the sets of positive integers and real numbers, respectively. For \(n\in\mathbb{N}\), we use \([n]\triangleq\{1,2,\ldots,n\}\) and \(\vec{0}_{n}\triangleq(0,\ldots,0)\in\mathbb{R}^{n}\), and often drop \(n\) from \(\vec{0}_{n}\) when the subscript is clear from context. For \(x=(x_{1},\ldots,\)\(x_{n})\in\mathbb{R}^{n}\), we use \(x_{-i}\triangleq(x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n})\). We call \(A\subseteq\mathbb{R}\) an _interval_ if it is \([a,b]\), \([a,b)\), \((a,b]\), or \((a,b)\) for some \(a,b\in\mathbb{R}\cup\{\pm\infty\}\). For \(A\subseteq\mathbb{R}^{n}\), \(\mathit{int}(A)\) and \(bd(A)\) denote the interior and the boundary of \(A\), and \(\mathbf{1}_{A}:\mathbb{R}^{n}\rightarrow\{0,1\}\) denotes the indicator function of \(A\). We say that \(f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\) is _analytic_ if it is infinitely differentiable and its Taylor series at any \(x\in\mathbb{R}^{n}\) converges to \(f\) on some neighborhood of \(x\). For \(f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\),

\[Df:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m\times n}\cup\{\bot\}\]

denotes the standard derivative of \(f\), where \(f(x)=\bot\) denotes that \(f\) is non-differentiable at \(x\). Lastly, for \(f:\mathbb{R}\rightarrow\mathbb{R}\),

\[\mathsf{ndf}(f) \triangleq\{x\in\mathbb{R}\mid\text{$f$ is non-differentiable at $x$}\},\] \[\mathsf{bdz}(f) \triangleq bd(\{x\in\mathbb{R}\mid f(x)=0\})\]

denote the set of non-differentiable points of \(f\) and the boundary of the zero set of \(f\), respectively.

### Neural Networks

We define a neural network as follows, following (Jacot et al., 2018; Laurent and von Brecht, 2018). Given the number of layers \(L\in\mathbb{N}\), let \(N_{0}\in\mathbb{N}\) be the dimension of input data, \(N_{l}\in\mathbb{N}\) and \(W_{l}\in\mathbb{N}\cup\{0\}\) be the number of neurons and the number of parameters at layer \(l\in[L]\), and \(N\triangleq N_{1}+\cdots+N_{L}\) and \(W\triangleq W_{1}+\cdots+W_{L}\). Further, for each \(l\in[L]\), let \(\tau_{l}:\mathbb{R}^{N_{l-1}}\times\mathbb{R}^{W_{l}}\rightarrow\mathbb{R}^{ N_{l}}\) be an analytic _pre-activation function_ and \(\sigma_{l}:\mathbb{R}^{N_{l}}\rightarrow\mathbb{R}^{N_{l}}\) be a pointwise, continuous _activation function_, i.e.,

\[\sigma_{l}(x_{1},\ldots,x_{N_{l}})\triangleq\big{(}\sigma_{l,1}(x_{1}),\ldots,\sigma_{l,N_{l}}(x_{N_{l}})\big{)}\]

for some continuous \(\sigma_{l,i}:\mathbb{R}\rightarrow\mathbb{R}\). Under this setup, we define a neural network as a function of model parameters: given input data \(c\in\mathbb{R}^{N_{0}}\), a _neural network_\(z_{L}(\,\cdot\,;c):\mathbb{R}^{W}\rightarrow\mathbb{R}^{N_{L}}\) is defined as

\[z_{L}(w;c)\triangleq(\sigma_{L}\circ\tau_{L}^{(w_{L})}\circ\cdots\circ\sigma_{ 1}\circ\tau_{1}^{(w_{1})})(c),\]

where \(w\triangleq(w_{1},\ldots,w_{L})\), \(w_{l}\triangleq(w_{l,1},\ldots,w_{l,W_{l}})\in\mathbb{R}^{W_{l}}\), and \(\tau_{l}^{(w_{l})}(x)\triangleq\tau_{l}(x,w_{l})\). We say such \(z_{L}\)_has \(L\) layers, \(N\) neurons, and \(W\) parameters_.

We next define the _activation neurons_\(z_{l}(\,\cdot\,;c):\mathbb{R}^{W}\rightarrow\mathbb{R}^{N_{l}}\) and the _pre-activation values_\(y_{l}(\,\cdot\,;c):\mathbb{R}^{W}\rightarrow\mathbb{R}^{N_{l}}\) at layer \(l\in[L]\), as we defined \(z_{L}\) above:

\[z_{l}(w;c)\triangleq(\sigma_{l}\circ\tau_{l}^{(w_{l})}\circ\cdots\circ\sigma_{ 1}\circ\tau_{1}^{(w_{1})})(c),\]

\[y_{l}(w;c)\triangleq\tau_{l}^{(w_{l})}(z_{l-1}(w;c)),\]

where \(z_{0}(w;c)\triangleq c\). Since the input data \(c\) is fixed while we compute the derivative of \(z_{L}\) with respect to \(w\) (e.g., in order to train \(z_{L}\)), we often omit \(c\) and simply write \(z_{l}(w)\) and \(y_{l}(w)\) to denote \(z_{l}(w;c)\) and \(y_{l}(w;c)\), respectively.

For the set of all indices of neurons

\[\mathsf{ldx}\triangleq\{(l,i)\mid l\in[L],i\in[N_{l}]\}\]

and for each \((l,i)\in\mathsf{ldx}\), we use \(y_{l,i},z_{l,i}:\mathbb{R}^{W}\rightarrow\mathbb{R}\) and \(\tau_{l,i}:\mathbb{R}^{N_{l-1}}\times\mathbb{R}^{W_{l}}\rightarrow\mathbb{R}\) to denote the functions that take only the \(i\)-th output component of \(y_{l}\), \(z_{l}\), and \(\tau_{l}\), respectively. Note that we defined \(\sigma_{l,i}\) above in a slightly different way: its domain is not \(\mathbb{R}^{N_{l}}\) (i.e., the domain of \(\sigma_{l}\)) but \(\mathbb{R}\).

Finally, we introduce the notion of piecewise-analytic5 to consider possibly non-differentiable activation functions.

Footnote 5: It is inspired by the notion of PAP in Lee et al. (2020).

**Definition 2.1**.: A function \(f:\mathbb{R}\rightarrow\mathbb{R}\) is _piecewise-analytic_ if there exist \(n\in\mathbb{N}\), a partition \(\{A_{i}\}_{i\in[n]}\) of \(\mathbb{R}\) consisting of non-empty intervals, and analytic functions \(\{f_{i}:\mathbb{R}\rightarrow\mathbb{R}\}_{i\in[n]}\) such that \(f=f_{i}\) on \(A_{i}\) for all \(i\in[n]\).

**Assumption**.: \(\sigma_{l,i}\) is piecewise-analytic for all \((l,i)\in\mathsf{ldx}\).

The class of piecewise-analytic functions includes not only all analytic functions but also many non-differentiable functions widely used in neural networks such as ReLU, LeakyReLU, and HardSigmoid. Hence, our definition of neural networks includes a rich class of practical networks: \(\tau_{l}\) can be any analytic function (e.g., a fully-connected, convolution, or normalization layer), and \(\sigma_{l}\) can be any pointwise continuous and piecewise-analytic function (e.g., ReLU, LeakyReLU, or HardSigmoid).

In practice, we often apply automatic differentiation to the composition of a neural network \(z_{L}\) and a loss function \(\ell\) (e.g., Softmax followed by CrossEntropy), to compute the derivative of the loss value of \(z_{L}\) with respect to its parameters. We emphasize that all of our results continue to hold even if \(z_{L}\) in the results is replaced by \(\ell\circ z_{L}\) for any analytic \(\ell:\mathbb{R}^{N_{L}}\rightarrow\mathbb{R}^{m}\). For simplicity, however, we state our results only for \(z_{L}\) and not for \(\ell\circ z_{L}\).

### Automatic Differentiation

As discussed in SS1, automatic differentiation operates not on mathematical functions, but on programs that represent those functions. To this end, we define a program \(\mathtt{P}\) that represents a function from \(\mathbb{R}^{W}\) to \(\mathbb{R}\) as follows:

\[\mathtt{P}::=r\mid\mathtt{w}_{l,j}\mid f\left(\mathtt{P}_{1},\ldots,\mathtt{P} _{n}\right)\]

where \(r\in\mathbb{R}\), \(l\in[L]\), \(j\in[W_{l}]\), \(f\in\{\tau_{l,i},\sigma_{l,i}\mid(l,i)\in\mathsf{ldx}\}\), and \(n\in\mathbb{N}\). This definition says that a program
can be either a real-valued constant \(r\), a real-valued parameter \(w_{l,j}\), or the application of a function \(f:\mathbb{R}^{n}\to\mathbb{R}\) to subprograms \(\mathtt{P}_{1},\ldots,\mathtt{P}_{n}\). In this paper, we focus on particular programs \(\mathtt{P}_{y_{i,i}}\) and \(\mathtt{P}_{z_{l,i}}\) that represent the functions \(y_{l,i}(\,\cdot\,;c),z_{l,i}(\,\cdot\,;c):\mathbb{R}^{W}\to\mathbb{R}\) and are defined in a canonical way as follows:

\[\mathtt{P}_{y_{l,i}} \triangleq\tau_{l,i}\left(\mathtt{P}_{z_{l-1,1}},\ldots,\mathtt{ P}_{z_{l-1,N_{l-1}}},w_{l,1},\ldots,w_{l,W_{l}}\right),\] \[\mathtt{P}_{z_{l,i}} \triangleq\sigma_{l,i}\left(\mathtt{P}_{y_{l,i}}\right),\]

where \(\mathtt{P}_{z_{0,i^{\prime}}}\triangleq c_{i^{\prime}}\) for \(i^{\prime}\in[N_{0}]\) represents the constant function \(z_{0,i^{\prime}}(\,\cdot\,;c):\mathbb{R}^{W}\to\mathbb{R}\).

Given a program \(\mathtt{P}\), we define \(\llbracket\mathtt{P}\rrbracket:\mathbb{R}^{W}\to\mathbb{R}\) as the function represented by \(\mathtt{P}\), and \(\llbracket\mathtt{P}\rrbracket^{\mathsf{AD}}:\mathbb{R}^{W}\to\mathbb{R}^{1 \times W}\) as the function that automatic differentiation computes when applied to \(\mathtt{P}\). These functions are defined inductively as follows (Abadi and Plotkin, 2020; Baydin et al., 2017; Lee et al., 2020):

\[\llbracket r\rrbracket(w) \triangleq r,\] \[\llbracket w_{l,j}\rrbracket(w) \triangleq w_{l,j},\] \[\llbracket f\left(\mathtt{P}_{1},\ldots,\mathtt{P}_{n}\right) \rrbracket(w) \triangleq f\big{(}\llbracket\mathtt{P}_{1}\rrbracket(w),\ldots, \llbracket\mathtt{P}_{n}\rrbracket(w)\big{)},\] \[\llbracket r\rrbracket^{\mathsf{AD}}(w) \triangleq \mathtt{0},\] \[\llbracket w_{l,j}\rrbracket^{\mathsf{AD}}(w) \triangleq \mathtt{1}_{l,j},\] \[\llbracket f\left(\mathtt{P}_{1},\ldots,\mathtt{P}_{n}\right) \rrbracket^{\mathsf{AD}}(w) \triangleq D^{\mathsf{AD}}f\big{(}\llbracket\mathtt{P}_{1}\rrbracket(w), \ldots,\llbracket\mathtt{P}_{n}\rrbracket(w)\big{)}\] \[\quad\cdot\big{[}\llbracket\mathtt{P}_{1}\rrbracket^{\mathsf{ AD}}(w)\big{/}\cdots\big{/}\big{/}\llbracket\mathtt{P}_{n}\rrbracket^{\mathsf{AD}}(w)\big{]}.\]

Here \(w_{l,j}\in\mathbb{R}\) is defined as \((w_{1,1},w_{1,2}\ldots,w_{L,W_{L}})\triangleq w\), \(\mathtt{0},\mathtt{1}_{l,j}\in\mathbb{R}^{1\times W}\) denote the zero matrix and the matrix whose entries are all zeros except for a single one at the \((W_{1}+\cdots+W_{l-1}+j)\)-th entry, \(D^{\mathsf{AD}}f:\mathbb{R}^{n}\to\mathbb{R}^{1\times n}\) denotes a "derivative" of \(f\) used by automatic differentiation, and \([M_{1}\,/\cdots\,/\,M_{n}]\) denotes the matrix that stacks up matrices \(M_{1},\ldots,M_{n}\) vertically. Note that \(\llbracket f\left(\mathtt{P}_{1},\ldots,\mathtt{P}_{n}\right)\rrbracket^{ \mathsf{AD}}\) captures the essence of automatic differentiation: it computes derivatives based on the chain rule for differentiation.

Using the above definitions, we define \(D^{\mathsf{AD}}z_{L}:\mathbb{R}^{W}\to\mathbb{R}^{N_{L}\times W}\) as the result of applying automatic differentiation6 to a program that canonically represents a neural network \(z_{L}:\mathbb{R}^{W}\to\mathbb{R}^{N_{L}}\):

Footnote 6: We remark that the definition of \(D^{\mathsf{AD}}z_{L}\) (and \(\llbracket\mathtt{P}\rrbracket^{\mathsf{AD}}\)) does not assume any specific choice of automatic differentiation algorithms (e.g., forward-mode or reverse-mode). Thus, all of our results are applicable to any choice of those algorithms.

\[D^{\mathsf{AD}}z_{L}(w)\triangleq\big{[}\llbracket\mathtt{P}_{z_{L,1}} \rrbracket^{\mathsf{AD}}(w)\,\big{/}\cdots\big{/}\,\llbracket\mathtt{P}_{z_{L,N _{L}}}\rrbracket^{\mathsf{AD}}(w)\big{]}.\]

The output \(D^{\mathsf{AD}}z_{L}\) of automatic differentiation depends on the choice of \(D^{\mathsf{AD}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
\(z_{L}\) is differentiable but automatic differentiation does not compute its standard derivative; on the non-differentiable set \(\mathsf{ndf}_{\Omega}(z_{L})\), \(z_{L}\) is non-differentiable but automatic differentiation outputs some finite values without informing non-differentiability. Note that \(\mathsf{ndf}_{\Omega}(z_{L})\subseteq\Omega\) is different from \(\mathsf{ndf}(f)\subseteq\mathbb{R}\) which was defined in SS2.1 for \(f:\mathbb{R}\to\mathbb{R}\).

## 3 Correctness of Automatic Differentiation for Neural Networks with Bias Parameters

Our main objective is to understand the incorrect and non-differentiable sets. In particular, we focus on neural networks with bias parameters (defined below) in this section and consider more general neural networks in SS4. For the former class of neural networks, we characterize the incorrect and non-differentiable sets in SS3.1 and SS3.2, and establish a connection between automatic differentiation and Clarke subderivatives (a generalized notion of derivative) in SS3.3.

We start by defining neural networks with bias parameters.

**Definition 3.1**.: A pre-activation function \(\tau_{l}:\mathbb{R}^{N_{l-1}}\times\mathbb{R}^{W_{l}}\to\mathbb{R}^{N_{l}}\) of a neural network _has bias parameters_ if \(W_{l}\geq N_{l}\) and for all \(i\in[N_{l}]\), there is \(f_{i}:\mathbb{R}^{N_{l-1}}\times\mathbb{R}^{W_{l}-N_{l}}\to\mathbb{R}\) such that \(\tau_{l,i}(x,(u,v))=f_{i}(x,u)+v_{i}\) for all \((u,v)\in\mathbb{R}^{W_{l}-N_{l}}\times\mathbb{R}^{N_{l}}\). Here \(v_{i}\) is called the _bias parameter of \(\tau_{l,i}\)_. A neural network \(z_{L}\)_has bias parameters_ if \(\tau_{l}\) has bias parameters for all \(l\in[L]\).

We note that many popular pre-activation functions, including fully-connected, convolution, and normalization layers, are typically implemented with bias parameters in practice.

### Characterization of the Incorrect Set

We first show that the incorrect set of a neural network is _always empty_ if the network has bias parameters, i.e., automatic differentiation computes the standard derivative wherever the network is differentiable.

**Theorem 3.2**.: _If a neural network \(z_{L}\) has bias parameters, then for all \(w\in\mathbb{R}^{W}\) at which \(z_{L}\) is differentiable,_

\[D^{\mathsf{AD}}z_{L}(w)=Dz_{L}(w). \tag{1}\]

_This implies that \(|\mathsf{inc}_{\Omega}(z_{L})|=0\)._

It should be emphasized that Eq. (1) is not only for machine-representable parameters, but also for any _real-valued_ parameters. Compared to existing results, this result is surprising. For instance, Bolte & Pauwels (2020); Lee et al. (2020) show that the incorrect set over \(\mathbb{R}^{n}\) (not over \(\mathbb{M}^{n}\)) has Lebesgue measure zero for some classes of programs, but they do not give any results on whether the set can be empty. In contrast, Theorem 3.2 states that the incorrect set over \(\mathbb{R}^{n}\) is empty for a smaller, yet still large class of programs, i.e., neural networks with bias parameters.

In Theorem 3.2, the condition that \(z_{L}\) has bias parameters plays a crucial role. Namely, Theorem 3.2 does not hold if this condition is dropped. For instance, consider a neural network \(z_{L}:\mathbb{R}\to\mathbb{R}\) that is essentially the same as \(f:\mathbb{R}\to\mathbb{R}\) with \(f(w)=\mathrm{ReLU}(w)-\mathrm{ReLU}(-w)\) (which we discussed in SS1). Then, \(z_{L}\) does not have bias parameters, and \(\mathsf{inc}_{\Omega}(z_{L})\) is non-empty if \(D^{\mathsf{AD}}\mathrm{ReLU}=\mathbf{1}_{(0,\infty)}\) is used.

The proof of Theorem 3.2 consists of the following two arguments: for all \(w\in\mathbb{R}^{W}\) with \(Dz_{L}(w)\neq\bot\),

1. if \(y_{l,i}(w)\in\mathsf{ndf}(\sigma_{l,i})\), then \(\partial z_{L}/\partial z_{l,i}=\vec{0}\) at \(w\), and
2. if (i) holds, then \(D^{\mathsf{AD}}z_{L}(w)=Dz_{L}(w)\).

That is, (i) if a pre-activation value \(y_{l,i}\) touches a non-differentiable point of its activation function \(\sigma_{l,i}\), then the derivative of \(z_{L}\) with respect to \(z_{l,i}\) should always be zero; and (ii) Theorem 3.2 follows from (i). We point out that the proof of (i) relies heavily on the bias parameter condition. For more details, see Appendix C.

### Characterization of the Non-Differentiable Set

We next show that if a neural network has bias parameters, then the density of the non-differentiable set in \(\Omega\) is bounded by \(n/|\mathbb{M}|\), where \(n\) is the total number of non-differentiable points in activation functions.

**Theorem 3.3**.: _If a neural network \(z_{L}\) has bias parameters,_

\[\frac{|\mathsf{ndf}_{\Omega}(z_{L})|}{|\Omega|}\leq\frac{1}{|\mathbb{M}|}\sum_ {(l,i)\in\mathsf{ldx}}|\mathsf{ndf}(\sigma_{l,i})|\]

_where \(\mathsf{ndf}(f)\) is the set of non-differentiable points of \(f\)._

In many practical settings, the bound in Theorem 3.3 is often small, especially under high-precision parameters. For example, \(\mathbb{M}\) is frequently chosen as the set of \(32\)-bit floating-point numbers so \(|\mathbb{M}|\approx 2^{32}\), while \(|\mathsf{ldx}|\) (the number of neurons) is often smaller than \(2^{32}\) and \(|\mathsf{ndf}(\sigma_{l,i})|\) is typically small (e.g., \(0\) for differentiable \(\sigma_{l,i}\), \(1\) for \(\mathrm{ReLU}\), and \(2\) for \(\mathrm{HardSigmoid}\)). This implies that in practice, the non-differentiable set often has a low density in \(\Omega\). We remark, however, that the bound in Theorem 3.3 can grow large in low-precision settings (e.g., when parameters are represented by \(\leq 16\)-bit numbers).

Although the bound in Theorem 3.3 can be large in some cases (e.g., when \(|\mathbb{M}|\) is small), we prove that the bound is in general tight up to a constant multiplicative factor.

**Theorem 3.4**.: _For any \(\mathbb{M}\subseteq\mathbb{R}\) and \(n,\alpha\in\mathbb{N}\) with \(1\leq|\mathbb{M}|<\infty\), \(n\geq 2\), and \(\alpha\leq|\mathbb{M}|/(n-1)\), there is a neural network \(z_{L}:\mathbb{R}^{W}\to\mathbb{R}\) with bias parameters that satisfies_

\[\frac{|\mathsf{ndf}_{\Omega}(z_{L})|}{|\Omega|}\geq\frac{1}{2}\cdot\frac{1}{| \mathbb{M}|}\sum_{(l,i)\in\mathsf{ldx}}|\mathsf{ndf}(\sigma_{l,i})|\]

_and the following: \(z_{L}\) has \(n+1\) neurons and \(|\mathsf{ndf}(\sigma_{1,i})|=\alpha\) for all \(i\in[N_{1}]\)._
In Theorem 3.4, the condition \(\alpha\leq|\mathbb{M}|/(n-1)\) is for achieving the constant \(1/2\) in the bound. A similar bound can be derived for a larger \(\alpha\) (i.e., \(\alpha>|\mathbb{M}|/(n-1)\)) but with a constant smaller than \(1/2\).

Theorems 3.3 and 3.4 describe how large the non-differentiable set \(\mathsf{ndf}_{\Omega}(z_{L})\) can be, but give no clue about exactly which parameters constitute this set. To better understand this, we present an easily verifiable _necessary and sufficient_ condition for characterizing \(\mathsf{ndf}_{\Omega}(z_{L})\).

**Theorem 3.5**.: _If a neural network \(z_{L}\) has bias parameters, then the following are equivalent for all \(w\in\mathbb{R}^{W}\)._

* \(z_{L}\) _is non-differentiable at_ \(w\)_._
* \(y_{l,i}(w)\in\mathsf{ndf}(\sigma_{l,i})\) _and_ \(\partial^{\mathsf{AD}}z_{L}/\partial z_{l,i}\neq\vec{0}\) _at_ \(w\) _for some_ \((l,i)\in\mathsf{ldx}\)_._

Here \(\partial^{\mathsf{AD}}z_{L}/\partial z_{l,i}\) denotes the partial derivative of \(z_{L}\) with respect to \(z_{l,i}\) that _reverse-mode_ automatic differentiation (e.g., backpropagation) computes as a byproduct of computing \(D^{\mathsf{AD}}z_{L}\) (see Appendix E for more details). Hence, Theorem 3.5 implies that we can efficiently7 decide whether a neural network with bias parameters is differentiable at a (real-valued) parameter or not. This result is somewhat surprising given a recent, relevant result that deciding such differentiability is NP-hard in general (Bolte et al., 2022).

Footnote 7: in \(\mathcal{O}(N_{L}T)\) time for a neural network \(z_{L}:\mathbb{R}^{W}\to\mathbb{R}^{N_{L}}\) where \(T\) is the time to evaluate \(z_{L}(w)\), because reverse-mode automatic differentiation takes \(\mathcal{O}(N_{L}T)\) time to compute \(D^{\mathsf{AD}}z_{L}(w)\).

Using Theorems 3.2 and 3.5, we can efficiently determine whether the output of (reverse-mode) automatic differentiation is correct with respect to the standard derivative: if the second item in Theorem 3.5 holds, then the output is always incorrect (since the standard derivative should be \(\perp\)); otherwise, it is always correct (by Theorem 3.2).

We now sketch the proof of Theorem 3.3, to explain how we obtain the bound in the theorem and where we use the bias parameter condition. First, we prove that if \(y_{l,i}(w)\) does not touch any non-differentiable point of \(\sigma_{l,i}\) for all \((l,i)\in\mathsf{ldx}\), then \(z_{L}\) is differentiable at \(w\). In other words,

\[\mathsf{ndf}_{\Omega}(z_{L})\subseteq\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
## 4 Correctness of Automatic Differentiation for Neural Networks without Bias Parameters

In this section, we investigate the correctness of automatic differentiation for neural networks that may or may not have bias parameters. For such general networks, however, considering only the properties of activation functions such as \(\mathsf{ndf}\left(\sigma_{l,i}\right)\) (as we did in SS3) is insufficient to derive non-trivial bounds on the size of the incorrect and non-differentiable sets, as long as general pre-activation functions are used.

To illustrate this, consider neural networks \(z_{L},\widehat{z}_{L}:\mathbb{R}\to\mathbb{R}\) that are essentially the same as \(f,\widehat{f}:\mathbb{R}\to\mathbb{R}\) with \(f(w)=\mathrm{ReLU}(h(w))-\mathrm{ReLU}(-h(w))\) and \(\widehat{f}(w)=\mathrm{ReLU}(h(w))\), where \(h:\mathbb{R}\to\mathbb{R}\) is some analytic pre-activation function satisfying \(h(x)=0\) and \(Dh(x)=1\) for all \(x\in\mathbb{M}\). Suppose that \(D^{\mathsf{d}\mathsf{D}}\mathrm{ReLU}=\mathbf{1}_{(0,\infty)}\). Then, we have \(\mathsf{inc}_{\Omega}(z_{L})=\mathsf{ndf}_{\Omega}(\widehat{z}_{L})=\Omega\) even though \(z_{L}\) and \(\widehat{z}_{L}\) have only \(\leq 2\) non-differentiable points in their activation functions. The main culprit of having such large \(\mathsf{inc}_{\Omega}(z_{L})\) and \(\mathsf{ndf}_{\Omega}(\widehat{z}_{L})\), even with a tiny number of non-differentiable points in activation functions, is that \(z_{L}\) and \(\widehat{z}_{L}\) use the unrealistic pre-activation function \(h\) which does not have bias parameters.

To exclude such extreme cases and focus on realistic neural networks, we will often consider _well-structured biaffine_ pre-activation functions when they do not have bias parameters.

**Definition 4.1**.: A pre-activation function \(\tau_{l}:\mathbb{R}^{N_{l-1}}\times\mathbb{R}^{W_{l}}\to\mathbb{R}^{N_{l}}\) is _well-structured biaffine_ if there are \(M_{i}\in\mathbb{R}^{N_{l-1}\times W_{l}}\) and \(c_{i}\in\mathbb{R}\) for all \(i\in[N_{l}]\) such that \(\tau_{l,i}(x,u)=x^{\mathsf{T}}M_{i}u+c_{i}\) and each column of \(M_{i}\) has at most one non-zero entry.

We note that any fully-connected or convolution layer is well-structured biaffine if it does not have bias parameters. Thus, a large class of neural networks is still under our consideration even after we impose the above restriction.

We now present our results for neural networks possibly without bias parameters, extending Theorems 3.2-3.6.

### Bounds for Non-Differentiable and Incorrect Sets

We first bound the density of the non-differentiable and incorrect sets in \(\Omega\), extending Theorem 3.3.

**Theorem 4.2**.: _If a pre-activation function \(\tau_{l}\) has bias parameters or is well-structured biaffine for all \(l\in[L]\), then_

\[\frac{|\mathsf{ndf}_{\Omega}(z_{L})\cup\mathsf{inc}_{\Omega}(z_{L })|}{|\Omega|}\] \[\qquad\leq\frac{1}{|\mathbb{M}|}\sum_{(l,i)\in\mathsf{ldx}}\Bigl{|} \mathsf{ndf}(\sigma_{l,i})\cup\bigl{(}\mathsf{bdz}(\sigma_{l,i})\cap S_{l+1} \bigr{)}\Bigr{|},\]

_where \(\mathsf{bdz}(f)\) is the boundary of \(f\)'s zero set (see SS2.1), and_

\[S_{l}\triangleq\begin{cases}\emptyset&\text{ if }l>L\text{ or }\tau_{l}\text{ has bias parameters}\\ \mathbb{R}&\text{ otherwise}.\end{cases}\]

We note that if \(z_{L}\) has bias parameters, Theorem 4.2 reduces to Theorem 3.3 since \(\mathsf{inc}_{\Omega}(z_{L})=\emptyset\) (by Theorem 3.2) and \(S_{l}=\emptyset\) for all \(l\) (by its definition) in such a case.

As in Theorem 3.3, the bound in Theorem 4.2 is often small for neural networks that use practical activation functions, since \(|\mathsf{ndf}(\sigma_{l,i})\cup\mathsf{bdz}(\sigma_{l,i})|\) is typically small for those activation functions (e.g., \(1\) for \(\mathrm{ReLU}\) and \(2\) for \(\mathrm{HardSigmoid}\)).

We now show that the additional term \(\mathsf{bdz}(\sigma_{l,i})\) in Theorem 4.2 is indeed necessary by providing a matching lower bound up to a constant factor.

**Theorem 4.3**.: _For any \(\mathbb{M}\subseteq\mathbb{R}\) and \(n,\alpha\in\mathbb{N}\) with \(1\leq|\mathbb{M}|<\infty\), \(n\geq 4\), and \(\alpha\leq|\mathbb{M}|/(n-1)\), there is a neural network \(z_{L}:\mathbb{R}^{W}\to\mathbb{R}\) that satisfies_

\[\frac{|\mathsf{ndf}_{\Omega}(z_{L})|}{|\Omega|}\geq\frac{1}{9}\cdot\frac{1}{| \mathbb{M}|}\sum_{(l,i)\in\mathsf{ldx}}\Bigl{|}\mathsf{ndf}(\sigma_{l,i}) \cup\mathsf{bdz}(\sigma_{l,i})\Bigr{|}\]

_and the following: (i) \(\tau_{l}\) is well-structured biaffine without bias parameters for all \(l<L\), and has bias parameters for \(l=L\); (ii) \(z_{L}\) has \(n+1\) neurons; and (iii) \(|\mathsf{ndf}(\sigma_{1,i})|=\alpha\) and \(|\mathsf{bdz}(\sigma_{1,i})|=0\) for all \(i\). We obtain the same result for (i), (ii'), and (iii'): (ii') \(z_{L}\) has \(2n+1\) neurons; and (iii') \(|\mathsf{ndf}(\sigma_{1,i})|=0\) and \(|\mathsf{bdz}(\sigma_{1,i})|=\alpha\) for all \(i\)._

We next give an intuition for why the zero set of \(\sigma_{l,i}\) (from which the additional term \(\mathsf{bdz}(\sigma_{l,i})\) is defined) appears in Theorem 4.2, by examining its proof. The proof consists of two main parts that extend Eqs. (2) and (3) from the proof sketch of Theorem 3.3: we first show

\[\mathsf{ndf}_{\Omega}(z_{L})\cup\mathsf{inc}_{\Omega}(z_{L})\subseteq\bigcup_{ (l,i)\in\mathsf{ldx},\;c\in\mathsf{ndf}(\sigma_{l,i})}\{w\in\Omega\mid y_{l,i }(w)=c\}\]

and then find a reasonable bound on \(|\Lambda_{l,i,c}|\) for \(\Lambda_{l,i,c}\triangleq\{w\in\Omega\mid y_{l,i}(w)=c\}\), the set of parameters on which the pre-activation value \(y_{l,i}\) touches the non-differentiable point \(c\) of \(\sigma_{l,i}\). Among the two parts, the zero set of \(\sigma_{l,i}\) arises from the second part (i.e., bounding \(|\Lambda_{l,i,c}|\)), especially when \(\tau_{l}\) does not have bias parameters and is well-structured biaffine. For simplicity, assume that \(\tau_{l}\) is a fully-connected layer with constant biases, i.e., \(y_{l,i}(w)=\sum_{j\in[N_{l-1}]}z_{l-1,j}(w)\cdot w_{j+a}+b\) for some constants \(a,b\). Based on this, we decompose \(\Lambda_{l,i,c}\) into \(\Lambda^{\prime}\cup\Lambda^{\prime\prime}\):

\[\Lambda^{\prime} \triangleq\{w\in\Omega\mid y_{l,i}(w)=c,\;z_{l-1,j}(w)\neq 0\text{ for some }j\},\] \[\Lambda^{\prime\prime} \triangleq\{w\in\Omega\mid y_{l,i}(w)=c,\;z_{l-1,j}(w)=0\text{ for all }j\}.\]

Then, we can show \(|\Lambda^{\prime}|\leq|\mathbb{M}|^{W-1}\) as in Eq. (3), since \(w_{j+a}\) acts like a bias parameter of \(y_{l,i}\) for any \(j\) with \(z_{l-1,j}(w)\neq 0\). To bound \(|\Lambda^{\prime\prime}|\), however, we cannot apply a similar approach due to the lack of \(j\) with \(z_{l-1,j}(w)\neq 0\). Instead, we directly count the number of parameters \(w\in\Omega\) achieving \(z_{l-1,j}(w)=0\) for all \(j\) (i.e., \(\sigma_{l-1,j}(y_{l-1,j}(w))=0\) for all \(j\)), and this requires the zero set of \(\sigma_{l-1,j}\). For the full proofs of Theorems 4.2 and 4.3, see Appendices B and D.
### Bounds for the Incorrect Set

For the non-differentiable set, Theorems 4.2 and 4.3 provide tight bounds on its size. For the incorrect set, it turns out that we can further improve the upper bound in Theorem 4.2 and get a similar lower bound to Theorem 4.3.

**Theorem 4.4**.: _If a pre-activation function \(\tau_{l}\) has bias parameters or is well-structured biaffine for all \(l\in[L]\), then_

\[\frac{|\mathsf{inc}_{\Omega}(z_{L})|}{|\Omega|}\leq\frac{1}{|\mathbb{P}|} \sum_{(l,i)\in\mathsf{idx}}\Big{|}\big{(}\mathsf{ndf}(\sigma_{l,i})\cap S_{l} \big{)}\]

_where \(S_{l}\) is defined as in Theorem 4.2._

**Theorem 4.5**.: _For any \(\mathbb{M}\subseteq\mathbb{R}\) and \(n,\alpha\in\mathbb{N}\) with \(1\leq|\mathbb{M}|<\infty\), \(n\geq 4\), and \(\alpha\leq|\mathbb{M}|/(n-1)\), there is a neural network \(z_{L}:\mathbb{R}^{W}\to\mathbb{R}\) that satisfies_

\[\frac{|\mathsf{inc}_{\Omega}(z_{L})|}{|\Omega|}\geq\frac{1}{13}\cdot\frac{1}{ |\mathbb{P}|}\sum_{(l,i)\in\mathsf{idx}}\Big{|}\mathsf{ndf}(\sigma_{l,i})\cup \mathsf{bdz}(\sigma_{l,i})\Big{|}\]

_and the following: (i) \(\tau_{l}\) is well-structured biaffine without bias parameters for all \(l<L\), and has bias parameters for \(l=L\); (ii) \(z_{L}\) has \(2n+1\) neurons; and (iii) \(|\mathsf{ndf}(\sigma_{1,i})|=\alpha\) and \(|\mathsf{bdz}(\sigma_{1,i})|=0\) for all \(i\). We obtain the same result for (i), (ii'), and (iii'): (ii') \(z_{L}\) has \(3n+1\) neurons; and (iii') \(|\mathsf{ndf}(\sigma_{1,i})|=0\) and \(|\mathsf{bdz}(\sigma_{1,i})|=\alpha\) for all \(i\)._

We note that if \(z_{L}\) has bias parameters, Theorem 4.4 reduces to \(|\mathsf{inc}_{\Omega}(z_{L})|=0\) as in Theorem 3.2 since \(S_{l}=\emptyset\) for all \(l\) in the case. On the other hand, if \(z_{L}\) does not have bias parameters, then the incorrect set can be non-empty as discussed in SS3.1, and more importantly, its size can be bounded by Theorem 4.4. To see why the bounds on \(|\mathsf{inc}_{\Omega}(z_{L})|\) depend on both \(\mathsf{ndf}(\sigma_{l,i})\) and \(\mathsf{bdz}(\sigma_{l,i})\), refer to the proofs of Theorems 4.4 and 4.5 in Appendices C and D.

### Sufficient Conditions for Computing

Standard Derivatives and Clarke Subderivatives

We extend Theorems 3.5 and 3.6 to general neural networks without the well-structured biaffinity restriction, by characterizing two sufficient conditions on parameters under which automatic differentiation computes the standard derivative or a Clarke subderivative.

**Theorem 4.6**.: _Let \(w\in\mathbb{R}^{W}\). If \(y_{l,i}(w)\notin\mathsf{ndf}(\sigma_{l,i})\) for all \((l,i)\in\mathsf{ldx}\) such that \(\tau_{l}\) does not have bias parameters or \(\partial^{\mathsf{AD}}z_{L}/\partial z_{l,i}\neq\vec{0}\) at \(w\), then_

\[D^{\mathsf{AD}}z_{L}(w)=Dz_{L}(w)\neq\bot.\]

**Theorem 4.7**.: _Let \(w\in\mathbb{R}^{W}\) and assume that \(D^{\mathsf{AD}}\sigma_{l,i}\) is consistent for all \((l,i)\in\mathsf{ldx}\). If \(y_{l,i}(w)\notin\mathsf{ndf}(\sigma_{l,i})\) for all \((l,i)\in\mathsf{ldx}\) such that \(\tau_{l}\) does not have bias parameters, then_

\[D^{\mathsf{AD}}z_{L}(w)=\begin{cases}Dz_{L}(w)&\text{if }Dz_{L}(w)\neq\bot\\ \lim_{n\to\infty}Dz_{L}(w^{\prime}_{n})&\text{if }Dz_{L}(w)=\bot\\ \quad\text{for some }w^{\prime}_{n}\to w\end{cases}\]

_and so \(D^{\mathsf{AD}}z_{L}(w)\) is a Clarke subderivative of \(z_{L}\) at \(w\). Here \(\mathsf{ndf}(f)\) denotes the set of real numbers at which \(f:\mathbb{R}\to\mathbb{R}\) is not continuously differentiable._

The two sufficient conditions on \(w\) given in Theorems 4.6 and 4.7 are simple enough to be checked efficiently in practice, so that we can use them to validate whether the output of automatic differentiation is the standard derivative or a Clarke subderivative. If \(w\) does not satisfy either of the sufficient conditions, then automatic differentiation may not compute the standard derivative or a Clarke subderivative; the first example discussed in SS3.3 illustrates both cases. We remark that the sufficient condition in Theorem 4.7 involves \(\mathsf{ndf}(\sigma_{l,i})\) (not \(\mathsf{ndf}(\sigma_{l,i})\)), since we use continuous differentiability (not differentiability) in the proof to properly handle the limit of derivatives \(Dz_{L}(w^{\prime}_{n})\). For the proofs of Theorems 4.6 and 4.7, see Appendices E and F.

## 5 Conclusion and Discussion

In this paper, we study for the first time the correctness of automatic differentiation for neural networks with machine-representable parameters. In particular, we provide various theoretical results on the incorrect and non-differentiable sets of a neural network, as well as closely related questions such as when automatic differentiation is correct and what it computes. Our results have two major practical implications: automatic differentiation is correct at most machine-representable parameters when applied to neural networks, and it is correct more often if more layers of the network have bias parameters. Furthermore, our theoretical analyses suggest new applications of automatic differentiation for identifying differentiability and computing Clarke subderivatives, not only for machine-representable parameters but also for any real-valued ones.

Our results have some limitations. For example, all of our results are for a class of neural networks consisting of alternating analytic pre-activation functions and pointwise continuous activation functions. Hence, if a network contains non-pointwise activation functions (e.g., MaxPool) or a residual connection bypassing a non-analytic activation function (e.g., ReLU), then our results may not be directly applicable. Our results for general neural networks (e.g., Theorems 4.2 and 4.4) additionally assume pre-activation functions to have bias parameters or to be well-structured biaffine, which does not allow, e.g., BatchNorm without bias parameters. Nevertheless, we believe that our results still cover a large class of neural networks, especially compared to prior works studying theoretical aspects of neural networks (Jacot et al., 2018; Kidger and Lyons, 2020; Laurent and von Brecht, 2018; Lu et al., 2017; Park et al., 2021). We believe extending our work to more general neural networks is an interesting direction for future work.