What does automatic differentiation compute for neural networks?
Authors: Sejun Park
Sanghyuk Chun
Wonyeol Lee
Venue: ICLR 2024 spotlight (2024)
Keywords: automatic differentiation
correctness
neural networks
clarke subdifferential
Primary area: general machine learning (i.e., none of the above)

Abstract: Forward- or reverse-mode automatic differentiation (AD) is a popular algorithm for computing the derivative of a function expressed by a program. AD always outputs the correct derivative if a program does not use any non-differentiable functions and control flows; however, it may return an arbitrary value otherwise. In this work, we investigate what AD computes for neural networks that may contain non-differentiable functions such as ReLU and maxpools. We first prove that AD always returns a generalized derivative called a Clarke subderivative for networks with pointwise activation functions, if the minibatch size is one and all non-differentiable neurons have distinct bias parameters. We show that the same conclusion does not hold otherwise, but does hold under some mild sufficient conditions. We also prove similar results for more general networks that can use maxpools and bias parameters shared across different neurons. We empirically check our sufficient conditions over popular network architectures and observe that AD almost always computes a Clarke subderivative in practical learning setups.

Published as a conference paper at ICLR 2024
WHAT DOES AUTOMATIC DIFFERENTIATION COMPUTE FOR NEURAL NETWORKS?
Sejun Park Sanghyuk Chum
Wonyeol Lee
Korea University NAVER AT Lab
CCanegiee Mellon University
ABSTRACT
Forward- or reverse-mode automatic differentiation (AD) is a popular algorithm for computing the derivative of a function expressed by a program. AD always outputs the correct derivative if a program does not use any non-differentiable functions and control flows; however, it may return an arbitrary value otherwise. In this work, we investigate what AD computes for neural networks that may contain non-differentiable functions such as ReLU and maxpools. We first prove that AD always returns a generalized derivative called a Clarke subderivative for networks with pointwise activation functions, if the minibatch size is one and all non-differentiable neurons have distinct bias parameters. We show that the same conclusion does not hold otherwise, but does hold under some mild sufficient con- ditions. We also prove similar results for more general networks that can use max- pools and bias parameters shared across different neurons. We empirically check our sufficient conditions over popular network architectures and observe that AD almost always computes a Clarke subderivative in practical learning setups.
INTRODUCTION
Computing the derivative of function represented by program is fundamental task in machine learning as well as many other areas such as scientific computing (Baydin et al., 2017: Heath, 2018). Automatic differentiation is class of algorithms for this computation that based on the chain rule, and has two popular "modes" called the forward mode and reverse mode (Griewank and Walther, 2008). In particular, the reverse mode includes the backpropagation algorithm (Rumel- hart et al., 1986) as a special case and is implemented in diverse machine learning frameworks such as TensorFlow (Abadi al., 2016), PyTorch (Paszke et al., 2017), and JAX (Frostig et al., 2018). This paper studies these two modes of automatic differentiation. and we write them simply as AD.
The correctness of AD has been extensively studied for decades, especially with respect to the standard derivative. For program that consists of differentiable functions and no control flows (e.g., if-ele and while statements), AD is shown to compute the standard derivative of the function represented by the program for all inputs (Elliout, 201 8; Abadi and Plotkin, 2020; Brunel et al., 2020; Barthe et al., 2020; Huot et al., 2020; Vákár, 2021). If a program starts to use non-differentibble functions (c.g.. ReLU) or control flows. however, AD might not compute the standard derivative for some inputs (Kakade and Lec, 2018). Fortunately, even in this case, AD is shown to compute the standard derivative for most inputs under mild conditions which often hold in practice. For instance, Bolte and Pauwels (2020b); Lee et al. (2020); Mazza and Pagani (2021); Huot et al. (2023) proved that for all practically used programs, AD does not compute the standard derivative at most measure-zero (i.e., negligible) subset of all real-valued inputs. In addition, Lee et al. (2023) studied the density of such inputs over all machine--eprrssentabe (e.g., floating-point inputs, proving that it is close to zero for many neural networks while it can be close to one if a network uses too many non-differentiabee functions.
These correctness results show that AD computes the standard derivative at most inputs, yet often provide little information about what it computes at the remaining inputs. To better understand AD, several works have studied its correctness with respect to various notions of generalized derivatives, including the so-called Clarke subdifferential (Clarke, 1975). The Clarke subdifferential is one of the most traditional, widely-used generalized derivatives, which extends the subgradients of convex functions to non-convex functions and has been considered in several areas such as optimization
Equul contribution
Emails: (sejun.park000, sanghyuk.chun, wonyeol.lec.cs) gmmal..com

---

Published as a conference paper at ICLR 2024
Table I: A summary of correctness results of AD, with respect to the Clarke subdifferential. We put / in the last column if the output of AD is always in the Clarke subdifferential, and X otherwise.
Distinct bias params
Shared bias params
Minibatch of size one
Choice of proxy derivatives
Without maxpools
Always correct?
Reference
Lee et al. (2023)
Ours (Theorem 1)
Ours (Lemma 2)
X
Ours (Lemma 3)
X9
Ours (Theorem 4)
Ours (Theorem 6)
Ours (Lemma7 7)
X
AD uses either D p(z) or D* p(az) as the proxy derivative of pointwise activation function at æ, where D p and D* p denote the left-hand and right-hand derivatives of p.
TAD uses an element of the Clarke subdifferential as the proxy derivative of
AD uses TD p(x) + [1 x)D* p(x) as the proxy derivative of p E [0, 1] is shared in layer.
A sufficient condition for AD to correct at the current parameter/input values given in Theorem 5.
AA sufficient condition for AD to correct at the current parameter/input values is given in Theorem 8.
and control theory (Clarke, 1990; Clarke et al., 1998). Some classical results such as (Clarke, 1990, Chapter 2) and (Rockafellar and Wets, 1998, Chapter 10) showed that the Clarke subdifferential enjoys the (exact) chain rule for certain classes of functions, implying that AD always computes an element of the Clarke subdifferential when applied
program consisting of these functions.
More recently, Lee et al. (2023) directly showed that AD always computes element of the Clarke subdifferential when applied to a certain class of neural networks.
The previous results on AD and the Clarke subdifferential, however, are not applicable to many neural networks used practice, e.g., networks that use non-differentiable funetions (e.g.. ReLU and maxpools) together with convolution layers, some normalization layers (e.g.. Borchh residual connections, or minibatches of inputs (Lee et al., 2023; Davis et al., 2020). This limitation makes it still unelear what AD computes for practical neural networks especially with respect to the Clarke subdifferential. We remark that some recent works such as (Bolte and Pauwels, 2020a;b; Lee al., 2020; Huot et al., 2023) proved the correctness of AD over all inputs, with respect to fundamentally new notions of generalized derivatives (e.g., conservative or intensional derivatives); but they did not study how the output of AD is connected the Clarke subdifferential, an arguably more popular notion of generalized derivatives.
Contributions. In this paper, investigate what AD computes for neural networks in various problem setups. As in practice, we assume that for each non-differentiable function (e.g., ReLU), AD uses an element of its Clarke subdifferential as its "proxy derivative." In this setting, our first set of results is for neural networks with pointwise and analyyic activation functions (e.g., ReLU and HardSigmoid), which can summarized as follows.
Theorem I shows that AD always computes element of the Clarke subdifferential, if the minibatch size is one and non-differentiable neurons have distinct bias parameters. This generalizes the prior result in (Lee et al., 2023) which requires AD to use element of the Bouligand subdifferential! for activation functions under a similar setup.
Given this correctness result of AD with respect to the Clarke subdifferential, a natural question arises: does the same conclusion hold under non-trivial minibatch sizes or the absence of bias parameters? We prove this is not true. Lemmas and 3 show that if the minibatch size least two or bias parameters are absent, then AD can return value not in the Clarke subdifferential for some network, input, and parameter configuration.
Then, without distinct bias parameters and the trivial minibatch size, when does AD compute an element of the Clarke subdifferential? Theorem 4 shows that for networks with distinct bias parameters, AD always correct regardless of the minibatch size, as long as we choose proper
'The Bouligand subdifferential is subset of the Clarke subdifferential. See Section 2.1 for their definitions.
2

---

Published as a conference paper at ICLR 2024
proxy derivatives. For fully-connected networks that might not have distinct bias parameters, Theorem provides an easily verifiable sufficient condition for checking the correctness of AD.
We next consider more general networks that can have shared bias parameters (e.g., in convolu- tional layers) and maxpools (i.e., non-poontwise activation functions), under general minibatch sizes.
Theorem shows that for networks with shared bias parameters and no maxpools, AD always computes an element of the Clarke subdifferential as long as proper proxy derivatives are cho- sen. Namely, AD is correct with respect to the Clarke subdifferential for modern convolutional networks without maxpools. We also show that having shared bias parameters, maxpools, and proper proxy derivatives are all necessary for this correctness result (Lemmas 2, 3, and 7),
Theorem 8 provides sufficient condition for verifying the correctness of AD when networks can have maxpools. Using our conditions in Theorems 5 and 8, we empirically check what AD outputs for fully-connected and convolutional networks under practical learning setups. In our experiments, we observe that AD successfully returns an element of the Clarke subdifferential although the non-differentiable points of activation functions are often touched during training.
Organization. In Section 2, introduce notations and problem setup including the formal defini- tions of neural networks and AD. We present our main results on the correctness of AD for neural networks in Section 3. In Section 4, empirically verify sufficient conditions and check whether AD is correct under practical learning setups. We lastly conclude the paper in Section 5.
PROBLEM SETUP AND NOTATIONS
2.1 NOTATIONS
We first introduce the notations used in this paper. We use N and R to denote the set of positive integers and that of real numbers. For n N. we use 1n _ (L..... 1), O,, - (O.....0) 0) E R", [n] (1.....n). and we treat x E R" as column vector. For k. mı...... ... my E N and tensor ., is )-th coordinate of v. Under the same setup, 2/ o for E [k] denotes the (k ((--))-dingg -))dimmmsia tensor whose (a1, (a1..... ak-;)-th coordinate is Likewise, for n N, f R" Rm (oxxx..XM. Xma, and j E [k]. we use fig....ly R" + mm x.. xma to denote the function such that (f(z))
v E I Xmmm we use Vi...... to denote the (i,,...,
"i.......1..........
=fn.... fn...... .s (x) for all x E R", for j = k, we assume mj+1 X X mg = 1 by following the convention. For u = (ul...., um)) and (UI...., Un). u & (uI...., Mm U1..... Un) denotes the concatenation of and v. For matrix A E Raxm whose i-th column is a; E RR" vec(A) A) & a1 ① ... @ am denotes a vectorization of A. For k m., nn E N, and given Fi...... E R for all ij [ny] and j [7.], we write "ig....i
to denote the k-dimensional tensor whose (ii,..., ig. )-t coordinate is ..... ig is clear
: we often use [2t, from the context. We write Phn to denote the n-dimensional Lebesgue measure. We often use signs + and to denote +1 and -1 respectively; for example, for s = and x E IR, 8 2 is -I.
to denote this tensor when the range of ......,
Df(x) R= denote the Jacobian matrix of f at x. and use ndf C R" to denote the set of inputs at which f is not differentiable. For f R + IR and s E {-,+). we use D*f(a) lim,- Df(v). Given locally Lipschitz / R + R. the Bouligand subdifferential of f at x E R" (Cui and Pang, 2021) is
For f: RD Rm and x R² at which is differentiable,
8 f()()) A { f&e E Feg U2,... E RR. " (nd((f] such that o - x and (f(v)) + +))
The Clarke subdifferential of locally Lipschitz f at E R" (Clarke, 1990) is defined the convex hull of 8 fzx), which we denote by d fx)) By definition, we always have 8 f(x) C Cff((x).
2.2 NEURAL NETWORKS
We define neural network follows. Given the number of layers L N. let No N be the dimension of input data, M,, N₁ E N be the dimensions of intermediate vectors at layer E [L]. Wi N be the number of parameters at layer I [L]. and W & W1 + Wz. Further, given the minibatch size B E N. and for each E [L]. let Ti : IR No x x ... x N, ιx x W + M be an analytic pre-activation function and MRM
IR be continuous activation function.
3

---

Published as a conference paper at ICLR 2024
We also use é NN. + R denote analytic loss function that maps the last layer's output to a scalar-valued loss. In this setup, we consider a neural network as a function of model parameters.
Specifically, given an input minibatch X E IR NoxB of size B, neural network (:; R is defined recursively as follows: zo w: X) _ X, and for all 1 E [T]].
R
(ww;)) A {(EL (w; X)), <(w;;] X) A of ()) so(w; X) - ==(20-11 X), wi) (1)
where (w; X) - (z;; x)...., 2n (w; X)), - wn @ (B... @ wi, and wi _ (wr.1,,... wi,w; E RW: Since the input minibatch X is fixed while we compute the derivative of v with respect to w, we often omit X and use (w)), 2 (w), and y (w) denote (w; X), <1w;; X). and yr X).
.....;
We mainly focus on two classes of neural networks, where the first class is characterized as follows. Definition 1. A function f R + R is preccewise-anlltie
if f is continuous and there exist n E N. a partition [Ai]ie(m) of IR consisting of intervals with μ (A.) > 0 for all i, and analytic functions {fr ER- + Rheeen) (x) such that f fs on for all i E [n].
Condition 1. A neural network V satisfies M1- for all E [L], and
<,, wx) = fi(E, un) or fi(x, ui) + b
=1((a1)baa)= (po
where wi uy or wt = @ by for some by E 12 fi is an analytic function, and pt R - R is piecewise-analytie function for all 1 E [L]. We say the network has "distinct bias parameters" if
(2, wi) = fi u)) + b, B for all I E [L] with non -on-differnttiale pt-
Here, by denotes vector of N₁ bias parameters, where each bt, is used in computing the i-th row of 't's output (i.e., the i-th neuron). The neural networks satisfying Condition 1 cover a wide range of practical network architectures. For example, if ft(2u:11. u² 2 where uy is vectorization of some A, E N 1. then it represents a fully-connected layer. Likewise, fi in Condition can represent attention layers (Vaswani al., 2017), normalization layers (e.g.. one-dimensional BatchNorm, and LayerNorm) (loffe and Szegedy, 2015; Ba et al., 2016), and their compositions. It can also express residual connections (He et al., 2016) as fi takes all previous activation tensors 214-1. In addition, Condition I allows any pointwise and piccewise-analytic activation functions such as ReLU and HardSigmoid. Thus, Condition 1 covers not only simple neural networks such as fully-connected ones but also complex network architectures such as transformer-base ones.
Although Condition can express a large class of practical networks, it cannot represent modern convolutional neural networks. For example, convolutional networks often have single bias pa- rameter that is shared across multiple neurons in the same channel, whereas Condition does not allow such "shared" bias parameters. In addition, Condition does not allow non-pointwise activa- tion functions such as MaxPool2d. To cover these exceptional cases, we introduce Condition 2. Definition 2. A function f : R" + R. is a "maxpool" if there exist II..... Imm C [n2] such that f(r
max.,..... max X3 iET1
TT..
Condition 2. A neural network Vi satisfies
C
T( wi) = f((I, u) or f((x, ui) + Σ Ai
(((aadl = ((((((())
where C. E N, wi = un or ui = ii $ by for some by = (bI,,,.., b,)c)) ERC. ALe E 10,13 M for all c E [Ct), fi is an analytic function, Pt : IR + R is riecewise-analyte function, and
oi M + R N is a maxpool for all E [L]. We say the network & has "shared bias parameters" " if EC = 1 for all E [L.] with non-differentiable pt- We say the network V "has only trivial maxpools" if Φi is an identity map for all I E [Z].
Condition 2 allows shared bias parameters (which are used in, c.g., convolutional layers and two- dimensional BatchNorm): bn denotes vector of Ct bias parameters, where each by used in computing the (i. k)hthh output of 7 (i.e., the i-th neuron for the k-th input) whenever (Ar.)). = 1. Further, Condition also allows non-pointwise activation functions (e.g., a composition of ReLU and MaxPool2d). Hence, it covers modern convolutional neural networks which often use nor- malization layers, maxpools, and residual connections. We note that Condition with only trivial maxpools is generalization of Condition I: consider the case that Mr N; C₁, A e.1 g= and di is an identity map for all / E LL] and e e [Ci], where e, denotes the c-th standard basis of RC, Also, having shared bias parameters is generalization of having distinct bias parameters.
4

---

Published as a conference paper at ICLR 2024
2.3 AUTOMATIC DIFFERENTIATION
Automatic differentiation is a class of algorithmss for computing the derivative of function (rep- resented by a program) based the chain rule, and it has two popular modes: forward mode and reverse mode. In this paper, AD refers to these two modes of automatic differentiation. Given a neural network y defined by Eq. (1) and an input minibatch E R-NoxB AD essentially computes
( (X) RRW + +R
by applying the chain rule of differentiation to Eq. (1). other words, for neural networks satisfying Condition 1 (or Condition 2), DAD is defined as the product of Dr and D p: (and D max,), where max, denotes the max function over RR", and DAD pt and DAD max, denote the "proxy gradi- ents" of and max, that AD uses in its computation. Here, the proxy gradients are necessary since Pt and max, are not differentiable in general, i.e., their (standard) derivatives might not exist at some points. We assume D p( E 0 (z) for all R. which implies D pi(x) = Dpi for all æ & ndf(pp)) since pt is piecewise-anaa analytic (see Lemma 9). We also assume D max, (z) é e, such that max,, (a:) Tj, and e; denotes the i-th standard basis
for all IR", where depends of Rpn? Many AD systems, including TensorFlow and PyTorch, fulfill these two assumptions for all one-dimensional
anallye functions and all maxpool functions that are implemented in the systems. The formal expression of D for neural networks V/ can be found in Appendix B.
Throughout the paper, we say AD is "correct with respect the Clarke subdifferential" (or simply, "correct") for a network V, an input X, and parameters w if ( X) E 8 (w;X). X). For a fixed V, we say AD is "always correct" if it correct for all X and w.
3 MAIN RESULTS
We are now ready to present our main results on the correctness of AD for neural networks, which consider various setups: the presence of bias parameters, the choice of the minibatch size, the choice of the proxy gradients used by AD, and the presence of maxpools. We first introduce our analyses on neural networks satisfying Condition I in Section 3.1. We then move to neural networks satisfying Condition 2 in Section 3.2. The proof's of all results in this section are given in Appendices D and E, and discussions on our theoretical results are provided in Sections H-J.
3.1 CORRECTNESS OF AD FOR NEURAL NETWORKS SATISFYING CONDITION
Our first result is about the correctness of AD for neural networks satisfying Condition especially when there are distinct bias parameters and the minibatch size is one.
Theorem 1. Let y E {B, c} and Ve be a network satisfying Condition 1 with distinct bias param- efers. Suppose that DAD pi(x) 8 pz()) for all 1 E [L] and x E ndf(pi). Then, DA (w: X) (w: X) for all w E RW and X E R NoxB with =
Theorem states that if network vi has distinct bias parameters and the minibatch size is one, then AD computes an element of the Clarke (or Bouligand) subdifferential of V as long the proxy gradient D Pr (xx) ( is an element of the Clarke (or Bouligand) subdifferential for all and x. In other words. AD is always correct in this case. This result extends the previous correctness result in (Lee et al., 2023), which states that AD computes an element of the Clarke subdifferential under a stronger setup: A pr(x)) d p (a))) and V has residual connections; result considers more general proxy gradients DAD (c(x)) E p()) and allows residual connections.
To prove Theorem 1 when ? B, we explicitly find sequence Th 72,... of parameters that converges to w such that V is differentiable on the sequence and (Mm),, (12))..... converges utilize bias parameters. (w)), i.e D (w)) E 8 (w.). To construct such sequence,
First, observe that D (x) E 0 pp((()) implies D (w). = D pi (w)) for some 81,5 E {-.+} for all e [L] and
[M] since B 1; here, we choose $t $1,5' if (t,(ww) = (w). Then, we can find a sequence of bias parameters that converges to b,, from the left/ight side depending on 81,5, while fixing non-bias parameters (i.e., u²) this leads us to the statement of Theorem 1. Using the result for y B, we can also prove the case for y C. We note that
Thii assumption implies TD (a) (z)) E 8 max, for all E R.
5

---

Published as a conference paper at ICLR 2024
similar strategies are used to prove other correctness results in this paper that consider networks with (distinet/shared) bias parameters (Theorems 4 and 6). See Section D.1 for the detailed proof.
Given the correctness of AD under the presence of distinct bias parameters and B = 1, natural question arises: are both conditions necessary? The following lemmas answer this by showing that both are indeed necessary for AD to be always correct; these lemmas based on the incompatibil- ity of the Clarke subdifferential with addition (Clarke et al., 1998; Kakade and Lee, 2018).
Lemma 2. There exists network y satisfying Condition I without distinct bias parameters such that DAD (()) E JP (x(x) for all I E [L] and x E (d)( but D TV (ww; X) & (W; X) for some
E TR and X E IR NoxB with B 1.
Lemma 3. There exists a network Ve satisfying Condition I with distinct bias parameters such that DADD pi(x) E 8 pilx)) for all I. E [T]] and x E ndf(pi), but DAD X) 8f (W; X) for some W E TR W and XXE E TR NoxB with B 2. 2.
Lemmas 2 and 3 show the existence of (i) network V satisfying Condition I without distinct bias parameters (respectively, with distinct bias parameters), (ii) an input minibatch X of size B = (respectively, of size B 2 2), and (iii) a parameter configuration w, for which AD does not return an element of the Clarke subdifferential. In other words, AD can be incorrect in general if B 2 2 or distinct bias parameters are absent.
Given these negative results, we may ask the following: is it impossible to have correct AD under more general setups? Our next result shows that if network has distinct bias parameters, proper choice of proxy gradients is sufficient for AD to be always correct, regardless of the minibatch size.
Theorem 4. Let Yi be network satisfying Condition 1 with distinct bias parameters. Suppose that p1 pDDpp(aa
+ (1 Dx) pi(z), for all I E [L] and x (pf( Then, DAD (w; X) E 88 (w; X) for all E RWW, B E N, and X RRNOBB" Further, if xi....,,.. do
there exist AI....,>,, E [0, 1] such that px(t) = >D
E {0, 13, then (A X) E O (w;; X) for all B, and X.
Here, D and D denote the left- and hhan derivatives (see Section 2.1 for formal definitions). Theorem 4 states that if the proxy gradient DAD Pr (ar) is a convex combination of the left- and right- hand derivatives of Pt with the same weight N for all E (pr), then AD is always correct for networks satisfying Condition I with distinct bias parameters, regardless of the minibatch size. For example, if pt has a single non-differeentiabl point 2 E R (c.g.. 2 0 for ReLU and LeakyReLU), then choosing AD (z) E 8. p,)()) (2) is sufficient for satisfying this condition. If Ind((pi) 2 2 as in RcLU6 and HardSigmoid, then choosing D pz))
D ((x)) for all x E (df (simi- larly, DAD (z) D* (z()) for all x E ndf(p)) )) is sufficient to ensure the condition; we note that our counterexample Lemma does not satisfy this condition (see Section D.3). Therefore, the condition in Theorem 4 can be easily fulfilled by choosing proper proxy gradients of AD.
We next provide a sufficient condition for the correctness of AD under general minibatch size and the (possible) absence of distinct bias parameters. For now, we focus on fully-connected networks; a result for general networks can be found in Theorem 8 in Section 3.2.
Theorem 5. Let 7 E {B, C} and VP be neural network satisfying Condition 1. Suppose that (= w/) = A or A + b for some A₁ E TR. NeN-L1 with wi = vec(Ar) or wy = Aec(AA)) @ by. and D (z))) E 8 pz))) for all I E [L] and E ndf(pi). Then, for any E R
B E N, and X E N we have DAP (w; X) E (w; X) if the columns of 2-1(w; X) are linearly independent whenever (,w,,(w; X) E ndf for some I E [L], i E [Ni). and b E [B].
For fully-connected networks, Theorem 5 shows that the correctness of AD is guaranteed if the column vectors of 3-1(w;; X) are linearly independent whenever y1 (www; X) touches any non- differentiable point of the activation function Pt. If the input and hidden dimensions ,,...., are larger than the minibatch size B (which often occurs in practical learning setups), this condition can be casily satisfied; we empirically demonstrate this in Section 4.
Unlike Theorems 1 and 4, a fully fulle-connected network considered in Theorem 5 might not have dis- tinct bias parameters. Hence, to prove the thcorem for y = B, we construct a sequence Th, T2. of parameters that converges to w, by varying only the non-bias parameters (i.e., Ad that (ML)), DVB (1z).... converges to D Here, the linear independence of the columns in 2 X) guarantees the existence of such a sequence. See Section D.5 for more details.
'ReLU6(>)) è min min 6) and HardSigmoid و min(max //6 1/2), 1).

---

CORRECTNESS OF AD FOR NEURAL NETWORKS SATISFYING CONDITION 2 Published as a conference paper at ICLR 2024
Algorithm Construction Pt
1: Input: I: the index of the target layer, 20:-11: the outputs of the o,.... (1 1)-th layers, wi: the parameters of the 1, I-th layers, (N) the index sets used by the maxpool function Φ1 at the (-th layer.
2: Initialize: P: <- RW;
3: for E [M]] x [B] do
4: Vi Th. 77. 22: wi). 02 + Pr(vs), 0y./dut
5: if yı E ndf then
6: Choose 8; (- such that DAD DAP pt(ss) D De pi(r))
7: P P: n {I E IR
(Te, x) > 0}
8: end if
9: end for
10: for j E [N]] [B] do
11:
S₁ < argmaxiez,
12:
ir 2 2 then
13:
i* f the index in S that AD uses when computing DAd DaPmax(aaiiie
14:
T₁ <- (i E Sj= @MD u;./ /8wn. = 800 (0,00/001s))
15:
Pi < Pin E (DM
x) > (DAPpi(us) m),a) for E Sj (T))
16: end if
17:
end for
18:
return Pi
3.2
In the previous subsection, we focused on networks satisfying Condition 1, and studied when AD is (always) correct or not by varying various setups such as the presence of bias parameters, the size of minibatch, and the choice of the proxy gradients used by AD. In this subsection, we analyze the correctness of AD for neural networks satisfying Condition (e.g.. convolutional neural networks), which is generalization of Condition 1, under general minibatch size B E N. To this end, we first introduce the following theorem for networks with shared bias parameters and trivial maxpools.
Theorem 6. Let & be a network satisfying Condition 2 with shared bias parameters and only trivial maxpools. Suppose that there exist ,1,..., E [0, 1] such that D p((x) = >2 pi(z) + (1 D*) pı(z) for all 1 E [L] and E ndf( Then, D (ww; X) E 8 (w; X) for all w E RW
B E and X E RNxx Further, if A1,..., E {0, 1}, then (w X) E 8 (w;; X) for all w WER' B E N, and X E Rox.
Theorem 6 is generalization of Theorem 4: it ensures the correctness of AD over all inputs and parameters (under a proper choice of DAP as long as a network satisfying Condition 2 has shared bias parameters and only trivial maxpools all layers. Many modern convolutional neural networks without maxpools satisfy the conditions in Theorem 6: e.g., MobileNet V3 (Howard et al., 2019), RexNet (Han al., 2021), and ConvNext (Liu et al., 2022). Namely, AD is always correct for those networks although they contain non con-differentiable activation functions.
Since Condition is a generalization of Condition 1, choosing a proper D and having bias parameters are necessary for Theorem 6 as we observed in Section 3.1 (see Lemmas 2 and 3). Given the necessity these conditions, our next result examines the only remaining condition in Theorem 6, which is about having only trivial maxpools.
Lemma 7. There exists a network V satisfying Condition with shared bias parameters and non- trivial maxpools such that DAD pr(x)) D pr(x) (1) for all I E [L] and ndf(pi), but DAP (w; X) & go X) for some w E W B E N, and X N
Lemma 7 shows that AD can be incorrect with non-trivia trivial maxpools. However, practical networks, especially convolutional networks, often include them. To examine the correctness of AD for such networks in practice, we provide a generic sufficient condition that guarantees correct AD.
Theorem 8. Let y be a network satisfying Condition Suppose that A p1(x) pp)((z) for all E [L] and x E (df( Then, for any E R,W, B E N, and X E Nox it holds that ( X) (W X)) if + 0 for all I [L] where Pi denotes the output of Algorithm 1.
4g00 ou / denotes the partial derivative of o with respect was that reverse-mode AD computes.
7

---

Published as a conference paper at ICLR 2024
To describe the main intuition behind Pl, we first consider the case when each T, in Algorithm has only a single element t". In this case, Pi satisfies the following property; for any Ç E Pi and small enough > 0, the activation function or is differentiable at 7(200-1 (w), wy + E(t) and
Do (01(12001-140) wi +EGi) D or (7(220-1(ww) mi)) as 0.
(2)
where DAD denotes the proxy derivative of o, used by AD (see Appendix B for its formal defini- tion). Due to this property, whenever Pi is not empty for all ( E [L], we can construct a sequence of parameters for showing (w) E (w)) as in the proof of Theorem 1. To construct Pa satisfying Eq. (2), Algorithm adds constraints to Pi in Lines 3-9 and 10-17, which ensure
Dpr (T.L0(=N-- (w), wr + +Gi) + D pr (
w.))
as + 0 and
(3)
Dot ((((((2 (w),, wi + +(()) + D ( (P((T)((0o wi)) as - 0
(4)
for all i E [Ni] and b E [B]: and Eqs. (3) and (4) immediately imply Eq. (2). Here, D40 Φi denotes the proxy derivative of Φi used by AD, which is induced by D max, (defined in Section 2.3).
Now, we consider the remaining case when Tj has at least two elements. In this case, Eq. (4) might not hold, Yet, even without Eq. (4), we can still find a sequence of parameters 7) 7/,.... E RW such that Yn + w and DV + DAD (w) as n + xX, using the definition of Tj (Line 14): 0AD ar. 10w1. = 8dh a for all i E Ty. See Section E.3 for detailed arguments.
To verify the sufficient condition in Theorem 8, one needs to check whether Pi is empty or not, where P:- = {ar RWW (aL,1, x) > 0 for all i E [K]]] for some al,,,.... dT,4 E g.. (which are deseribed in Algorithm 1). To check this, one can solve the following linear programming: find (c, E IR x R th such that maximizes c subject to (ar,s, x) 2 c for all E [Mx]. Then, the solution c of this problem is strictly positive if and only if Pi is not empty.
4 EXPERIMENTS
We use the sufficient conditions in Theorems 5 and 8 to verify whether AD is correct in two practical leamning scenarios. In the first scenario, we consider fully-connected networks with distinct bias parameters that do not satisfy the conditions in Theorems 1 and 4. In the second one, we use convolutional networks with shared bias parameters that do not satisfy the conditions in Theorem 6.
Scenario 1: Fully-connected networks. We consider three fully-connected networks with two hidden layers and hidden dimensions of N₁ = 256 and N₂ = 64, where each network uses one of ReL.U6. Hard'Tanh, and HardSigmoid as its non-differentiabbe activation function. We trained these networks on the MNIST dataset (LeCun et al., 2010) using stochastic gradient descent (SGD) with the minibatch size B = 128, where each gradient was computed via (reverse-mode) AD im- plemented in Py Torch. All networks were trained for 20 epochs with the initial learning rate 0.05 and the weight decay 0.0001, where the learning rate was decayed by the cosine annealing schedul- ing (Loshchilov and Hutter, 2017). We note that all the activation functions in these networks (i.e., Pt E (ReLU6, HardTaanh, HardSigmoid)) have exactly two non-differentiable points, and Py- Torch uses the following as their proxy gradients: A (x) = 0 for all x E (df( Due to this, there is no \ E [0, 1] satisfying DAD p( = A ((()) + (1 A pt(z) for all E ndf():). i.c. these networks do not satisfy the conditions in Theorems I and 4.
During the training, we checked if AD is correct by verifying the sufficient condition in Theo- rem 5, i.e., whether the activation matrix ( E NN has full column rank whenever any con-differentiable point of Pt touched. We ran five experiments for each network, and observed that all the parameter values E RW taken over all training steps (469 /epoch x 20 epoch) satisfied the sufficient condition. This observation and Theorem imply that in our experiments, AD returned an element of the Clarke subdifferential at all training steps, even though the non- differentiable points of activation functions were touched for the following number of times in each training (averaged over five runs): 0, 9.8, and 13.8 times for networks using ReLU6, HardTanh, and HardSigmoid, respectively.
Scenario 2: Convolutional networks with maxpools. We next evaluate the correctness of AD for three convolutional networks with non con-trivial maxpools: VGG11 (Simonyan and Zisserman, 2015); VGG11 with BatchNorm (VGG11-BN) which adds the BatchNorm operation after each
8

---

Published as a conference paper at ICLR 2024
Table 2: Statistics related Sj and S T.. The total number of max, operations in VGG11 and VGG11-BN per each layer (with non-trivial maxpool) is 1,048,576/ 524,288 262, 144 / 131,072 32,768. ResNet has 2,095, 140 max, operations in the first layer. The total number of training steps is 7,820 for all networks. All the below values are averaged over five independent runs.
Ratio of max
# training steps with S, T; *
Average [S, TT
Network
when S T of Correct?
with | 2 2 (%)
3.2/ / x00 1.7x10 /0
1435.8/ 166.3 / 44.0/ 18.0/0
1.18/ 1.04 1.00/ 1.00/ NA
VGGI1
VGGI1-BN
0.07 -.100.0/445x1099 /
3668.5 / /9.0/
1.46/ 1.09/ 1.01/ 1.02/1000
/
4.2x10 /355x10
42.0/
ResNer18 4.2
3904.8
1.78
convolution operation in VGG11; and ResNet18 (He al., 2016). In VGG11 and VGG11-BN, five layers have non-trivial maxpools, and in ResNet18, only the first layer has a non-trivial maxpool. In these networks, ReLU is the only pointwise non-differentiable activation function, and Py PyTorch uses (0) 0 as its proxy gradient at zero. To reduce the computational overhead, we halved the channel dimensions of VGG11 and VGG11-BN. We trained these networks on the CIFAR-10 dataset (Krizhevsky et al., 2009) using AD-based SGD with the same settings described above.
During the training, we checked if the parameter values w at each training step satisfy the sufficient condition in Theorem 8. To construct the set P, in Theorem 8, we used Algorithm 2 in Section F, which is identical to Algorithm for networks that have shared bias parameters and use ReL.U (with ReI 0) as the only non-differentiable Pt. The major difference between Algorithms and 2 is that Algorithm 2 adds constraints to Pi only when a tie occurs at some max, operation in maxpools, and it does not care whether any input to ReLU touches zero not. In these experiments, we observed that the sufficient condition in Theorem was always satisfied, implying that AD always returned an element of the Clarke subdifferential.
To better understand the results, we measured three additional quantities. The first one is the number of events that a tie occurs some max,, i.e., |Sy] 2 2 in Algorithm 2. We counted the number of such events over all max, operations in each layer (with a non-trivial maxpool), and divided by the total number of max, operations in that layer, which we denote by "ratio of max, with |S 2 2." As summarized in Table 2, we observed that this ratio is not negligible (c.g., 2 3% for the first layer). This because, for some max,, operation, the image patches corresponding to the receptive fields of its inputs are often identical (see Section G for concrete examples); for such a max, operation, tie always occurs regardless of the parameter values w.
To exclude such trivial cases and examine non-trivial ties in max, operations, we also measured the number of training steps where |S, \ (Tyl 2 1, and the average size of S₁ \T, when [S, T > 1, both per each layer with a non-trivial maxpool. As shown in Table 2, the event that |S, \ T 2 1 (i.e., non-trivial ties exist) occurred frequently during training: e.g., in VGGII, this event happened in the first layer at 1435.8 steps (on average) among the total of 7,820 training steps. We also observed that the size of S \ Tú was typically one or two, implying that Pt was non-empty very easily.
5 CONCLUSION
In this paper, we study the correctness of AD for neural networks. We first show that AD is always correct for networks satisfying Condition if they have distinct bias parameters and the minibatch size is one (Theorem 1). While AD may not be always correct if one of the conditions in Theorem violated (Lemmas 2 and 3), we prove that having proper proxy derivatives ensures AD to be correct again for general minibatch sizes (Theorem 4), under the presence of distinct bias parameters. For general fully-connected networks that may not have distinct bias parameters, we provide a sufficient condition for checking the correctness of AD (Theorem 5), which often holds in practical learning setups. We also prove similar results for a more general class of networks that can have shared bias parameters and maxpools (Theorem 6 and Lemma 7), and provide a generic sufficient condition as well (Theorem 8), which often holds in the training of practical convolutional networks (Section 4). We believe results and analyses would contribute to better understanding of AD.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
SP was supported by Institute of Information communications Technology Planning & Eval- uation (IITP) grant funded by the Korea government (MSIT) (No. 2019:0-00079, Artificial In- telligence Graduate School Program, Korea University) and Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2022RIF1 (10761800.
REFERENCES
Martín Abadi and Gordon D. Plotkin. A simple differentiable programming language. Proceedings of the ACM on Programming Languages, 4(P0PL))3811338.28,, 2020.
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek Gordon Murray, Benoit Steiner, Paul A. Tucker, Vijay Va- sudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: A system for large-scale machine learning. In Symposium on Operating Systems Design and Implementation (OSDI), pages 265-283, 2016.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv:1607.06453 2016.
arXiv preprint
Gilles Barthe, Raphaëlle Crubillé, Ugo Dal Lago, and Francesco Gavazzo. On the versatility of open logical relations continuity, automatic differentiation, and containment theorem. In European Symposium on Programming (ESOP), pages 56-83, 2020.
Atilmm Güneş Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: survey. Journal of Machine Learning Research, 18:153:1-153:43, 2017.
David Bertoin, Jérôme Bolte, Sébastien Gerchinovitz, and Edouard Pauwels. Numerical influence of ReLU on backpropagation. In Annual Conference on Neural Information Processing Systems (NeurIPS), pages 468-479, 2021. URL https://arxix: wwwpriiw.w..oooooooooooooooooore wwtp///gg////////////..///eee/// abs/2106 12915.
Jéröme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning. Mathematical Programming, 19-51, 2020a.
Jérôme Bolte and Edouard Pauwels. mathematical model for automatic differentiation machine learning. In Annual Conference Neural Information Processing Systems (NeurIPS), pages 10809-10819, 2020b.
Etienne Boursier. Loucas Pillaud-Vivisn and Nicolas Flammarion. Gradient flow dynamics of shal- low relu networks for square loss and orthogonal inputs. In Annual Conference on Neural Infor- mation Processing Systems (NeurIPS), 2022.
Alois Brunel, Damiano Mazza, and Michele Pagani. Backpropagation in the simply typed lambda- calculus with linear negation. Proceedings of the ACM on Programming Languages, 4(POPL)) 64:1-64:27, 2020.
Francis H. Clarke, Yuri S. Ledyaev, Ronald Stern, and Peter R. Wolenski. Nonsmooth analysis and control theory. Graduate Texts in Mathematics: Volume 178, Springer Science & Business Media, 1998.
Frank H. Clarke. Generalized gradients and applications. Transactions of the American Mathemat- ical Society, 205:247-262. 1975.
Frank Н. Clarke. Optimization and nonsmooth analysis. Classics in Applied Mathematics: Vol- ume 5. SIAM, 1990.
Ying Cui and Jong-Shi Pang. Modern nonconvex nondirentlle optiiizaton... MOS- SIAM Series on Optimization. SIAM, 2021.
10

---

Published as a conference paper at ICLR 2024
Damek Davis, Dmitriy Drusvyatskiy, Sham M. Kakade, and Jason D. Lee. Stochastic subgradient method converges on tame functions. Foundations of Computational Mathematics, 20(1):119- 154, 2020.
Conal Elliott. The simple essence of automatic differentiation. Proceedings of the ACM on Pro- gramming Languages, 2(ICP)):0:11770:2) 2018.
Roy Frostig, Matthew Johnson, and Chris Leary. Compiling machine learning programs via high- level tracing. In SysML Conference, 2018.
Andreas Griewank and Andrea Walther. Evaluating derivatives: Principles and techniques of algo- rithmic differentiation. SIAM, 2nd edition, 2008
Dongyoon Han, Sangdoo Yun, Byeongho Heo, and YoungJoon Yoo. Rethinking channel dimensions for efficient model design. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
Michael T. Heath. Scientific Computing. SIAM, 2nd edition, 2018.
Andrew Howard, Mark Sandler, Grace Chu, Liang-Chich Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for MobileNetV3. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2019.
Mathicu Huot, Sam Staton, and Matthijs Vákár. Correctness of automatic differentiation via diffe- ologies and categorical gluing. In International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), pages 319-338, 2020.
Mathicu Huot, Alexander K. Lew, Vikash K. Mansinghka, and Sam Staton. wPAP spaces: Rea- soning denotationally about higher-order, recursive probabilistic and diffcrentiable programs. In Symposium Logic in Computer Science (LICS), 2023.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), pages 448-456. pmlr, 2015.
Sham M. Kakade and Jason D. Lee. Provably correct automatic sub-differentiatiin for qualified programs. In Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7125-7135, 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [On- line]. Available: http://yann..e http://ynn.lecuu.comm fecum.com/exd//mmist. 2, 2010.
Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongseok Yang. On correctness of automatic differ- entiation for non-differentiable functions. In Anmual Conference on Neural Information Process- ing Systems (NeurIPS), pages 6719 2020.
Wonyeol Lee, Sejun Park, and Alex Aiken. On the correctness of automatic differentiation for neural networks with muchine-representtine parameters. In International Conference on Machine Learning (ICML), pages 19094-19140, 2023.
Zhuang Liu, Hanzi Mao, Chao- Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. convnet for the 2020s. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastie gradient descent with warm restarts. In Interna- tional Conference on Learning Representations (ICLR), 2017.
Damiano Mazza and Michele Pagani. Automatic differentiation in PCF. Proceedings of the ACM Programming Languages, 5(POPL))28:1128812 2021.

---

Published as a conference paper at ICLR 2024
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In NIPS Autodiff Workshop, 2017.
R. Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, Series of Comprehensive Studies in Mathematics: Volume 317. Springer Science & Business Media, 1998.
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back-propagating errors. Nature, 323(6088):533-555 1986.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference Learning Representations (ICLR), 2015.
Matthijs Vákár. Reverse AD at higher types: Pure, principled and denotationally correct. In Euro- pean Symposium on Programming (ESOP), pages 607-634, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Annual Conference on Neural Information Processing Systems (NeurIPS), 2017.
12

---

Published as a conference paper at ICLR 2024
A ADDITIONAL NOTATIONS AND DEFINITIONS
For n, m E N, we use Oaxm (respectively, 1xx) to denote the matrix consisting of zeros (respec-
tively, ones) of size n x m. For R, define
(or +)
if x > x = 0 if æ < 0.
sign(x) -
-1
(or
For S C R. we use iS) to denote the interior of S. For S C R" (or a set S of functions from In to )",, we use cSnv(S) to denote the convex hull of S: conv(S) (E C K c, 2 0, E S with ΣiE[K] C: = 1}.
For a piecewise-analytic function f R - R with a partition {Atkeeal and a E R, we use a +) to denote A, for some [n] such that (I, x + E) C A, for some e > 0. Likewise, we use P( to denote A; for some i E [n] such that (xr - s,x) C A; for some > 0. For a differentiable function f : R" x .... x R" - R and x; E R for all i E [k], we use D.f Ikk to denote the derivative of f with respect the i-th argument in (#1s..., i..., (f /x2/0z; E R
We say that function R" + R is "differentiable maxpool" if it is maxpool with [[] |mm| = 1 in Definition 2. that is, f(11...... .1f2.....,,,, In) We note that trivial maxpool is always differentiable maxpool.
= (z.,....; Din)) for some .1,..., Im E [n].
B AUTOMATIC DIFFERENTIATION FOR NEURAL NETWORKS
Given a neural network V. its parameters E RW, and input minibatch X R the output of AD DA (w;; X) can be written by the following recursive relationship that involves DAD (w: X) E NR-Nxx and DAD DAP (w; X) E RMxxBx for I E [L). [N), E [M],
and E [B].
D v7 w:; X) A
Σ
(De(zL(w; x))) 2D 21 (w;
())xx))).. 2.8 ERW.
(EE , |x [B]
(DAP 211;; X)),b
Σ
X))) i.bar.o (DAD x)) jrM E RRW.
(M X
(D v((; X))
Σ
Σ
(Dite (zolu;
- X)...., X) wi)) wil)e 10DDz((u X)) 2
RE 1) (1 (E
Σ
(Dinss((zo(w; X); . (w; X), wz)) eW.+.....IHH ER
VE[W
where e; denotes the i-th standard basis of R Here, (x) E Nx is defined as follows for all x E Mi B, when the network v satisfies Condition 1, we use
A DD (x
if c) (i,b) if (f + (i,b),
and when T satisfies Condition 2, we use
DDD (I
if (j.c) Cii if (j. c) + (Ji,s c.,))
(D (DLO(()))
where (Ji c. argmax
Dy.e' denotes the index that AD uses for the proxy gradient of (ox)), b MR + IR (i.c., the maxpool in the 1-th layer restricted to its (i, 6)-th output) and Ia, C
[M. x [B] denotes the set of indices that (di),, uses (i.e., di uses to compute its (i, b) output). We
note that the above definition of D (w: X) depends on the choice of proxy gradients A pi R
R. Whenever want to make this dependency explicit, will write D (D (De (w; X)
to denote DAD (w, X).
13

---

Published as a conference paper at ICLR 2024
C TECHNICAL LEMMAS FOR MAIN PROOFS
Lemma 9. Let f R - R be a piecewise-analyic function and x E R. Then, f is differentiable at if and only if f is continuously differentiable f.
Proof of Lemma 9. We only prove that if f is differentiable at then f is continuously differen- tiable at z, since the converse is trivial. Suppose that f is differentiable at æ. Then, by the defi- nition of piecewise-analyticcn (Definition 1), there exist analytic functions f+ IR - R and < x. such that f f- on (a, and f = f on (z, b). Since f is differentiable at x and f are analytic over I. we have
lim Df(z)= lim Df (z) Df (x), 2-
lim Df(=) lim ( +-x
2-
:-x (z)- Df
Df lim (2)) = Df(x) 2-
f+
lim
--
_-
z
Here, the second and third equalities in the second line above follow from ʃ being differentiable at I. This implies that is continuously differentiable at æ.
Lemma 10. For any open O P. analytic and non-constant f : + R, and O, there exists 8 > 0 such that
f() & c,,
Furthermore, is strictly monotone on [z. E and strictly monotone on 2, 2/. In particular, Df()) > (or Df(x) < 0), then f is strictly increasing (or strictly decreasing) on [st - 6, 1 +e.
Proof of Lemma 10. Without loss of generality, suppose that f(x) Since f is analytic, f infinitely differentiable and can be represented by the Taylor series on (x 5, x + 5) for some 8 > 0 as follows:
(0) (z x2) on (x o, +
f(z)
=
20 i!
where f(t) denotes the i-th derivative of f. Since f is non-constant, there exists i E N such that (x) * O. Let i* the minimum such Then, by the Taylor's theorem,
(z) 141
f(z)
(z - x) + +ol2= z((") on (x 6, + 5).
(5)
We now consider the case that ((() > 0 and is odd. By Eq. (5) and the analyticity of ʃ. we can choose E 60, that
(i) f(z)
E, x) and f(z) > on (x, x and
(i)) f(() (2) > 0 on [x - e, te.
Then, by (i), f() & f(x - f1
{x}). Furthermore, we claim that ff is strictly monotone on [x and [z, x + By (ii). the analyticity of f. the mean value theorem, and by our assumption
that (x) for all < i", holds that
-
)) (z)
(ar e,x) and (0)
Again, by the same reasoning, we have
g( 2) (z) > on (z 10-a, 2.)) and 2 (2) on (z, + +
By repeating this process, implying that is strictly monotone on [x - e, xr) and [z, x +o-+2 +
show that (2) > on x)) and (2)) on (x,
By applying similar arguments, can also show that the above claim (i.c., f(x) f([x E, + <l\ (a+) and ff is strictly monotone on [xt fx-e, x:) and [x, + for some > 0) holds in the remaining cases: (x)) < 0 and is odd; fx(")()) > and i" is even; and (()) < and i' even. This completes the proof of Lemma 10.
14

---

Published as a conference paper at ICLR 2024
Lemma 11. Ler fi, f2 R - R be functions, p R. be piecewise-onalltic funcciiii and & E R. Let p(z) E p()) for all x E ndf(p). Suppose that
(i) for each i {1.2). if f((z) E (p), then Ddd p(fa(z)) D*ip(f((z)) for some E {- and 8; Dz,(z) > holds; and
-f (f)(2)) D p(f(z)) Df2(2). (ii) p(f((2) 2 p(2(z)) and D DAD p(f((z))
Then, it holds that
lim sign ()((((((z - p(f2(z +c))) = 5-0++
Proof Lemma 11. If f1(2) nd) then sign(D)((2)) 8: E (-,+) by (i), so Sa is non-
constant. Therefore, by Lemma 10, we have
lim -
f((x)) = 8i.
(6)
and this implies that
DAD p(f((z)
DD' DI(()) (po fi)(2),
where the first equality is by (i) and the second equality is by the piecewise-analyicity of p. the chain rule, and Eq. (6). If fz) & ndf(p), then is easy observe that
DAD 1Ad p(f((z)) (2) = Dp(fi(z)) Df.(z) = D(p o fa)()) = (po
where the first equality is by the assumption that DAD D(0p(t)) E p()( and the second equality is by the chain rule. Hence, by (ii), we have
DAD (()(()) Dz((2) DAP ((f(2))) Df2(2) ( - po po f2)()) o. This implies that for any small enough E 0,
[[J((= (((i(=+
+ E)) - ,(f((z) /12(2= ([((=+)))) - -
+ sign
sign(p(/i ((((==) Ml(== + p(f((z)))
sign(p(fi + +(f((=+e))) +E))),
where the last equality uses the assumption p(fi(z)) 2 p(f((z)) in (ii). Therefore, we have lim sign(p(f((z+e)) p(f2(= ++))) =
+
and this completes the proof.
Lemma 12. Let
a network satisfying Condition 2, and consider w E RW,, B E N. R N B For each 1 E [L]. let $1 E {- all (j', ()) [M] [B]. For each I [L] and (i, E [Ni]] x [B].
[M] X [B] be the of indices that (di)). uses (i.e., (u,((w)) max (w))) (i', b'' I1,,p) for all w' E BRW); ); let (H4 v1,..) E I1, be the index that AD uses when computing D () (see Ap- pendix B for details); and let Ji. C. II,b \ {pu,,. v1,i,)).
let InND
Here, (pr.s. vL...) and Jis depend on w which is fixed in this lemma. For each I E [L]. let No (G',6') E [M]] x [BB] W (w)) ndd( Suppose that we are given S1 E RW, ,..,, such that for all [L] and (i,b) [NI] [B).
........ SL E R
lim sign Te. (20.- wr + ECI) - T.. (w), wi) = 3133.0
8 ++
for all (i',b') EN, + eG)) (T (20.-1(w), wi + sci)) = for all (j" ""," E Ti,
(7)
lim sign e-o+
(8)
Then, there exists sequence (meN R such that for each 1 [T.) and (i, [Ni] [B].
15

---

Published as a conference paper at ICLR 2024
oon ?n Ow, a (w + ma) (pp yu sn v.) for all (i,b)) E [Mi] x [B] and n E N, and
M (w + mn)) > pi vo v<(w m,)) for all (j", .²) E It and n E N.
Here, P(f.x,+) and P(f,x, x,,, were defined in Appendix A.
Proof of Lemma 12. Without loss of generality, suppose that ||Gll2 1 for all [L]. By Eqs. (7) and (8), we can choose .1....,ō1 > 0 such that for all / E [L) (i. E [Nd x [B. Mi.
and (i","" E Tiii
sigu (T. (w): wy + =Gt) Ti ( wz) sI,',,,
(9)
p (T.psssi
wy + EGi)) p (r + EGi)
(10)
for all E E (0, 61). Without loss of generality, we assume òi...., dr also satisfy the following: for all I [Z] and ()' [M]] x [B]
Th, ( (w)), wi + EÇI) E int (llps y1 (w), $1., s..
(11)
for all e E (0, 61). We can always find such small enough ò1 ......, dr from Eq. (9), the continuity of 7r, and (P(r,, 3 (w), s1. > (which holds by the piecewise-analltiitt pt and Definition 1).
We now claim that there exists {n MnEN C R W such that for any n E N, l E [L], and (1,b) [N]] x [B].
(i) 1mmll22 S VInn.
(ii) W + mm) E int(P(pt, u st,, for all (),b) E [M] x [B], (ii) P (w + va)) > pi(y1,5" v (w + mn)) for all (j", b") Ji,s,b
Then, {na) In is desired sequence. To show the existence of such (1/m Jns construct (),,))met C RW for each & [L] such that for any N, [L] [L 1t), and (i, [Ni] [B].
k-(i) (Mn,k)) = 0 for all I E [Wi + .... - WT-M),
k--(i) [|m,,kl12 S vk/(nL),
k-(ii) 11.5, + k) E (Ptt B s) for all (i', b) E [M] x [B]. k-(iv) p(y.masse (w + (n,,)))) > pr (w m,,))) for all (j", b²) E Ti
Then, choosing 7hs = 1n.L completes the proof.
We construct such ( Jn by induction k. Consider the base case: 1. For each n. choose 7m.1 = Ow +......WW. - + (EnSI) for en = 2 [I(m)]). Then, Th, satisfies I-((i)..., (iv)} by Eqs. (10) and (11) and by our choice of 7h,1 and En. Now, consider a general k > 1. By the induction hypothesis on h 1, there exists {M,,6-1h, satisfying (k- 1)-((i)...... (fv))- For each n, we choose 7n,k 1-. + OW,+...4w some e'n > 0 so that 7n.6 satisfies k- k-((),, ..., (iv)). Such ex always exists as follows: for any c x11 /1/(L))) 70, satisfies
(--+))))1) ① Ow:- for
k-((i), (ii) and k-i(i (iv)) for L +
This is because 7n.A-1 satisfies (I: 1)-((i), (ii)} and Eqs. (10) and (11) hold. Furthermore, for
a small enough E > O, Nn,k satisfies l- ((ii,, (iv)} for all I > L k + 1, since 7J, satisfies
(k- 16-11 1)-(( (iv)) and Te, oy continuous for all L. This completes the proof of Lemma 12. IT
16

---

Published as a conference paper at ICLR 2024
Lemma 13. Let V be neural network satisfying Condition with only trivial (or differentiable) maxpools, w E IRW, B E 18, and X E INNoX.. For every E [L]. let {Ar be a partition Suppose that for each I [T], j E [M]) and [B], there exists
of (r described in Definition k E [nu] such that V.,..b X)) in,( Then, ( is differentiable at w (i.e., (w; exists) and (ww X) DD (w)
Proof of Lemma 13. By Definition the condition ( X) int((Arx) implies that pi is dif- ferentiable at yt,j, (w;; X) for all J, 6. Since oi uses trivial (or differentiable) maxpool, is dif- ferentiable at y1 (w;; X) for all I. Moreover, TÜ is differentiable on its domain for all I by Condition 2. Hence, ( ; X) is differentiable at w by the definition of Tp and the chain rule for differentiation. Further, we have (w: x) D T (w; X) by the definition of DAP (Appendix B) and by the chain rule with Dp (p((M)s)(u) = D pi (i()) for all L,j,b.
Lemma 14. Let VY be neural network satisfying Condition 2. Consider any I E [L], E RWW and X E RN Then, for any fi,..., fi........ SL ftlb...,,
R + I, and for any K E N, R, and c IR with C1 + +CK we have
DAD (t eiaaait f2) 10 (w;
Σ c,D (i Je (w; X). (E(K)
Proof of Lemma 14. This follows from the definition of AD (Appendix B). We omit the proof as uses simple induction over the definition of D (w; X). We remark that the condition + сx- = is essential: this lemma no longer holds without the condition.
Lemma 15. Let be a neural network satisfying Condition 2, K1,..., K2 E EN and ft,k R R for all I [L] and & E [Ki]. Let g [gg....., (L) Ii (ft1,..., ft,K Y for all 1 [L]]. Then,
for any (h,,..., h2) such that hy E conv([ft....... fL, for all l E [L), it holds that
D (w; X) E conv( TV X): :9 E 9)).
Proof of Lemma 15. We show the following claim using induction (hi...., ht) satisfies that h E (fn.((f......fiikkk for all S n and hi E (f. fi,K } for
for all E [4]. if h
all l n, then
DAD (w; (w: X) E conv(1 v (w: X) g g)).
Then, the desired statement follows from the case for =
The base case (i.e., when n 1) follows directly from Lemma 14 with / 1= 1. Consider general case (i.e., when n 2 2) and h = (h1,-. hy.)) such that by E conv([Ji.,,...... fi,K, for all I I n and h E {fi......, fi,K,} for all > Let Eg (hI,..., h, hnt1, h2) for all E [K,]. Then, by the induction hypothesis on n 1, we have
DM X) E conv (w: X) g))
for all & E [K,]. Since h, E con.((ff.......... }), the definition of h and Lemma 14 imply D (w; X) conv(1 v (w;; (w; h E [K]]]) C conv(ID,"v (w;; Xw; X): : G}).
This completes the proof of Lemma 15.
17

---

Published as a conference paper at ICLR 2024
D PROOFS OF RESULTS IN SECTION 3.1
D.1 PROOF OF THEOREM
Fix W E RW, B I, and X R8xxBB
Case 7 = B. First, choose 81 E (-,+} for each / E [L] and i E [Ni] so that
DaD (r()n,(w)) = D (((,,,((),
(12)
Such 81,; always exists as we assumed DAD pr(1:) E (;:)(a)) for all E ndf and is piecewise- analytic. Let 81 ($1,1..... SI,N,). and let Ç Ow, & (s1,1,....) SI,N,, E RW; for all I E [L], i.e, the coordinates corresponding to the bias parameters in (i have non-zero values s1,1. 81,N1 Then, one can observe that
lim sign (= wy + EÇI) 7 71 wi) = St c-0+
for all E [L]. Then, by Lemma 12, there exists {n C. R such that for all E [L] and i [Ni],
(i) The - Ow - oo and (ii) yt. + mm) int((((t, (t, for all n E N.
From these, holds that
DV + mm) ( mm.) (ww)
-> 00.
(13)
Here, the existence of the first term (i.e., V is differentiable at wo + +m)) and the first equality are both by Lemma 13 and (ii), and the convergence is by the definition of A (Appendix B), Eq. (12), and (i). By combining Eq. (13) and (i), we have D E (w)) as desired.
Case 7 C. Let ndf(pt) far,i,..., LLA for all E [L], and let T [I each / E [4] and t T with & (f1....,tt)) and + we define h1, fi,. 12 - 1R
For
(Dp((z) (DWp
i (df(
hx(x) DAD p((x),
fi,(2))
if = 31,1-
Then, the assumption A pi(x) E of (zx) implies that for all / E [4] and e R.
(Dp((z) D pr(x) + (1- +t
if & nd if Zi
hx(z)=
for some λτ, E [0, 1). From this, one can observe that
hn E conv((Ji, 1 E T)) for all / E [4].
Using this observation, we can derive the desired conclusion:
(w)) DAP (e (w)
E conv (f DAD (s.....g.) (w) gi E :.i::E for all / E [4]})
C conv (anv((((w))) (w)),,
where the first inclusion is by Lemma 15, and the second inclusion follows from the fact that D (gn .g.......) (w) 8 (w)) for any Ii {fi, and our proof for the previous case 7 = B). This completes the proof of Theorem 1.
T (which holds by fi.(2)) 8 (x))
D.2 PROOF OF LEMMA 2
Consider neural network v defined as follows:
= L 1, No = 1, N, = 2, and W, =
NoXB
R 4: IR NB is defined as (X, wi) (Xw,, -Xwn).
18

---

Published as a conference paper at ICLR 2024
P1 IR + is defined as P1 ReLU with D (0) = 0.
RR x + is defined as ((21, x2)) = 21 22.
Then, y is expressed as (w; X) E(o,,
w1 R, X E R. and 01 = P1). Moreover, V satisfies Condition 1 without distinct bias parameters, and D Pi E p (x) for all ndf {0). We now consider X 1. Then, for all w1 R,
(T (x, w1 ())) where
V (w; ) (eLU(w)) ReI. ReI.U(-w)) w1,,
so 8 (0; X*) (1}. However, D (O; X*) & (0; X*). This completes the proof of Lemma 2.
D.3 PROOF OF LEMMA 3
Consider neural network V defined as follows:
= 2, N, Nı = 1, and W1 =
T1 TR:RRooe Noxx R R N is defined as (X, w1) X W1.
P1 P1:R. + defined as P1 = HardSigmoid with D p1 (-33) = DnD p0 (3) = (see Footnote
for the definition of HardSigmoid),
L: N + R is defined as ((11, = + 22.
Then, V expressed (w; X) ((a) (Ti (X, wn ))), where wi RR X E R2, and 0n (P1, p1). Moreover, li satisfies Condition with distinct bias parameters, and D (z) E 08
for all x E ndf(p1) = 3.3 We now consider X (3, -3). Then, for all w1 E.
(w; X*) HardSigmoid(3 + w1) + HardSigmoid(-33 w1) w /6 Lemma 3.
so (0; = {1/6). However, DAP X*) = 0 & a (0: X*). This completes the proof of
D.4 PROOF OF THEBREM 4
Theorem 4 special case of Theorem 6, and the proofs of the theorems are almost identical. Hence, we omit the proof of Theorem 4; the proof of Theorem can be found in Section E.
D.5 PROOF OF THEOREM 5
Fix E IW, B e N, and X E R. For each 1 [L], le = (1. E [N]] x [B] m..((w) (df(pp))) We note that by the assumption. M₁ * implies (ank(2)11(w)) B for any
Case 7 B. First, we choose 81,i, E [-,+} for each [7] and (i,b) E [N]] x [B] such that
D DA pi(L.,,, D ((()).
if (i. E EM:
(14)
we can choose an arbitrary 81,., E (-,+) (e.g.. 81,ib = +) if (1, & Nr. Such 81,i always exists since DAD (AP pr()) p()((z) = 0 ((x)) for all E ndf(pt) (by the assumption) and since o is piccowise-analytic. We then choose PI, E 1lxN--1 for each / E [4] and E [Ni] such that
P1 (w) = [sc,,]]
if
(15)
we can choose an arbitrary stt, if Mi 0. Such Pt, always exists since Ni * implies rank(((-1(w)) B noted above.
Next, let &; E IR N: be matrix whose i-th row is sPLs- Also, let G = vec( if the 1-th layer does not have bias parameters, and G vec((;) @ Ov, otherwise. Then, by Eq. (15),
( [5,, for all E [L] with NG + 0.
(16)
Under this setup, we claim that for all E [L] and (i, Ai.
lim sign T...0 un + =GI - T2,.6(20:11 w())) wi) = S1,i.b-
(17)
-1
19

---

Published as a conference paper at ICLR 2024
This claim holds as follows: for any 7 [L] with Ni o 0, if the I-th layer has bias parameters, then
T1, 20--1 (w), (w)) wy + E() 77,t, (00-1(ww), wi)
Ti,ib (201-1 (w)) (vec( Ar) @ bi) (((vec(F1))))) @ 0x.)) 72.. (20. (w)))((w): vec(Ar) e eb)))
TTiib 20:1-1 (w), vec( + + + bi) 72,1 200-1(w), vec(Ai) @ 0bb1)
((4) + +b) (A12)-1(0) + bi)
= -c.1 = (31,,,)
where the first and third equalities are by the assumption, and the last equality is by Eq. (16). We can use similar argument to prove the case when the 1-th layer does not have bias parameters.
Finally, by Lemma 12 applied Eq. (17), there exists {nan R& such that for each [4].
i [N.], and E [B],
(i) 7h - Ow as + co and (ii) (w + mn) (Pt((((p,, (1,,,, s1,1,)) for all n E N.
From these, holds that
DV + Vn.)) = (ww + Thn) (ww)
->
(18)
Here, the existence of the first term (i.e., v is differentiable at w + m7)) and the first equality are both by Lemma 13 and (ii), and the convergence is by the definition of A (Appendix B), Eq. (14), and (i). By combining Eq. (18) and (i), we have DA (w) E (w)((w) as desired.
Case y = C. The proof for this case is identical to the proof Theorem for the same case, except that now rely the proof for the case = B in this theorem (not in Theorem 1). This completes the proof of Theorem 5.
20

---

Published as a conference paper at ICLR 2024
E PROOFS OF RESULTS IN SECTION 3.2
E. PROOF OF THEOREM
Since all maxpools trivial, have Ni Mj for all 7.
Case ,1,..., År. E I. Let 81 = if X = and + if X 0 for all / E [4]. Let
- Ow- (s)lc,) for all I [4]. Then, can observe that
lim sign (T(2O-- (w), wi + =() - m=<zat-(ww) wi)) st N 6-0++
for all E [7.. Then, by Lemma 12, there exists {mh) C IR. such that for each I E [Z], E [Ni]. and E [B).
(i) Th - Ow + oo and (i) M1, + mn) E (P((,,, (w)) 91)) for all n E N.
By Lemma 13, (ii), the definition of (w))(w) and by D P: D pr. have DV +m)) D (w-+ +m)) + D (w) as n - oo (for a more detailed argument, refer to Eq. (13) and the text below that). From this and (i), it holds that ( (w))
Case , dL E [0, Fort = .t) E + let ft (fi.e...,, fi,) where
let
f(,(2) = Dp((a))
i & ndf(pi)
(((p)()))
if E ndf(pi)
for all E [L]. Also, let (/1....,hL) with h1 = DAD pt. By the assumption, we know that (Dpi(z) (ND (1- p(()) if E ndf(pi)
if & ndf(pi)
DAD p(())
for some À E [0, 1]. From this, we can observe that hy E conv(lfi. :t {-,+}=] for all I E [L]. From this, we obtain the desired conclusion:
(w=) = (ww) E conv ( (().....))) (w)) : on E ( (-,+)²) for all / e (Z]])
S conv (w)) (ww),
where the first inclusion is by Lemma 15 and the second inclusion is by the observation that DAD Do gg.)) (w) E 8 (w)) for any 9i (fu, E {-++} (which follows from fi,
{D Pr, D+ pt} and our proof for the previous case). This completes the proof of Theorem 6.
E.2 PROOF OF LEMMA
Consider neural network V defined follows:
B = I. 1, N₂ = 1, M, = 4, N₁ = 2, and W, = IR M is defined as (X, (u1, b2)) (Xu1 bi, bi, Xou bı, bz). Pi : - + is the identity function.
R.. NoxB R
RN is defined as Φ1 (I) x2, #3, (max² 22)) maxe (za, x44), where AD uses A maxz(11, I2) = (1,0) for all xy 22 (i.e., AD uses the first index of
di
X
max; the two inputs are identical).
R:RN N + R is defined as ((211, x22) =
Then, V expressed ((;; X) f(o1 (Ti (X, (u,, b1)))), where w (u1, E² and R. Moreover, Ve satisfies Condition with shared bias parameters and non-trivial maxpools, and A
p1 DA (x) D Pi (x) for all E ndf(p1) V. We now consider X" Then, for all (ui,bi) R2,
(w; X*) maxfus + b, b,} max(-u: + bb, b1} U1,
so ( (0; = ((1,)). However, D 0): (()) = (2,0) & (V(((, This completes the proof of Lemma
21

---

Published as a conference paper at ICLR 2024
E.3 PROOF OF THEOREM 8
In this proof, we write Ti Tj. and Sj appearing in Algorithm 1 as T1, Ti. and St. to make their dependency on E [T] explicit. Consider any w E RRW. B E N, and X E IR No Suppose that Pi + 0 for all E [r]. Let
Mi ((', E [M] x [B] ( ndf((r))
for each 1 E [L] as in the statement of Lemma 12.
Step 1. We choose Şi E Pt for each I E [L], and choose st.r E {-, for each / [Z] and ('' E [M]] x [B] such that
DdD pr(nn (w)) D pelmn (w)).
(19)
First, we claim that for each / [4] and ()) E Nr.
lim sign --
(2on-1(w), wi + EÇI) Thy (ww)- ui)) =s,,"
(20)
To prove this, fix I E [L] and ()' E Nr. and define a function Se.j.. R - R as s1.))((())
=
Tiy (20:-1 (w), wr + EQ).. Then,
sign sign / (0)) = sign (( (( (wo))1(w),
wi), (())
( (i)) sL (21)
where "1,3'88 corresponds to Tyss in Algorithm (as noted above), the second equality is by Line in Algorithm and the last equality is by Lines 6-7 in Algorithm G Pt, and Eq. (19). This implies that fi is non-constant analytic function (since D fug. (0) # 0). Hence, we can apply Lemma 10 fijy o and this yields Eq. (20).
Next, we claim that for all l E [L] (i. b) E [M] X [B]. and (i',b" E It,ib \ Tr.s.b.
lim sign p (T. ( (w), wy + =()) PI(T (20d-1 + ECi))) = (22) 8-0+
where pLi. V1,ib; Ii. are defined as in Lemma 12 and Ti.. corresponds to Tr.s in Algorithm (as noted above). To show this, fix 1 E [Z] and (i, E [Ni] [B). Then, Eq. (22) clearly holds for all (i',8) E Irii SLib by Line 11 in Algorithm I and the continuity of pt and nT where St.. corresponds to S. in the algorithm (as noted above). Also, we immediately obtain Eq, (22) for the remaining (j",8') (i.e., (f',8) E St,Lb Tr,,,) by applying Lemma 11 to Pt. ft. and fi.j..r. Here, Lemma 11 is applicable because: the condition (i) of the lemma follows from Eqs. (19) and (21), and the condition (ii) of the lemma follows from the definition of 14,i,, Pl,ib Eq. (21), and Line 15 in Algorithm 1.
Finally, by applying Lemma 12 Eqs. (20) and (22), obtain the following: there exists quence (MnJnEn C R such that for each E [L] and (i, E [Ni] x [B].
(i) lim Th2 Ow.
(ii) ( n.) E int(P((t, yy (w), sty())) for all (J' E [M] x [B] and N, and (ii)) pi (w + na)) > p (w +.)) for all (J' 8') I.i Ti.L and E N.
Let E' be collection of all sequences 3 C IR W that satisfy (i)iiii). Then, El is not empty since {mm Jm E
Step 2. We first consider an easy case. That is, suppose that there is a sequence (7 E g satisfying the following: for each I, i, b, there exists an index (Hi..: v(..s) E Ti.i such that
arg max P dr (w +x)) (vi....r ((,s) for all N.
(23)
G ('
We remark that (Ki, (t can be different from (Mi,i.d M...)).
Then, it holds that
DwW + w/h) ( v/h) AT
-
(24)
22

---

Published as a conference paper at ICLR 2024
The equality is by (ii) and Lemma 13. Here, the lemma is applicable because for each n. v is identical to a network with only differentiable maxpools, on some open neighborhood of w + m/ this follows from the existence of ( (( The convergence in the above equation follows from the definition of DA (see Appendix B), (i)-(ii), Eq. (23), and two observations: for all 1, b,
D ( DAD pi Pi (w))
for all (J', (') E [Mi] [B),
OND pilyn,y ((w)) 2ND pt (()
for (J', 8) = (Hi, ((,i,) and
Owia
Swra
(j" 8") (11,i, (2,i,))
where the first equality is by the definition of $1, (see Eq. (19)) and the second equality is by (H,,, (,,)), (HU,L,, Ml,,,)) E Ti.s,b and the definition of Ti,i (see Line 14 of Algorithm 1). From Eq. (24) and (i), we obtain the desired conclusion: D ( E (w)).
Step 3. We now consider general case. That is, we no longer make the assumption considered in
Step 2. For any E [L] and (i,b) [Ni] x [B], we define the function GI.,b IR 2
( A arg max pr ( +)), G (
where 2-4
denotes the powerset of set A.
Step 3-1. First, we claim that there a sequence {1% E E' such that for any 1,
(.,,o(hh)) Gras((m)) for all n, m E N.
(25)
Such sequence always exists as follows: take any {fn} E E' and let Hr (Gr,, (fm H1,i I1 2 2 then some element in (Na),, must appear infinitely many times in H. because II.,, 2 is a finite set while H is indexed over an infinite set, hence, we can choose a de- sired Jn as a subsequence of }i Without loss of generality, we assume that )n has the minimum value of Σ1,, 19,,,, over all sequences in E' satisfying Eq. (25).
Step 3-2. Next, we claim that there is a subsequence {n" In of {n/m), satisfying the following: for each n E N. there exists an open neighborhood O% of w + 7/2 such that
pr(an.y' sr (-)) pe(Mn.s" (-) on O"
(26)
for any b, and ("',"), ."" E Gr, Gr.., (11).. We prove this claim by contradiction.
Suppose that there is no such subsequence. Then, there should exist subsequence {m of (v/ some 1", i", b", and (j*), b"),, (i" b"") E Gi-,ir,b (n/) such that:
Pt- (Mr- (u-(u-rrraar(())) # pt (VI- 5"m, be (.)
(27)
on any open neighborhood of w + vi for all and
pr u + mh)) > pr(Vi.s" (w + m)))
(28)
for all n, (f',V) E (r),) and (j",8") E Irib \. (rr((1)) We can show this by ap- plying a similar argument used above (to show Eq. (25)), to the fact that i,, 8.j"" j""," 8") : 1, 1,i,b, b, and (j', b', ,"" E Eqs. (27) and (28), we can construct another sequence (ni Jn such that still belongs to El and
(
} is a finite set. By perturbing {n little bit and using
Py (" (w + mr"")) & pr- (Me """.b" (w + n)))),
(29)
Pi (w + )) > pr(Mn."" (ar (w n)²)),
(30)
for all n, 1,i,b, 15',8) E G.,oo(f), and b"" Ir.so \ G,,.or)). Further, by applying the same argument used to show Eq. (25), we can take a subsequence {n= Ja of (n +1 hn so that satisfies Eq. (25). Then, one observe that (nt""),.
h. E E' and
Σ G 5,6
1.5.b
because 191-,0 s- (n) }1 < 10- (nf)) (by Eq. (29)) and (G.,,(( - 19,s001) for all Lii,b (by Eq. (30)). This contradicts to our assumption: {n/ Jn has the minimum value of Enao (77,((1111 over all sequences in 8' satisfying Eq. (25). Hence, there should exist subse- quence (n/ of (n satisfying Eq. (26).
23

---

Published as a conference paper at ICLR 2024
Step 3-3. Lastly, show the desired conclusion based the sequence {%%1 which satisfies (ii- and Eq. (26). To do so, claim that for each N. there exists a network v with only differentiable maxpools such that V = V and D = DAP both on some open neighborhood of w + 7/ Such network L exists because the fact that (v, O%) satisfies Eq. (26) implies that we can replace all the non-trivial maxpools in by differentiable maxpools without changing the
value of y and D on O": here, we use the fact that if fi....,fff................ 91... ................................ .9. A + R satisfy
f(()) = f+(() > g5(-) on for all i,'' then maxp+g (..
max1 (.f(.) on for
any (and max, is a differentiable maxpool).
Given the existence of Vn. we can show the following:
D (w + m = TT (w + m = (W + -/- + (w))
as oc.
(31)
The first equality is by (ii) and Lemma 13 applied to Vn, where the lemma applicable because V uses only differentiable maxpools; the second equality is by D D y some neighbor- hood of w + nn The convergence in the above equation follows from the definition of D (see Appendix B), (ii- the definition of G1,s,b, and two observations: for all n, L,
D pi(M (w)) = DAD Pe (W (w))
for all ()' E [M] x [B], for all (j', b) E Gr.,(1") and (j",
OAD pi OAD pi
Owna
Owia
(HI,),. (1,,6))
where the first equality is by the definition of 81.5",8 & (see Step 1), and the second equality is by (1,,(("") S TTii, (which follows from (iii), (Hl,i,b, (1,i,)) E TT,ii,, and the definition of Tr,s,b (see Line 14 of Algorithm 1). From Eq. (31) and the fact that v = L some open neighborhood of w + "/" V also differentiable on that neighborhood and DVD(w + v/() = DV oc. From this and (i), obtain D V (w) E 8 (w) and this completes the
DNE,,,, (w + v7") >
DD To proof of Theorem 8.
24

---

Published as a conference paper at ICLR 2024
F ALGORITHM FOR NETWORKS WITH SHARED BIAS AND ReLU
Algorithm is Algorithm for networks with shared bias parameters, where all non-differentiable Pt are ReLU with ReLU(() O.
Algorithm Construction of P/ for networks with shared bias parameters, where pt ReLU if p is non non-differentiable with (eL(()) = 0
1: Input: I: the index of the target layer, 20:-11: the outputs of the o,.... (7 the parameters of the 1,...,l-th 1-th layers, {Ii {Z) the index sets used by the maxpool function Φ4 the (-th layer.
1)-th layer, wi::
2: Initialize: Pt f- RW:
3: for i [M]]] [B] do
4:
- Ti.i 20: wi), ar + Pi(B)), + dy:/Owr
5: end for
6: for E [N]] B] do
7:
S; argmax ag
8:
[s 2 2 and maxieT, 0i 0 then
9:
i* t the index in I, that AD uses when computing DAD max(farliez,
10:
T₁ + {ie Sj 0n0 /dwna 0 a0////wi
11:
P1 + P E (T) > (T., for all i S; Tr}
end if
13:
end for
14: return Pt
G EXAMPLES OF IDENTICAL IMAGE PATCHES
Figure 1: Examples of identical input patches that incur ties in max, operations.
In Figure 1, we show example images where a tie occurs in a max, operation due to the same image patches that correspond to the receptive fields of the max, 's inputs. As shown in the figure, due to the nature the datasets, adjacent image patches are often identical to each other.
25

---

Published as a conference paper at ICLR 2024
H DISCUSSION ON FAILURE CASES OF AD AND OUR RESULTS
In this section, we consider three well-known failure cases of AD and discuss how they are handled in Theorems 1, 4-6, and Let g h ReLU with D 0 and (() = Then, AD returns an incorrect output (i.e., a value not in the Clarke subdifferential) in the following cases, even though it uses proxy gradients that are in the Bouligand subdifferential.
For fi(w) g(w) -(( we have D (0) D
0 {1} 8 f1)).
For f2(w) g(w) h(ww), we have D f2) -1 & [0) f2(O).
For fa(w) h(-h(w)), we have D (0 = -11 $ {0) = 0 (a()).
The three cases are handled in our theorems as follows. First, Theorems and 4 require that a given neural network should have distinct bias parameters. However, none of f: can be represented by network with distinct bias parameters, so they simply do not satisfy the conditions in Theorems and 4. Second, Theorem 5 requires that given network should have fully- connecco layers. How- ever, none of /i can be represented by a network with fully-connected layers, so they do not satisfy the condition in Theorem as well. Third, Theorem 6 requires that given network should have shared bias parameters and use the same À for all activation functions at the same layer (see the statement of the theorem for details). However, fi and fa cannot be represented by network with shared bias parameters, since the two g's in fi take arguments of different signs and the two h's in fs use only one parameter w; further, f2 cannot be represented by network that satisfies the afore- mentioned condition on X, since and h use the left- and right-hand derivatives at O, respectively. Hence, none of Sa satisfies the condition in Theorem 6. Finally, none of Sa satisfies the sufficient condition in Theorem 8 (i.e., Pi * 0 for all 1), where each ʃ; is considered network with two layers: we have P1 = 0 for fi and f2, and P2 for fa.
I DISCUSSION ON THEOREMS 1 AND 6
In this section, we compare Theorems and with a closely related prior result: Theorem 3.6 in (Lee et al., 2023).
Our Theorem is an extension of Theorem 3.6 in (Lee et al., 2023) in two ways. First, our theorem considers larger class of neural networks than the previous theorem: the latter restricts network to have no residual connections (page of (Lee et al., 2023)), while the former does not have this restriction (Section 2.2). Second, for the same network, our Theorem proves the same conclusion given in Theorem 3.6 of (Lee et al., 2023), but under a weaker assumption. The latter theorem states that if proxy gradients are in the Bouligand subdifferential, then AD computes element of the Clarke subdifferential. Our Theorem I extends this result as follows: the same conclusion holds even if use wider class of proxy gradients (namely those in the Clarke subdifferential). We believe this extension is an important addition to line of recent works (e.g., Bertoin et al. (2021); Boursier al. (2022)) on understanding the effects of the choice of proxy gradients.
Our Theorem 6 further generalizes Theorem 3.6 in (Lee et al., 2023) by considering an even larger class of neural networks. The latter theorem considers networks that not contain usual residual connections, convolutional layers, and normalization layers such as BatchNorm (pages 4 and 9 of (Lee al., 2023)) and do not allow minibatched inputs; hence, this prior result is not applicable to most convolutional networks used in practice. In contrast, our Theorem 6 allows minibatch setup and a network with general residual connections, convolutional layers, and normalization layers (Section 2.2); thus, this result is applicable wider range of neural networks including practically- used convolutional networks.
26

---

Published as a conference paper at ICLR 2024
J DISCUSSION ON ALGORITHM 1 AND THEOREM 8
In this section, we discuss the computational complexity of Algorithm 1 and provide a comparison between Theorem 8 and prior works.
J.1 COMPUTATIONAL COMPLEXITY OF ALGORITHM 1
We analyze the computational complexity of Algorithm 1 for the 1-th layer as follows. To simplify the notation, we assume that memory read/write, additionmmuliplicationn, and computing a proxy gradient take unit cost. Let A C [Mi] x [B] be the set of indices i of pointwise activation functions Pt whose non- non-differentiable points are touched (i.e.. Line 5 of Algorithm is true). For each index d E [MT] x [B] of maxpool neurons, let S, C [M]] x [B] be the set defined in Line 11 of Algorithm 1, and let C [ x [B] be the set of j's that satisfy |Sy] 2 2 (i.e., Line 12 of Algorithm is true). First, for each element in A. Algorithm 1 adds a constraint to Pt. Next, for each index j E B, Algorithm 1 computes Tj. which requires at most |رك] number of backward passes of AD (up to the (-th layer), and then it adds most |S,] - constraints to Pt. Finally, Algorithm checks whether Pi is empty or not, which can be done by solving a linear programming problem (see the last paragraph of Section 3). Hence, the worst-case time complexity of Algorithm can be written as O(IA + ( JEB (S Ct + 11,, (s,)), where Ci denotes the cost of a backward pass of AD up to the I-th layer and D,,, denotes the cost of solving linear programming problem with n variables and & constraints. To sum up, Algorithm has a worst-case time complexity that depends the number of ties arising in maxpools (i.e., (Sy]) and the number of ton-differentiability touches in pointwise activation functions (i.e., |A)..
J.2 EMPIRICAL OVERHEAD OF ALGORITHM 1
For neural networks that have shared bias parameters and use maxpools and ReLUs (with (e) = 0) as the only non-differentiable activation functions, Algorithm 1 can be sim- plified to Algorithm which does not care about whether any input to ReLU touches zero or not (i.e., does not care A discussed above). We used Algorithm 2 to check Pi & 0 in our experiments, and empirically observed that Algorithm 2 incurred not much computational overhead: for train- ing ResNet18 on the CIFAR-10 dataset, the average running times per epoch were 419 seconds with Algorithm 2 and 237 seconds without our algorithms, i.e., additional computational overhead was ~77% of the running time of the vanilla learning algorithm. We further observed that solving linear programming did not incur much overhead (<1%); almost all overhead (>99%) was from computing S₁ and Ty. and this overhead can be significantly reduced if we optimize our naive im- plementation of Algorithm 2 (e.g.. by implementing a native GPU kernel for computing Sý). This relatively small overhead of Algorithm was due to two phenomena we observed (shown in the second and fourth columns of Table 2): ties in maxpools occurred mostly in the first layer, so the backward passes of AD done in Algorithm 2 were very fast; and the number of constraints in P, was typically small, so checking the emptiness of Pi was very fast. To sum up, we observed that the empirical overhead of running Algorithm 2 was relatively low in the training of neural networks.
J.3 COMPARISON OF THEOREM WITH PRIOR WORKS
Compared to existing results, Theorem 8 has made important contributions in both theoretical and empirical perspectives. Theoretically. Theorem 8 is strict generalization of Theorem 4.7 in (Lee al., 2023), one of best known sufficient conditions for AD to compute a Clarke subderivative. More precisely, Theorem 8 not only includes the previous theorem as a special case, but also covers many more cases such as convolutional networks with residual connections and normalization lay- ers (which cannot be covered by the previous theorem). To our knowledge, Theorem 8 is the first sufficient condition that is applicable to practical neural networks. Empirically, Theorem 8 enables us verify that AD actually computed a Clarke subderivative in several practical learning scenarios (Section 4). To our knowledge, there has been no prior work that empirically verified (or theoreti- cally proved) that AD always outputs a Clarke subderivative in certain learning scenarios; our work is the first such work.
27


Reviews:
[{"review_id": "sKtlHyOb3w", "reviewer": "Reviewer_FQtB", "summary": "The paper studies the problem of automatic differentiation of neural networks with non-smooth operations such as ReLu activation and max-pooling. It provides some theoretical results.", "questions": "1. Are the results in Table 2 given by gradient descent, subgradient descent, or Clarke subgradient descent?\n2. Are the theoretical results applicable to other nonsmooth activation functions such as step function?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The theoretical results are rich.\n2. The numerical results are consistent with the theoretical results to some extent.", "weaknesses": "1. The results in the theorems are not intuitive and are difficult to follow.\n2. It is not clear how the numerical or theoretical result given by gradient descent differs from that given by subgradient descent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y7FzJBhIIc", "reviewer": "Reviewer_DHhS", "summary": "This paper extends the previous results on the characteristics of auto-differentiation (AD) in modern neural networks. Existing methods were limited in cases where the ADs of individual operations are limited to Bouligand subdifferentials, which is extended to Clarke subdifferentials in this paper. The paper shows that if biases are distinct and the batch size is one, then the overall gradient of a fully connected network using AD is always correct (is an instance of Clarke subdifferentials). If the batch size is larger than one, ADs of individual operations should be a convex combination of left-side and right-side derivatives to have a correct gradient. If there are no distinct biases, then having linearly independent features whenever non-differential boundaries are touched. The paper also provides conditions for CNN (presence of max-pool,  shared bias). Experiments demonstrate that the conditions provided in the paper are empirically correct.", "questions": "On page 6, when batch size is larger than one, a convex combination of the left-side and right-side derivatives is required. Here, the equation seems to suggest that any element that touches the boundary must have the same combination weights. Is this correct?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Even though auto-differentiations are widely used in practice, it is not well-known how it behaves on non-differentiable regions. These are usually ignored in practice. However, since most modern deep learning is usually performed numerically, these regions can sometimes be problematic. In this respect, accurate knowledge regarding the actual behavior can be beneficial.\n\nThis paper extends the existing results to wider conditions with more practical settings, i.e., Clarke subdifferentials, general fully-connected networks, and CNN as well. This significantly improves the usability of such knowledge in real situations (such as defining the individual gradient operation so that the overall gradient can be a Clarke subdifferential.)\n\nI did not check the proofs in detail, but they seem correct.", "weaknesses": "There are a wide variety of recent network structures and they go beyond the conditions assumed in this paper. However, considering the nature of incremental improvement in this kind of theoretical work, I believe it is a sufficient contribution.\n\nOn page 6, it is said that the input and the hidden dimension are typically larger than the batch size. However, this can be somewhat controversial. There are indeed cases where large batch sizes are used (e.g., early self-supervised learning) for several reasons, e.g., training stability, training time/speed, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lQvXeroLsy", "reviewer": "Reviewer_uFDP", "summary": "The paper studies the important problem of what is computed by automatic differentiation (AD) when the activation functions are not continuously differentiable, which is the most common case in practice with activations like the ReLU or its variants.\n\n---\n\nThe main results are several theorems (Thm 1, Thm 4, Thm 5, Thm 6, and Thm 8) that give sufficient conditions on a broad class of neural network architectures and training regimes (batch sizes) to ensure that AD always produces an element of the clarke subdifferential. Besides these sufficient conditions, there are several results showing how tight these results are, by proving that relaxing some of the sufficient conditions will result in AD producing something that is not an element of the clarke subdifferential.\n\nThere are two conditions considered to ensure that AD produces a clarke subgradient and both of them are centered on bias parameters. In the fist condition, the bias parameters must be distinct and the activations are applied componentwise. In the second condition, the bias parameters can be shared and more general activations (e.g., maxpooling, maxpool2d) are considered.\n\nThe strategy for showing that these conditions guarantee AD computes a clarke subgradient is to construct a sequence of points converging to the current point, on which the neural network is actually differentiable, and showing that the limits of the gradient on this set are converging to what is computed by AD, i.e., directly showing the definition of the Clarke subgradient is satisfied for what is computed by AD.\n\n---\n\nThe ultimate goal of the paper is theoretical but it does include some empirical validations of the theoretical claims made. The claims are tested by running sgd on fully connected networks and convolutional networks, both with activations that are not continuously differentiable.\n\nIn the fully connected case (they use 2 hidden layers with dimensions 256 and 64 respectively, trained on MNIST with batchsize 128), they check whether or not the sufficient condition to ensure AD computes a clarke subgradient is satisfied, and indeed it always is using three different activations (ReLU6, HardTanh, and HardSigmoid). They also confirm that the points where the activations are not continuously differentiable are seen by the algorithm (0 times for ReLU6, 9.8 times for HardTanh, and 13.8 times for HardSigmoid; all averaged over 5 runs).\n\nIn the convolutional case, they use the ordinary ReLU activation but combine with maxpools (they test 3 architectures - VGG11, VGG11-BN (batchnorm), and ResNet18 all on CIFAR10). They observe that their sufficient condition to ensure that AD computes a clarke subgradient is always satisfied here.\n\n---\n\nSmall comment: I find the usage of the word safe in the paper to be a bit weird. Whether or not AD computes a clarke subgradient doesn't make it safe or unsafe, even if it does not compute subgradients AD might still converge to a clarke-stationary point (see Bolte-Pauwels 2020). I also found this sentence “These correctness results show that AD computes the standard derivative at most inputs, yet provide no information about what it computes at the remaining inputs” to be incorrect, Bolte-Pauwels 2020 *does* provide information about what is computed at the remaining inputs - an element of the conservative field is computed and this object can still be used to show convergence of sgd-like algorithms.", "questions": "Something that I didn't understand regarding the notion of distinct bias parameters - is it ever an issue that some bias parameters might be equal during training?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper studies an important problem and gives strong theoretical results that apply to a broad class of neural network architectures and training regimes. Despite being theoretical in nature, the results are quite practical since many of the sufficient conditions are checkable in practice, as demonstrated in secion 4 with experiments on some realistic architectures.", "weaknesses": "I feel that the empirical validation section is missing something; it's always checked that the sufficient conditions derived in the paper are holding but it's never empiricaly validated that these sufficient conditions are actually sufficient for guaranteeing that AD computes a clarke subgradient. That being said, I still found the experiments are convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s3uju5Fxiz", "reviewer": "Reviewer_XRNZ", "summary": "This article provides an important step in the direction of providing a theoretical backbone to the behemoth topic of neural networks -- in particular, showing Clarke stationarity is the gold standard for this class of optimization problems, and they provide (modest, but appreciable) steps in this direction. The contribution does not appear to be huge, but the importance of the problem itself and the quality if the writing and results (if they are true) is worthy of publication.\n\nDue to a medical emergency, I unfortunately did not have the time to check the mathematical details and proofs of this article. To\naccount for this lack of availability, I am providing a low-confidence review with my impressions based on the results and impact to the research community.", "questions": "Due to a medical emergency, I unfortunately do not have the time to properly vet this article. I offer my deep apologies.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "In my opinion, the question studied in this article is one of the\nmost fundamental and pressing questions to modern-day theoretical\nmachine learning. I am happy to see work in this direction.", "weaknesses": "Of course, this is also a very challenging problem.\nAppropriately, this article appears to be a modest step in the\nright direction, with nothing particularly groundbreaking.\nNonetheless, the impact of this work would still be quite relevant. \n\nSubdifferential analysis is a very technical and detailed topic,\nand I must express my lack of confidence in the validity of the results.\nIt also appears that the authors have mixed up a Bouligand (directional) subdifferential\nand a Mordukhovich (sequential) subdifferential on page 3 of their\narticle. \nFurthermore -- and this not a qualm with the article specifically -- \nI have doubts about the ability of an ML\nconference (where reviewers have essentially two weeks to review 3+\narticles) to appropriately verify the correctness of the proofs\nin the 10+ pages of the (often un-reviewed or under-reviewed)\nappendices. I am hopeful that other referees have sufficient time to\nverify the proofs here, because if these results *are* indeed\naccurate, it is my opinion that this article would absolutely be\nworthy of publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y08wFpgFTp", "reviewer": "Reviewer_84GA", "summary": "### Edit after rebutal: \nI updated my score and my assessement of the paper after reading authors response. \n\nThis is an important topic which oughts to be discussed. The authors claim original results on correctness of automatic differentiation in a nonsmooth context based on the existence of bias parameters for each layer.", "questions": "Lemma 2 and Lemma 3:  the example in Lemma 2 is explicitely mentioned in Kakade and Lee 2018 and the mechanism in Lemma 3 is exaclty the same, namely \"incompatibility with addition\". A similar comment holds for Lemma 7. Is there anything else beyond these lemmas? Why not refering to the fact that this is a known issue?\n\nLemma 3 and Theorem 4 are contradictory. D- and D+ are never explicitely defined, so I assume that for a piecewise analytic function it corresponds to the derivative of the function on the left and on the right at a piece change point. In this case, the Bouligand derivative is {D-,D+} and the clarke is its convex hull. So in Theorem 4, choosing all lambda = 0, one is in the setting of Lemma 3. I suspect that Theorem 4 is false for this reason. Is my reasoning correct?\n\nI really have troubles to understand the difference between Condition 1 and Condition 2 with \"trivial max-pool\". This is very complicated and I believe there should be a qualitative description of what these conditions mean. For example I cannot tell: is one of the condition more general than the other? Similarly: is there is a difference between Theorem 4 and Theorem 6? Lastly, due to the same concern as above, I suspect that Theorem 6 is false.\n\nTheorem 8 is of little use without a discussion on:\n- When does the algorithm stop with Pl non empty? Does it occur often? Does it always occur?\n- What is the complexity of the algorithm? How much overhead does it represent compared to AD?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The results are among the only positive ones available in the litterature regarding soundness of AD for nonsmooth neural networks.", "weaknesses": "### Edit after rebutal: \nthe authors responded in a satisfactory way to the concerns raised below. \n\n- Theorem 1 is a minor extension of Theorem 3.6 in Lee et al. (2023). \n- Lemma 2 and Lemma 3 are complicated formulations of essentially known facts\n- Lemma 3 and Theorem 4 are contradictory\n- I suspect that Theorem 4 is flase, as well as theorem 6.\n- Conditions 1 and 2 are very complicated without an intuitive explaination of what they mean.\n- Theorem 8 lacks discussion on the rate of positive outcomes and complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)