Wonyeol Lee

Hangyeol Yu

Xavier Rival

Hongseok Yang

On Correctness of Automatic Differentiation for Non-Differentiable Functions

Differentiation lies at the core of many machine-learning algorithms, and is wellsupported by popular autodiff systems, such as TensorFlow and PyTorch. Originally, these systems have been developed to compute derivatives of differentiable functions, but in practice, they are commonly applied to functions with non-differentiabilities. For instance, neural networks using ReLU define nondifferentiable functions in general, but the gradients of losses involving those functions are computed using autodiff systems in practice. This status quo raises a natural question: are autodiff systems correct in any formal sense when they are applied to such non-differentiable functions? In this paper, we provide a positive answer to this question. Using counterexamples, we first point out flaws in oftenused informal arguments, such as: non-differentiabilities arising in deep learning do not cause any issues because they form a measure-zero set. We then investigate a class of functions, called PAP functions, that includes nearly all (possibly nondifferentiable) functions in deep learning nowadays. For these PAP functions, we propose a new type of derivatives, called intensional derivatives, and prove that these derivatives always exist and coincide with standard derivatives for almost all inputs. We also show that these intensional derivatives are what most autodiff systems compute or try to compute essentially. In this way, we formally establish the correctness of autodiff systems applied to non-differentiable functions.

Introduction

Automatic differentiation or autodiff is one of the key technologies behind the dramatic progress of deep learning in recent years [START_REF] Baydin | Automatic differentiation in machine learning: A survey[END_REF][START_REF] Lecun | Deep learning[END_REF][START_REF] Rumelhart | Learning representations by back-propagating errors[END_REF][START_REF] Schmidhuber | Deep learning in neural networks: An overview[END_REF]. It refers to the idea of developing and using a generic tool that can differentiate any function expressed as a program in a general-purpose programming language [START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF][START_REF] Pearlmutter | Reverse-mode AD in a functional framework: Lambda the ultimate backpropagator[END_REF]. Effective autodiff systems have been developed for popular programming languages [START_REF] Abadi | TensorFlow: A system for large-scale machine learning[END_REF][START_REF] Baydin | Diffsharp: An AD library for .NET languages[END_REF][START_REF] Bergstra | Theano: A CPU and GPU math compiler in Python[END_REF][START_REF] Bradbury | JAX: Composable transformations of Python+NumPy programs[END_REF][START_REF] Hascoët | The Tapenade automatic differentiation tool: Principles, model, and specification[END_REF][START_REF] Maclaurin | Autograd: Effortless gradients in Numpy[END_REF][START_REF] Paszke | PyTorch: An imperative style, high-performance deep learning library[END_REF][START_REF] Revels | Forward-mode automatic differentiation in Julia[END_REF][START_REF] Tokui | Chainer: A deep learning framework for accelerating the research cycle[END_REF][START_REF] Van Merrienboer | Tangent: Automatic differentiation using source-code transformation for dynamically typed array programming[END_REF][START_REF] Walther | Getting started with ADOL-C[END_REF]. They have enabled the development of sophisticated models and algorithms in machine learning that, in particular, involve deep neural networks [START_REF] Goodfellow | Deep learning[END_REF]. This paper is concerned with one seeming contradiction of these autodiff systems: the systems have originally been developed to compute derivatives of differentiable functions, but in practice, they are commonly applied to functions with non-differentiabilities. For instance, neural networks using ReLU define non-differentiable functions in general, but the derivatives of losses involving those functions are computed using autodiff systems in practice. This status quo raises a natural question: are autodiff systems correct in any formal sense when applied to such non-differentiable functions?

A common reaction to the question is: non-differentiabilities arising in deep learning (e.g., from ReLU) do not cause any issues because they occur rarely (i.e., they form a Lebesgue-measure-zero set). In the paper, we first show that this reaction needs to be carefully re-examined at least. Using counterexamples, we point out flaws in three often-used arguments derived from this reaction. We then present our answer. It is also positive, but based on a class of functions that satisfy a condition called piecewise analyticity under analytic partition (in short, PAP). These PAP functions include nearly all (possibly non-differentiable) functions in deep learning nowadays. For these PAP functions, we propose a new type of derivatives, called intensional derivatives, and prove that these derivatives always exist and coincide with standard derivatives for almost all inputs. These intensional derivatives behave almost as well as, and sometimes even better than, usual derivatives for differentiable functions. For instance, they always satisfy a chain rule even if functions are non-differentiable. Using these properties of intensional derivatives, we show that the intensional derivatives are what most autodiff systems compute or try to compute essentially. In this way, we formally establish the correctness of autodiff systems that compute derivatives of non-differentiable functions.

We use (a, b), (a, b], [a, b), and [a, b] to denote intervals in R, and a 1 , . . . , a n to denote tuples. For n ∈ (Z >0 ∪ {∞}), [n] means the set {1, 2, . . . , n}. We call Lebesgue measure simply by measure. The detailed statements and missing proofs of our results can be found in the appendix.

Challenges

As mentioned in the introduction, practitioners frequently apply autodiff systems to functions with non-differentiabilities, and justify these out-of-scope use cases with plausible yet heuristic arguments. In this section, we analyse these arguments. We go through three claims that are often used in the arguments implicitly, and show that although looking innocent at the outset, the claims have serious flaws; they are wrong, and we provide counterexamples.

Recall a notion of correctness for an autodiff system covering non-differentiable functions [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning[END_REF][START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF][START_REF] Kakade | Provably correct automatic sub-differentiation for qualified programs[END_REF]: Definition 1 (Correctness of Autodiff). We say that an autodiff system is correct if the following condition holds: for every measurable function f : X → R m defined on an open X ⊆ R n and implemented by a program, if f is differentiable almost everywhere (i.e., the set of inputs making f non-differentiable is contained in a measure-zero set), then for almost every x ∈ X , the autodiff system applied to (the program of) f and the input x computes the derivative of f at x.

The definition permits a non-differentiable function as an input to an autodiff system, as long as its non-differentiability occurs rarely (i.e., at a measure-zero subset of the input domain). For such a function, it may be impossible to compute the correct derivative for all inputs, simply because the derivative does not exist for inputs where the function is non-differentiable. Thus, the definition just requires that the system should compute the correct derivative for most inputs instead (i.e., for a subset of the input domain whose complement inside the domain is contained in a measure-zero set).

Proving the correctness of an autodiff system is surprisingly difficult. Nearly every autodiff system is based on a chain rule for computing the derivative of function composition, but when the component functions are non-differentiable, designing a correct version of the rule is challenging. To help the reader see this challenge, we analyse three plausible yet flawed claims about the derivative of function composition, which are sometimes used implicitly in heuristic justifications of autodiff systems.

Let f : X → Y and g : Y → R l be measurable functions defined over open sets X ⊆ R n and Y ⊆ R m . Here is the first claim:

Claim 1 If f and g are differentiable almost everywhere and continuous, then g • f should be differentiable almost everywhere.

A rationale for the claim goes as follows. In order for g • f to be non-differentiable at x 0 , the function f has to be non-differentiable at x 0 , or it should map x 0 to a non-differentiable input to g and be able to vary enough in a neighbourhood of x 0 . The claim says that such an x 0 is rare (from the perspective of measure). Of course, the first case that f is non-differentiable at x 0 occurs rarely by assumption. The second case seems to happen rarely as well, because the non-differentiable inputs to g are rare and f is continuous: because of continuity, if f maps many x 0 's (i.e., all the x 0 in some non-measure-zero set) to those rare non-differentiable inputs of g, it should behave as a constant function in the neighbourhoods of most of those x 0 's.

The rationale has a flaw, and the claim is false. The inputs x 0 falling into the second case are not necessarily rare. Although f is continuous, it is possible that f maps many x 0 's to some of those rare non-differentiable inputs of g without acting as a constant function in a neighbourhood of each of those x 0 's. The precise result is summarised in the following proposition: Proposition 1. There exist functions f : (0, 1) → (0, 1) and g : (0, 1) → [0, 1] such that f and g are differentiable almost everywhere and continuous, but g •f fails to be almost-everywhere differentiable.

Proof. Before our proof, we review a generalised version of the Cantor set and Cantor function [START_REF] Cantor | De la puissance des ensembles parfaits de points: Extrait d'une lettre adressée à l'éditeur [On the power of perfect sets of points[END_REF][START_REF] Darst | Some Cantor sets and Cantor functions[END_REF] defined over the open interval (0, 1): the λ-Cantor set C λ and the λ-Cantor function φ λ for λ ∈ (0, 1], which reduce to the original Cantor set and function when λ = 1. The C λ and φ λ will serve as building blocks of counterexamples presented in this paper. The set C λ ⊂ (0, 1) consists of all the real numbers not removed during the following procedure: at step k = 0, start with a closed interval [0, 1] ⊂ R; at each step k > 0, remove every open interval of length λ/3 k which locates exactly at the middle of each remaining closed interval; and after all these steps, remove 0 and 1.

Note that what remains after the step k are 2 k closed intervals. The function φ λ : (0, 1) → (0, 1) is defined as follows, based on the construction of C λ . At each step k > 0, define φ λ over the i-th open interval to be removed as

φ λ (x) = (2i -1)/2 k (i ∈ [2 k-1 ]
). After all these steps, φ λ is defined over some dense open subset S of [0, 1] (in fact, S = (0, 1) \ C 1 ). Since φ λ : S → [0, 1] is uniformly continuous with S being dense in [0, 1], it has the unique continuous extension Exercise 4.13]. The λ-Cantor function refers to its restricted version φ λ : (0, 1) → (0, 1).

φ λ : [0, 1] → [0, 1] [37,
Returning to the proof, let f be the inverse of the homeomorphism F : (0, 1) → (0, 1) defined by

F (x) = 1 2 (φ 1 (x) + x) [8, Example 2.3.1]. It is known that f (C 1/2 ) = C 1 [8, Example 2.3.2]. Construct g : (0, 1) → [0, 1]
based on the construction of C 1 as follows, similarly to [18, Example 8.18]: at each step k > 0, define g over the i-th open interval (l i , r i ) to be removed, as

g(y) = 2 -k • [1 -(y -(r i + l i )/2) 2 /((r i -l i )/2) 2 ] (i ∈ [2 k-1 ]
); and define g over C 1 as g(y) = 0. See Figure 1 for the graphs of φ 1 , f , and g constructed so far. Clearly, f is continuous. Also, g is continuous, since the height of the parabolas defined at the k-th step of g's construction converges to 0 as k → ∞, and g(C 1 ) = {0} (see Appendix A for the details). Hence, g • f is continuous. Note that f is even Lipschitz continuous. To prove this, observe that f can be constructed similarly to φ 1/2 , and repeat the proof of the Lipschitz continuity of φ 1/2 [START_REF] Darst | Some Cantor sets and Cantor functions[END_REF].

We now show that f and g are differentiable almost everywhere, but g • f is not. First, since f is Lipschitz continuous, it is differentiable almost everywhere by Rademacher's theorem [START_REF] Tao | An introduction to measure theory[END_REF]Theorem 2.2.4]. Next, since g is differentiable on (0, 1) \ C 1 by its construction, it is differentiable almost everywhere (as C 1 has measure 0). Lastly, g • f is non-differentiable on C 1/2 , which has measure 1/2, due to that: the parabolas defined at the k-th step of g's construction get sharper as k → ∞; g(C 1 ) = {0}; and f is a homeomorphism with f (C 1/2 ) = C 1 (see Appendix A for the details).

The second claim is about a chain rule.

Claim 2 If f , g, and g • f are differentiable almost everywhere and continuous, then the standard chain rule for g • f should hold almost everywhere. In particular, if f, g : (0, 1) → (0, 1),

then (g • f ) (x 0 ) = g (f (x 0 )) • f (x 0 ) for almost all x 0 ∈ (0, 1).
Note that all of f , g, and g • f in the claim are assumed to be differentiable almost everywhere. The claim comes from heuristic reasoning that if we just avoid those rare non-differentiable inputs of g • f , we should be able to use the standard result for differentiation, including the chain rule.

The second claim is also wrong. The flaw in the heuristic reasoning from above is that the almosteverywhere differentiability of f , g, and g • f does not stop g (f (x 0 )) from being undefined for many x 0 's in (0, 1). This is related to the flaw in the justification for the first claim that we explained. The next proposition and its proof provide a concrete example for this phenomenon:

Proposition 2. There exist functions f, g : (0, 1) → (0, 1) such that f , g, and g • f are differentiable almost everywhere and continuous, but it is not that g (f (x)) is defined for almost all x ∈ (0, 1).

Proof. Let f (x) = 1/2 and g(y) = ReLU(y -1/2) + 1/2. Then, (g • f )(x) = 1/2. Certainly, f , g, and g • f are differentiable almost everywhere and Lipschitz continuous. But, g is not differentiable at f (x) = 1/2 for all x ∈ (0, 1). So, it is not that g (f (x)) is defined for almost all x ∈ (0, 1).

The third claim is a natural reaction to the failure of the second claim. It implements the strategy of making the chain rule in the second claim more permissive such that the counter argument of Proposition 2 no longer applies. The claim expresses a weaker version of the rule that allows one to set the derivatives of f and g to arbitrary values wherever f and g are not differentiable.

Claim 3 Let f, g : (0, 1) → (0, 1). If f , g, and g • f are differentiable almost everywhere and continuous, then there should exist df , dg : (0, 1) → R such that df (x 0 ) = f (x 0 ), dg(y 0 ) = g (y 0 ), and

(g • f ) (x 0 ) = dg(f (x 0 )) • df (x 0 )
for almost all x 0 , y 0 ∈ (0, 1).

The functions df and dg in the claim are the extensions of f and g that set df (x) and dg(y) to arbitrary values whenever f (x) and g (y) are undefined. The chain rule in the claim is phrased in terms of these extensions df and dg, so that it does not suffer from the problem pointed out in Proposition 2. However, this new rule is still flawed as shown in the next proposition:

Proposition 3. There exist functions f, g : (0, 1) → (0, 1) such that f , g, and g • f are differentiable almost everywhere and continuous, but for some measurable subset A ⊆ (0, 1) with non-zero measure, they satisfy the following property: f (x) = 0 and (g • f ) (x) = 0 for all x ∈ A.

Proof. Consider the function f in the proof of Proposition 1. Let g be the 1-Cantor function φ 1 . Then, g • f is the (1/2)-Cantor function φ 1/2 . We already showed f is differentiable almost everywhere and even Lipschitz continuous. Since g and g • f are monotone on (0, 1), they are differentiable almost everywhere by the monotone differentiation theorem [41, Theorem 1.6.25]; and they are clearly continuous. We now show there exists A ⊆ C 1/2 with the desired properties. Since C 1/2 has measure 1/2, it suffices to prove f (x) = 0 and (g • f ) (x) = 2 for almost all x ∈ C 1/2 . The claim indeed holds due to the following: f and g • f are Lipschitz, so absolutely continuous; f (x) = 2 and (g • f ) (x) = 0 for all x / ∈ C 1/2 ; f (x) ≥ 0 and (g • f ) (x) ≤ 2 for all x ∈ C 1/2 whenever these derivatives exist; and C 1/2 has measure 1/2. For the details, see [START_REF] Boyarsky | Laws of chaos: Invariant measures and dynamical systems in one dimension[END_REF]Example 2.3.2] and [START_REF] Darst | Some Cantor sets and Cantor functions[END_REF].

The proposition implies the third claim is doomed. The claim says that df (x 0 ) = f (x 0 ) and (g • f ) (x 0 ) = dg(f (x 0 )) • df (x 0 ) for almost all x 0 ∈ A. But both equalities cannot hold simultaneously: if they do, by Proposition 3, (g

• f ) (x 0 ) = dg(f (x 0 )) • df (x 0 ) = dg(f (x 0 )) • f (x 0 ) = dg(f (x 0 )) • 0 = 0,
but the same proposition also entails (g • f ) (x 0 ) = 0, leading to a contradiction.

A lesson from these flawed claims is that although the notion of correctness in Definition 1 only refers to almost-everywhere differentiability, we need a condition stronger than it, which behaves better in handling function composition and gives rise to a chain rule. We describe such a condition next.

PAP Function and Intensional Derivative

Our justification of autodiff systems relies on two key concepts: piecewise analyticity under analytic partition, and intensional derivative. The first is a (strictly) stronger property about functions than almost-everywhere differentiability, and yet it is satisfied by practically all programs targeted at by existing autodiff systems, as we will show in §4. Functions with this new property, called PAP functions, have an unusual type of derivatives, called intensional derivatives, which form the second concept. Intensional derivatives of PAP functions are defined everywhere and satisfy a chain rule, while still agreeing with standard derivatives for almost all inputs. In fact, the PAP functions have not just first-order but also all higher-order intensional derivatives. In §4, we will show that most autodiff systems compute intensional derivatives when applied to functions with non-differentiabilities.

To expand the overview of the two concepts just given, we need a notion of piecewise representation:

Definition 2 (Piecewise Representation). Let X ⊆ R n and Y ⊆ R m . A set of pairs γ = { A i , f i } i∈[I] is a piecewise representation of a function from X to Y or simply representa- tion if and only if (i) I ∈ Z >0 ∪ {∞}; (ii) {A i } i∈[I] is a partition of X ; and (iii) each f i : X i → Y is a function on an open domain X i ⊆ R n with A i ⊆ X i . The evaluation of a representation γ = { A i , f i } i∈[I]
is the map γ : X → Y defined by: γ (x) = f i (x) for all i ∈ [I] and x ∈ A i .

A representation γ = { A i , f i } i∈[I] describes a function f in terms of a finite or countable number of component functions f i and their scopes A i of application. For each input x, the value of f at x is determined by some component f i , chosen based on which piece of the input partition {A i } i∈[I] , the x belongs to. Our notation for the described f is γ . Note that the domain X i of each f i has to be open, and it may be larger than A i , the set of inputs where f i is used. As a result, a function can be described by an infinite number of representations. For instance, ReLU has at least two representations:

{ R <0 , x -→ 0 , R ≥0 , x -→ x } and { R <0 , x -→ 0 , {0}, x -→ 2x , R >0 , x -→ x }.
Having a piecewise representation of a function, instead of just the function, has several advantages. One of them is that for many properties of functions, we can derive their piecewise variants using those representations. We apply this advantage to analyticity. Recall that a real-valued function is analytic if and only if it is infinitely differentiable and is equal to its Taylor expansion. For R m -valued function g, the analyticity means the coordinate-wise analyticity: for all j ∈ [m], the composition π j • g of the j-th projection π j and g is analytic. Analytic functions are favoured by autodiff systems, because they are infinitely differentiable and become zero only at a measure-zero set of inputs (unless they are zero everywhere or their domains are disconnected). Let X ⊆ R n and Y ⊆ R m be any sets. Definition 3 (Analytic Partition). A set A ⊆ R n is analytic if and only if for some J, L ∈ Z >0 , there are analytic functions g + j :

X + j → R and g - l : X - l → R over open domains X + j , X - l ⊆ R n (j ∈ [J], l ∈ [L]) such that A = {x ∈ R n | ( j∈[J] x ∈ X + j ∧ g + j (x) > 0) ∧ ( l∈[L] x ∈ X - l ∧ g - l (x) ≤ 0)}. A partition {A i } i∈[I] of X is analytic if and only if all A i are analytic. Definition 4 (PAP Representation). A representation γ = { A i , f i } i∈[I] from X to Y is piecewise analytic under analytic partition (in short, PAP) if and only if {A i } i∈[I] is an analytic partition of X and f i is analytic over its domain X i for all i ∈ [I]. Definition 5 (PAP Function). A function f : X → Y is piecewise analytic under analytic partition (in short, PAP) if f = γ for some PAP representation γ.
The definitions identify PAP representations and PAP functions as those built by the two-step process: we first split the input domain such that boundaries of the split regions are expressed by the zero sets of analytic functions, and next choose an appropriate analytic function for each piece of the split. Note the use of analytic functions in both steps. Thus, just like the standard analyticity, the PAP property implies almost-everywhere differentiability (Proposition 4), but not vice versa (Proposition 5). Proposition 4 ( [START_REF] Zhou | LF-PPL: A lowlevel first order probabilistic programming language for non-differentiable models[END_REF]). All PAP functions are differentiable almost everywhere. Proof. The proof extends the one for a similar result in [START_REF] Zhou | LF-PPL: A lowlevel first order probabilistic programming language for non-differentiable models[END_REF]. The key idea is to use the fact that the zero set of a non-constant analytic function over a connected open domain has measure zero [START_REF] Mityagin | The zero set of a real analytic function[END_REF]. To prove the proposition, we show that for each PAP function f , there exist countably many non-constant analytic functions {g j } j over connected open domains such that if f is non-differentiable at x ∈ X , then x belongs to the zero set of some g j . For the details, see Appendix B.3. Proposition 5. There is a continuous almost-everywhere differentiable yet non-PAP function. Proof. We have two sufficient conditions for a function f to be non-PAP: (i) the k-th order derivative of f is undefined on a set of positive measure for some k ≥ 1 (Proposition 8); and (ii) the k-th order derivative of f is undefined on an uncountable set for some k ≥ 1, and f is defined on a subset of R (Appendix B.5). The following functions satisfy (i) with k = 2: the λ-Cantor function for all λ ∈ (0, 1), f in the proof of Proposition 1, and Volterra's function V : (0, 1) → R [START_REF] Gelbaum | Counterexamples in analysis[END_REF]Example 8.35]. The following functions satisfy (ii) with k = 1: the 1-Cantor function and g in the proof of Proposition 1. All these functions are known (or already proven above) to be continuous and almost-everywhere differentiable. Hence, all of them are desired functions.

We now define intensional derivatives of PAP representations and PAP functions. Let γ

= { A i , f i } i∈[I] be a PAP representation from X to Y for some X ⊆ R n and Y ⊆ R m . Definition 6 (Intensional Derivative of PAP Representation). An intensional derivative of γ is the set Dγ = { A i , Df i } i∈[I]
, where Df i is the standard derivative of f i viewed as a function from the domain X i of f i to R m×n . Proposition 6. The intensional derivative Dγ is a PAP representation from X to R m×n . Proof. Nearly all the requirements for Dγ to be a PAP representation directly follow from the fact that γ is PAP. The only exception is the analyticity of Df i . There we use the fact that the operation of taking a (standard) partial derivative of a function preserves analyticity [25, Proposition 2.2.3].

Definition 7 (First-Order Intensional Derivative). Let f : X → Y be a PAP function. Define ∂ • f to be the following set of functions:

∂ • f = { Dγ | γ is a PAP representation of f }. Each df ∈ ∂ • f is called a (first-order) intensional derivative of f .
By Proposition 6, only PAP functions live in ∂ • f . Thus, we can also take intensional derivatives of functions in ∂ • f . We push this observation further and define higher-order intensional derivatives: Definition 8 (Higher-Order Intensional Derivative). Let f : X → Y be a PAP function. For each k ∈ Z ≥0 , inductively define the set ∂ k

• f of functions by:

∂ 0 • f = {f }, and ∂ k • f = {df k ∈ ∂ • (df k-1 ) | df k-1 ∈ ∂ k-1 • f } for k ≥ 1. Each df k ∈ ∂ k • f is called a k-th order intensional derivative of f .
A function f : X → Y may have zero, one, or more than one intensional derivatives. Having at least one intensional derivative corresponds to f being differentiable in the standard sense. The next propositions show that every PAP function is infinitely differentiable in the new sense (Proposition 7), and that these standard and new notions of differentiability coincide if we ignore a measure-zero set of inputs (Proposition 8). Let f : X → Y be a PAP function for some X ⊆ R n and Y ⊆ R m . Proposition 7. For all k ∈ Z ≥0 , the set ∂ k • f of the k-th order intensional derivatives is not empty. Furthermore, its elements are again PAP functions from X to R m×n k . Proof. The proof is by induction on k. First, for the case k = 0, ∂ k

• f is a singleton set and its unique element f is PAP. Hence, the proposition holds. Next, consider the case k > 0. By induction hypothesis, ∂ k-1 • f is not empty and consists of PAP functions only. Thus, the set {γ | γ is a PAP representation of g for some g ∈ ∂ k-1 • f } is not empty. This and Proposition 6 imply that ∂ k

• f (obtained by applying Don the above set) is nonempty and contains only PAP functions. Proposition 8. For all k ∈ Z ≥0 , f has the k-th order standard derivative almost everywhere, and this derivative agrees with any k-th order intensional derivative df k ∈ ∂ k

• f almost everywhere. In the proposition, we view the k-th order standard derivative of f as a function of type X → R m×n k . For instance, when k = 1, the derivative maps an input to the Jacobian matrix of f . Proof of Proposition 8. The first claim is proven similarly to Proposition 4, except that we additionally use the following: an analytic function is infinitely differentiable. As in Proposition 4, we prove a stronger statement: there exist countably many non-constant analytic functions {g j } j over connected open domains such that for all k, if the k-th order standard derivative of f is not defined at x ∈ X , then x is in the zero set of some g j . Next, consider the second claim. Its current form is not strong enough to enable inductive proofs. We instead prove a stronger statement by induction on k: for each df k ∈ ∂ k

• f , there exist countably many non-constant analytic functions {h l } l over connected open domains such that the k-th order standard derivative of f is well-defined, and agrees with df k , at all those inputs not in the zero sets of {h l } l . For the details, see Appendices B.3 and B.4.

Intensional derivatives behave better than standard derivatives. First, the intensional derivatives of a PAP function f are total functions, i.e., functions defined for all inputs (Proposition 7). Contrast this with the fact that the standard derivative of f is a partial function in general. The intensional derivatives can be understood as extensions of this standard derivative of f to those problematic inputs that make f non-differentiable (Proposition 8). The totality simplifies the reasoning about intensional derivatives. Second, the intensional derivatives satisfy a chain rule for all PAP functions (Proposition 10). Let f : X → Y and g : Y → R l be PAP functions for some X ⊆ R n and Y ⊆ R m . Proposition 9. g • f is a PAP function. Proof. Since f and g are PAP, they have PAP representations

γ f = { A i , f i } i∈[I] and γ g = { B j , g j } j∈[J]
. Define their composition as follows:

γ g • γ f = { C i,j , g j • f i } i,j ∈[I]×[J] where C i,j = {x ∈ X | x ∈ A i ∧ f i (x) ∈ B j }. Then, γ g • γ f is a representation of g • f .
Also, it is PAP as the composition of analytic functions is analytic [25, Proposition 2.2.8]. Thus, g • f is PAP. Proposition 10 (Chain Rule for Intensional Derivatives). Let df : X → R m×n and dg : Y → R l×m be intensional derivatives of f and g (i.e., df ∈ ∂ • f and dg ∈ ∂ • g). Let h = g•f . Then, the following function dh : X → R l×n is an intensional derivative of h (i.e., dh ∈ ∂ • h): dh(x) = dg(f (x))•df (x) for all x ∈ X , where dg(f (x)) • df (x) is the multiplication of matrices dg(f (x)) and df (x). Proof. By the definition of intensional derivative, df = Dγ f and dg = Dγ g for some PAP representations γ f = { A i , f i } i∈[I] and γ g = { B j , g j } j∈[J] of f and g. Let γ g • γ f be the composed representation defined in the proof of Proposition 9. Then,

γ g • γ f is a PAP representation of g • f . So, D(γ g • γ f ) is an intensional derivative of g • f . Also, for all x ∈ X , if we let i, j ∈ [I] × [J] with x ∈ A i and f i (x) ∈ B j , then D(γ g • γ f ) (x) = D(g j • f i )(x) = D(g j )(f i (x)) • D(f i )(x) = Dγ g (f (x)) • Dγ f (x).
The first and last equalities follow from the definition of intensional derivative. The second equality uses the chain rule for standard derivatives: the rule holds here because f i and g j are analytic in neighbourhoods of x and f i (x), respectively.

We next use these properties to show that existing autodiff systems compute intensional derivatives.

Correctness of Autodiff Systems

Consider a simple programming language that assumes real-valued input variables x 1 , . . . , x N and has the following syntax for programs:

e ::= c | x i | f(e 1 , . . . , e n ) | if (e 1 > 0) e 2 e 3 .
A program e in the language describes a real-valued computation. It is a real number c, an input variable x i , the application of a primitive function f to arguments e 1 , . . . , e n , or a conditional expression. In the third case, the applied function is required to be a PAP function of the right type (i.e., R n → R in this case). We remark that practically all primitive functions supported by autodiff systems are indeed PAP; we are unaware of any non-PAP primitive function used in practice. If this requirement is met, all programs e mean PAP functions of type R N → R. More precisely, we interpret each program e as a function e : R N → R inductively, as shown below:

for all v ∈ R N , c v = c, x i v = v i , f(e 1 , . . . , e n ) v = f( e 1 v, . . . , e n v), if (e 1 > 0) e 2 e 3 v = if ( e 1 v > 0) then e 2 v else e 3 v.
where v i is the i-th component of the vector v, and f : R n → R is the PAP function denoted by the function symbol f in the language. Then, the defined e is always PAP. Proposition 11. For every program e, its denotation e is a PAP function from R N to R.

Proof. The proof is by induction on the structure of e. The cases of e ≡ c and e ≡ x i follow from the fact that both constant functions and projections are PAP. For the case of e ≡ f(e 1 , . . . , e n ), we note two facts about PAP functions: the composition of two PAP functions is PAP (Proposition 9); and for PAP functions g 1 , . . . , g n : R N → R, the function v -→ g 1 (v), . . . , g n (v) of type R N → R n is PAP again, mainly because any finite intersection of open sets is again open. By these two facts, the claimed property of the proposition holds in this case.

The only remaining case is e ≡ (if (e 1 > 0) e 2 e 3 ). By induction hypothesis, all of e 1 , e 2 , and e 3 are PAP. Let

γ 1 = { A i , f i } i∈[I] , γ 2 = { B j , g j } j∈[J]
, and γ 3 = { C k , h k } k∈[K] be their PAP representations, and define their conditional composition cond(γ 1 , γ 2 , γ 3 ) as follows:

cond(γ 1 , γ 2 , γ 3 ) = { E i,j,k,l , t i,j,k,l } i,j,k,l ∈([I]×[J]×[K]×{0,1}) , E i,j,k,l = A i l ∩ B j ∩ C k , and t i,j,k,l = if (l = 1) then g j else h k , where A i 1 = {v ∈ A i | f i (v) > 0} and A i 0 = {v ∈ A i | f i (v) ≤ 0}.
Then, {E i,j,k,l } i,j,k,l is an analytic partition of R N , every t i,j,k,l is an analytic function, and its domain is an open set containing E i,j,k,l . Thus, cond(γ 1 , γ 2 , γ 3 ) is a PAP representation. Furthermore, its evaluation cond(γ 1 , γ 2 , γ 3 ) is equal to if (e 1 > 0) e 2 e 3 . Hence, the proposition holds in this case.

We show that if an autodiff system for the language satisfies two requirements to be described shortly, it essentially computes an intensional derivative, even when the input function is not differentiable. The first requirement is that for every primitive operation f of type R n → R, the system should come with a function Df : R n → R 1×n that satisfies Df ∈ ∂ • f and serves as a "derivative" of f. To describe the second requirement, we inductively define the function e ∇ : R N → R 1×N , formalising symbolic differentiation of a program e, as follows:

for all v ∈ R n , c ∇ v = 0 1×N , f(e 1 , . . . , e n ) ∇ v = ( Df)( e 1 v, . . . , e n v) • [ e 1 ∇ v; . . . ; e n ∇ v], x i ∇ v = [ 0 (i-1)×1 ; 1 1×1 ; 0 (N -i)×1 ] , if (e 1 >0) e 2 e 3 ∇ v = if ( e 1 v>0) then e 2 ∇
v else e 3 ∇ v. Here c i×j denotes the i × j matrix containing only the constant c, and the RHS of the second equation means the multiplication of the 1 × n matrix ( Df)( e 1 v, . . . , e n v) and the n × N matrix [ e 1 ∇ v; . . . ; e n ∇ v] that is constructed by concatenating n matrices e 1 ∇ v, . . . , e n ∇ v of size 1 × N . The definition of e ∇ v computes a "Jacobian" matrix of e (which is a 1 × N matrix in this case) in the usual way of symbolic differentiation: run the program e under the input v, and calculate the "Jacobian" matrix of the encountered operations using the chain rule with the "derivatives" Df of those operations f [START_REF] Abadi | A simple differentiable programming language[END_REF][START_REF] Baydin | Automatic differentiation in machine learning: A survey[END_REF][START_REF] Huot | Correctness of automatic differentiation via diffeologies and categorical gluing[END_REF][START_REF] Wang | Demystifying differentiable programming: Shift/reset the penultimate backpropagator[END_REF]. Our second requirement is that given a program e and an input v ∈ R N , if the system performs forward-mode (or reverse-mode) autodiff with a tangent vector w ∈ R N (or a cotangent vector u ∈ R), it should output the Jacobian-vector product ( e ∇ v) • w ∈ R (or the vector-Jacobian product u • ( e ∇ v) ∈ R N ) [START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF][START_REF] Maclaurin | Modeling, inference and optimization with composable differentiable procedures[END_REF][START_REF] Margossian | A review of automatic differentiation and its efficient implementation[END_REF]. Intuitively, the second requirement says that the output of an autodiff system should coincide with that of symbolic differentiation. Note that the requirement does not fix the choice of an autodiff algorithm, and has two separate conditions for forward-mode and reverse-mode algorithms. Our next results show that these requirements ensure the correctness of an autodiff system. Theorem 12. If Df ∈ ∂ • f for all primitive functions f, then e ∇ ∈ ∂ • e for all programs e. Proof. The proof is by induction on the structure of e. When e ≡ c, the trivial partition {R N } and the constant function v -→ c form a PAP representation of e . The intensional derivative of this representation is { R N , v -→ 0 1×N }, and its evaluation is c ∇ , as claimed by the theorem. The other base case is e ≡ x i . We use the trivial partition again with the projection function v -→ v i , and form a PAP representation of e . The intensional derivative of this representation is { R N , v -→ [ 0 (i-1)×1 ; 1 1×1 ; 0 (N -i)×1 ] }, and its evaluation is

x i ∇ .
The next case is e ≡ f(e 1 , . . . , e n ). By induction hypothesis, e i ∇ is an intensional derivative of e i for every i ∈ [n]. Let g : R N → R n and dg : R N → R n×N be functions defined by g(v) = e 1 v, . . . , e n v and dg(v) = [ e 1 ∇ v; . . . ; e n ∇ v] for all v. Then, dg is an intensional derivative of g. Also, f(e 1 , . . . , e n ) = f • g. Therefore, by the chain rule for intensional derivative (Proposition 10), the function v -→ ( Df)(g(v)) • dg(v) is an intensional derivative of f(e 1 , . . . , e n ) = f • g. Here we use the assumption that Df is an intensional derivative of f. Note that the function is equal to f(e 1 , . . . , e n ) ∇ . So, the theorem holds.

The last case is e ≡ (if (e 1 > 0) e 2 e 3 ). By induction hypothesis, e i ∇ is an intensional derivative of e i for all i ∈ [START_REF] Baydin | Diffsharp: An AD library for .NET languages[END_REF]. Let γ 1 , γ 2 , and γ 3 be the PAP representations of e 1 , e 2 , and e 3 such that Dγ 2 = e 2 ∇ and Dγ 3 = e 3 ∇ . Let cond(γ 1 , γ 2 , γ 3 ) be the conditionally composed representation defined in the proof of Proposition 11. Then, it is a PAP representation of if (e 1 > 0) e 2 e 3 . But by the definitions of γ 2 , γ 3 , -∇ , cond(-, -, -), and D-, we have

Dcond(γ 1 , γ 2 , γ 3 ) (v) = if (e 1 > 0) e 2 e 3 ∇ v for all v ∈ R N .
Hence, the theorem holds in this case as well. Corollary 13. Assume that an autodiff system for the language in this section satisfies the two requirements. Then, for each program e, there exists an intensional derivative df of e such that if the system performs forward-mode (or reverse-mode) autodiff with a tangent vector w ∈ R N (or a cotangent vector u ∈ R), it computes the Jacobian-vector product df (v) • w ∈ R (or the vector-Jacobian product u • df (v) ∈ R N ) for every input v ∈ R N . Furthermore, the computed entity is the corresponding Jacobian-vector product (or vector-Jacobian product) with the standard derivative of e for almost all inputs v ∈ R N . Proof. Suppose that the two requirements are met, and let e be a program. Consider the case when the system performs forward-mode autodiff. Let df = e ∇ . Then, by Theorem 12, df is an intensional derivative in ∂ • e . Moreover, by the second requirement, the output of the system for e with a tangent vector

w ∈ R N is ( e ∇ v) • w = df (v) • w ∈ R for all inputs v ∈ R N .
This proves the first part of the corollary. The other part of the corollary follows immediately from Proposition 8. The proof for the case when reverse-mode autodiff is performed is essentially the same, so we omit it. Remark 1 (Intensional Derivatives in Practice). We briefly discuss whether the first requirement mentioned earlier is indeed met by autodiff systems. TensorFlow [START_REF] Abadi | TensorFlow: A system for large-scale machine learning[END_REF] and PyTorch [START_REF] Paszke | PyTorch: An imperative style, high-performance deep learning library[END_REF], two popular autodiff systems, support a wide range of primitive functions that are not differentiable for some inputs. A well-known example is relu : R → R (i.e., the map x -→ max(0, x)). This function is not differentiable at 0, but when these autodiff systems are applied to differentiate relu at 0, they return 0 instead of an error (i.e., ( Drelu)(0) = 0). It means that the systems compute the intensional derivative Dγ of relu for γ = { R >0 , x -→ x , R ≤0 , x -→ 0 }. Thus, they fulfil the first requirement on relu. Note that setting the derivative at the input 0 to any c ∈ R is an acceptable option; it can be justified by a different PAP representation γ of relu where γ = { R >0 , x -→ x , {0}, x -→ c•x , R <0 , x -→ 0 }. Another example is reciprocal_no_nan from TensorFlow. It means the map f (x) = 1/x if x = 0, and 0 if x = 0. Differentiating this map by TensorFlow gives the function ( Df )(x) = -1/x 2 if x = 0, and 0 if x = 0. The Df is an intensional derivative of f , because γ = { R \ {0}, x -→ 1/x , {0}, x -→ 0 } is a PAP representation of f and Dγ coincides with Df . Hence, TensorFlow meets the first requirement on reciprocal_no_nan.

However, for some functions, TensorFlow and PyTorch behave more conservatively than our theory of PAP functions permits. A good example is sqrt. The domain of sqrt is R ≥0 , but differentiating sqrt at 0 using these autodiff systems returns +inf, which means ∞ (i.e., ( Dsqrt)(0) = ∞). Thus, the first requirement on sqrt is violated by these systems. One consequence of this is that when the systems are applied to differentiate sqrt(mult(x, 0)), they end up with computing 0*(+inf) that evaluates to NaN (meaning an undefined number in floating point arithmetic) for all x ∈ R. Note that sqrt(mult(x, 0)) is constantly zero and has zero as its derivative. This conservative behaviour could have been avoided if TensorFlow and PyTorch had recognised that sqrt is a PAP function and had used its intensional derivative instead. For instance, the function (dsqrt)(x) = 1/(2 √ x) if x > 0, and 0 if x = 0, is an intensional derivative of sqrt, since γ = { R >0 , x -→ √ x , {0}, x -→ 0 } is a PAP representation of sqrt. If TensorFlow and PyTorch used dsqrt as a derivative of sqrt, they would be able to differentiate sqrt(mult(x, 0)) correctly for all x ∈ R.

Related Work and Discussion

Autodiff has a long history with a large body of literature [START_REF] Baydin | Automatic differentiation in machine learning: A survey[END_REF][START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF][START_REF] Pearlmutter | Reverse-mode AD in a functional framework: Lambda the ultimate backpropagator[END_REF]. Its community has been aware of some issues with non-differentiable functions [START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF]Chapter 14]. These issues have become ever more important, as autodiff has been increasingly applied to a variety of non-differentiable functions, including sophisticated linear algebra functions [START_REF] Kakade | Provably correct automatic sub-differentiation for qualified programs[END_REF][START_REF] Maclaurin | Modeling, inference and optimization with composable differentiable procedures[END_REF][START_REF] Seeger | Auto-differentiating linear algebra[END_REF]. In this paper, we investigate the issues in a more systematic and rigorous way, by presenting non-trivial concrete counterexamples that illuminate subtleties of non-differentiable functions in autodiff, and also proposing intensional derivatives, a new notion of derivatives, that enable us to formally prove the correctness of, and better understand the behaviour of, autodiff systems applied to non-differentiable functions.

Clarke subdifferential [START_REF] Clarke | Optimization and nonsmooth analysis[END_REF][START_REF] Clarke | Nonsmooth analysis and control theory[END_REF] and related notions have been favourite tools for studying the use of nondifferentiable functions in the context of autodiff and stochastic gradient descent [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning[END_REF][START_REF] Davis | Stochastic subgradient method converges on tame functions[END_REF][START_REF] Griewank | On Lipschitz optimization based on gray-box piecewise linearization[END_REF][START_REF] Kakade | Provably correct automatic sub-differentiation for qualified programs[END_REF][START_REF] Majewski | Analysis of nonsmooth stochastic approximation: The differential inclusion approach[END_REF]. Let f be an input program (or function) to be differentiated. Assume that f is locally Lipschitz continuous but possibly non-differentiable at some inputs. Kakade and Lee [START_REF] Kakade | Provably correct automatic sub-differentiation for qualified programs[END_REF] proposed a lineartime algorithm that correctly computes a subdifferential of f at x almost surely, for all inputs x, when f satisfies some qualification condition. Their work, however, could not provide the correctness of the current autodiff systems, because those systems do not use their algorithm. Bolte and Pauwels [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning[END_REF] presented a result closest to ours: standard autodiff algorithms correctly compute the standard derivative of f at x always, for almost all inputs x, if f is definable [START_REF] Van Den Dries | Geometric categories and o-minimal structures[END_REF]. To do so, they extended Clarke subdifferential to define a new notion of derivatives, called conservative fields, and showed that autodiff algorithms compute conservative fields and the fields coincide with the standard derivatives almost everywhere. We point out three key differences between these works and ours. First, they use highly advanced mathematical tools (e.g., variational analysis [START_REF] Rockafellar | Variational analysis[END_REF]). Thanks to those powerful tools, they could prove more results than ours, such as the almost-sure convergence of the stochastic gradient descent with conservative fields [START_REF] Bolte | Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning[END_REF], but they are less accessible than our work, which requires much simpler mathematics (probably at an undergraduate level) but still gives the correctness proof of autodiff systems. Second, subdifferentials and conservative fields are difficult to be generalised to higher-order derivatives, because they are defined in terms of a single set-valued function. In contrast, our intensional derivatives are defined in terms of a set of standard (i.e., singleton-valued) functions, and thus have a natural generalisation to higher-order derivatives. Lastly, different function classes are considered: those works apply to locally Lipschitz continuous functions with additional properties (e.g., definability), whereas ours applies to PAP functions. We point out that PAP functions include many non-locally-Lipschitz functions, such as discontinuous x ∈ R -→ 1[x > 0] and continuous x ∈ R -→ |x|; the opposite direction is also true (e.g., the λ-Cantor functions for λ ∈ (0, 1)).

The PAP property is similar to some other piecewise properties, such as piecewise smoothness [START_REF] Zhou | LF-PPL: A lowlevel first order probabilistic programming language for non-differentiable models[END_REF] which inspired PAP, and piecewise analyticity [START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF]. The PAP, however, differs from the others in a few ways: unlike piecewise smoothness, it allows piecewise functions to be defined on open subsets of R n (not just on R n ), but restricts them to be analytic (rather than smooth); unlike piecewise analyticity, it allows piecewise domains to be countably many (not just finitely many), but restricts them to be analytic (rather than unrestricted). Unlike prior works, we also give an in-depth study of the PAP property, such as its closedness under operations (e.g., composition) and its relationship to other properties (e.g., almost-everywhere differentiability). The property of almost-everywhere differentiability has been studied as well for programs and functions (that need not be related to programs). E.g., it is shown to hold for all programs in some programming languages [START_REF] Griewank | Evaluating derivatives: Principles and techniques of algorithmic differentiation[END_REF][START_REF] Mak | Densities of almost-surely terminating probabilistic programs are differentiable almost everywhere[END_REF], and for all piecewise smooth functions [START_REF] Zhou | LF-PPL: A lowlevel first order probabilistic programming language for non-differentiable models[END_REF]. We prove the property for all PAP functions and utilise it in proving that higher-order intensional derivatives agree with standard derivatives almost everywhere.

Recently and concurrently with this work, Bolte and Pauwels [START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF] studied some concepts and results similar to ours. They proposed a new class of functions and a new notion of derivatives, called elementary selections and selection derivatives, which roughly correspond to our PAP functions and intensional derivatives; and proved properties of those new functions and derivatives, which roughly correspond to our Propositions 8 to 11 and Theorem 12. Although having some similarities, our work and their work have three key differences, complementing each other. First, their work is applicable to a strictly smaller class of functions than ours, as any elementary selection is PAP (and locally Lipschitz) but not vice versa. Second, it considers selection derivatives of first order only, whereas our work considers intensional derivatives of higher orders as well. Third, their work provides some results not in our work (e.g., convergence of stochastic gradient descent with selection derivatives), and vice versa (e.g., the results in §2).

We conclude the section by discussing a few remarks on a notion of correctness for autodiff systems. First, there can be multiple different correctness conditions of autodiff systems and we do not claim that our correctness condition (Definition 1 or Corollary 13) is "the" gold standard. Rather we are just suggesting "a" correctness condition that can serve as a reasonable (possibly minimal) requirement for existing and future autodiff systems. Second, as important as the correctness of autodiff systems is the correctness of the applications built upon autodiff systems (e.g., gradient descent, variational inference, and Hamiltonian Monte Carlo), but the latter might not necessarily follow from the former. For example, consider an autodiff system that is correct in the sense of Corollary 13 (i.e., computes an intensional derivative), and a gradient descent algorithm that follows the "derivative", computed by the system, of an objective function f : R → R to minimise f . Suppose that f is given by f (x) = x2 if x = 1, and 1 if x = 1; the autodiff system computes df (x) = 2x if x = 1, and 0 if x = 1, as the "derivative" of f ; and the gradient descent starts at x = 1.1 Then, the gradient descent gets stuck at x = 1 forever since df (1) = 0, even though 1 is never a critical point of f . This example illustrates that the correctness of autodiff systems does not necessarily imply the correctness of gradient descents built upon those systems (where the latter correctness is given by that gradient descents should converge to Clarke critical points). 2 Nevertheless, the two notions of correctness discussed so far, one for autodiff systems and the other for applications using autodiff systems, address two separate issues and this paper is mainly about the former notion of correctness.

Broader Impact

This work focuses mainly on theoretical aspects of autodiff systems. In particular, we formally prove that the systems, though developed to handle differentiable functions, remain correct even when applied to non-differentiable functions. Our result justifies, at least in part, the current situation in machine learning, in which the systems are frequently applied to non-differentiable functions without much consideration to their correctness under such out-of-scope use cases. Other than the justification, this work does not present any other foreseeable societal consequence due to its theoretical nature.

A Comments on Results in §2

A.1 Comments on the proof of Proposition 1 First, we elaborate on our proof in Proposition 1 that g is continuous on (0, 1). Since g is continuous on (0, 1) \ C 1 by its construction, we only need to show that g is continuous on C 1 . Consider any x ∈ C 1 and > 0. It suffices to show that there is δ ∈ (0, x) such that

0 < |x -x | < δ =⇒ |g(x) -g(x )| = |g(x )| = g(x ) < . (1)
Let k > 0 be an integer with 2 -k < . Consider the set

S = {x ∈ (0, 1) \ C 1 | g(x ) ≥ 2 -k }.
By the construction of g, S is the union of some finitely many closed intervals in (0, 1) that do not contain x. (Note that each of those closed intervals is contained in an open interval removed at some k (≤ k)-th step of g's construction.) Hence,

δ = min inf x ∈S |x -x |, x
is positive. We now show that δ satisfies (1). Consider any

x with 0 < |x -x | < δ. If x ∈ C 1 , then g(x ) = 0. If x / ∈ C 1 , then x ∈ (0, 1) \ C 1 and
x / ∈ S by the definition of δ, and thus g(x ) < 2 -k < by the definition of S and k. Hence, (1) holds and this completes the proof.

Second, we elaborate on our proof in Proposition 1 that g • f is not differentiable on C 1/2 . Consider any x ∈ C 1/2 . It suffices to show that for any δ ∈ (0, x), there exist

x 1 , x 2 ∈ (x -δ, x + δ) \ {x} such that (g • f )(x) -(g • f )(x 1 ) x -x 1 = 0 and (g • f )(x) -(g • f )(x 2 ) x -x 2 > 1. (2)
Consider any δ ∈ (0, x). Since x ∈ C 1/2 is a limit point of C 1/2 , there exists x 1 ∈ (x-δ, x+δ)\{x} with x 1 ∈ C 1/2 . For this x 1 , the first equality in (2) holds, since (g • f )(C 1/2 ) = g(C 1 ) = {0}. To find x 2 , let k > 0 be an integer such that

d(k) = 1 2 • 1 2 k + 3 4 • 1 3 k < δ and 3 4 • 2 3 k < 1 2 . (3)
We claim that there exists x 2 ∈ (0, 1) such that

0 < |x -x 2 | ≤ d(k) and (g • f )(x 2 ) = 2 -k . (4)
If the claim holds, then

(g • f )(x) -(g • f )(x 2 ) x -x 2 ≥ 2 -k /d(k) (by (4) and (g • f )(x) = 0) = 2 -k 1 2 • 1 2 k + 3 4 • 1 3 k (by the equality in (3)) = 1 1 2 + 3 4 • 2 3 k > 1/ 1 2 + 1 2 = 1
(by the inequality in (3)), and thus the second equality in (2) holds. Hence, finding x 2 ∈ (0, 1) satisfying (4) completes the proof. We now show that such x 2 exists. Consider the situation right after the k-th step of C 1/2 's construction is performed. Then, the total length of the closed intervals that still remain is

1 - 1 2 • 1 3 1 • 2 0 + 1 3 2 • 2 1 + • • • + 1 3 k • 2 k-1 = 1 2 • 1 + 2 3 k ,
so the length of each of those closed intervals is 1 2 (2 -k + 3 -k ), since those closed intervals have the same length and there are 2 k such intervals. Due to this, and by the construction of C 1/2 , there is some open interval I that is removed exactly at the k-th step of C 1/2 's construction and satisfies

dist(x, I) ≤ 1 2 • 1 2 k + 1 3 k .
Let x 2 ∈ (0, 1) be the midpoint of I. By the construction of f and g, we have

(g • f )(x 2 ) = 2 -k .
Furthermore, since the length of I is 3 -k /2, we have

|x -x 2 | ≤ dist(x, I) + 1 2 • len(I) ≤ 1 2 • 1 2 k + 1 3 k + 1 4 • 1 3 k = d(k).
Hence, x 2 ∈ (0, 1) satisfies ( 4), and this concludes the proof.

Next, we make a remark on non-differentiable inputs of f , g, and g • f in the proof. One might guess that f should be non-differentiable exactly on C 1/2 , given that f maps (0, 1) \ C 1/2 onto (0, 1) \ C 1 in a linear way and maps C 1/2 onto C 1 in a non-smooth-looking way. Surprisingly, the guess is wrong: f is in fact non-differentiable only on a measure-zero subset of C 1/2 . On the other hand, g and g • f are non-differentiable exactly on C 1 and C 1/2 , respectively. The proof that g is non-differentiable on C 1 is similar to the above proof that g • f is non-differentiable on C 1/2 , and thus we omit it.

Finally, we connect the examples in the proof with our results in §3. Both f and g are shown to be non-PAP (Proposition 5). Hence, our results do not guarantee that g • f is PAP and so almost-everywhere differentiable. In fact, g • f is non-PAP, since g • f is not almost-everywhere differentiable.

A.2 Comments on the proof of Proposition 2

We explain how the counterexample in the proof does not contradict to our results in §3. The functions f and g are PAP (and thus g • f is so). Although g is undefined at 0, we can extend it to an intensional derivative dg ∈ ∂ • g such that dg is defined everywhere (even at 0) and coincides with g at all but countably many inputs. With such dg, the following version of the chain rule holds almost everywhere:

(g • f ) (x) = dg(f (x)) • f (x)
for almost all x ∈ (0, 1).

This is because we have the chain rule for intensional derivatives and and these intensional derivatives and standard derivatives coincide almost everywhere (Propositions 8 and 10).

A.3 Comments on the proof of Proposition 3

The functions f , g, and g • f in the proof do not contradict to our results. Neither f nor g is a PAP function (Proposition 5). Hence, our results do not guarantee the validity of our version of the chain rule for g • f .

B Comments on and Proofs for Results in §3

Let X , X f , X g ⊆ R n and Y ⊆ R m be arbitrary sets.

B.1 Comments on the proof of Proposition 5

We prove the following argument used in the proof of Proposition 5: the functions listed in the proof satisfy the sufficient condition (i) or (ii) mentioned in the proof.

First, consider (i). To show that a function h : X → R m satisfies (i) with k = 2, it suffices to show the claim that the set S = {x ∈ X | h is undefined or discontinuous at x} has positive measure. For the λ-Cantor function φ λ with λ ∈ (0, 1), S is a full measure subset of C λ due to the following: φ λ (x) = 1/(1 -λ) = 0 for almost all x ∈ C λ ; φ λ (x) = 0 for all x / ∈ C λ ; and C λ ⊂ (0, 1) has no interior. Since C λ has measure 1 -λ > 0, the claim holds for φ λ . For f in the proof of Proposition 1, S is a full measure subset of C 1/2 due to similar reasons. So the claim holds for f . For Volterra's function, S is known to have positive measure [START_REF] Gelbaum | Counterexamples in analysis[END_REF]Example 8.35]. So the claim holds for Volterra's function.

Next, consider (ii). Observe that the 1-Cantor function and g in the proof of Proposition 1 are both defined on (0, 1) ⊆ R and non-differentiable exactly on C 1 (for the non-differentiability of g, see §A.1). Since C 1 is uncountable, the two functions satisfy (ii) with k = 1. This completes the proof of the argument.

As a side note, we remark that Volterra's function V is more pathological than the λ-Cantor function φ λ for λ ∈ (0, 1), in that V is discontinuous on a set of positive measure even though V is differentiable everywhere and V is bounded. Contrast this with the fact that φ λ is also discontinuous on a set of positive measure, but φ λ is differentiable just almost everywhere, not everywhere. In fact, there even exists a more pathological function W : (0, 1) → R such that W is differentiable everywhere and W is bounded, but W is discontinuous almost everywhere [10, Exercise 5:5.5]. Certainly, W is an another example for Proposition 5: it is continuous and differentiable almost everywhere, but not PAP.

int(A) = i∈[I] int(A i ; R n ),
where int(A i ; R n ) denotes the largest open subset of R n that is included in A i . Definition 10 (Subinterior of Analytic Partition). Let A = {A i } i∈[I] be an analytic partition of X with I ∈ (Z >0 ∪ {∞}). Suppose that a subset X ⊆ X and a partition B = {B t } t∈[T ] of X satisfy the following conditions:

(i) T ∈ (Z >0 ∪ {∞}).
(ii) For all t ∈ [T ], B t is subanalytic. That is, for all t ∈ [T ], there exist J t , L t ∈ Z ≥0 and analytic functions g + t,j : X + t,j → R and g - t,l :

X - t,l → R over open domains X + t,j , X - t,l ⊆ R n (j ∈ [J t ], l ∈ [L t ]) such that: X - t,l is connected in R n and (g - t,l ) -1 ({0}) = X - t,l for all l ∈ [L t ]; and B t = j∈[Jt] (g + t,j ) -1 (R >0 ) ∩ l∈[Lt] (g - t,l ) -1 (R <0 ) . (5)
(iii) Let C t ⊆ R n be the set defined as follows:

C t = j∈[Jt] (g + t,j ) -1 (R >0 ) ∩ l∈[Lt] (g - t,l ) -1 (R ≤0 ) . Then, C = {C t } t∈[T ] is a finer partition of X than {A i } i∈[I] . That is, C is a partition of X , and for all t ∈ [T ], C t ⊆ A i for some i ∈ [I].
We call the set X a subinterior of A, and the partition B a subanalytic partition of X . We use subint(A) to denote the set of all subinteriors of A. Lemma 14. Let A = {A i } i∈[I] be an analytic partition of X with I ∈ (Z >0 ∪ {∞}). Then, subint(A) = ∅. Furthermore, for any X ∈ subint(A), the following hold:

(a) There is an analytic partition

B = {B t } t∈[T ] of X with T ∈ (Z >0 ∪ {∞}) and int(B) = X . (b) X ⊆ int(A) and X is open in R n . (c) X \ X is contained in some measure-zero set. (d) X \ int(A) is contained in some measure-zero set.
Proof. We first prove that subint(A) = ∅. Consider any i ∈ [I]. Since A i is analytic, there exist J i , L i ∈ Z >0 and analytic functions g + i,j :

X + i,j → R and g - i,l : X - i,l → R over open domains X + i,j , X - i,l ⊆ R n (j ∈ [J i ], l ∈ [L i ]) such that A i = j∈[Ji] (g + i,j ) -1 (R >0 ) ∩ l∈[Li] (g - i,l ) -1 (R ≤0 ) .
We use the following fact: any open set in R n is a union of countably many open balls in R n , thereby a union of countably many disjoint connected open sets in R n . For every l ∈

[L i ], since X - i,l is open in R n , there exists a partition {X - i, l,t l } t l ∈[∞] of X - i,l such that X - i, l,t l is connected and open in R n . For each t 1 , . . . , t Li ∈ [∞] Li , let B i, t1,...,t L i = j∈[Ji] (g + i,j ) -1 (R >0 ) ∩ l∈[Li] (g - i, l,t l ) -1 (R <0 ) C i, t1,...,t L i = j∈[Ji] (g + i,j ) -1 (R >0 ) ∩ l∈[Li] (g - i, l,t l ) -1 (R ≤0 )
where g - i, l,t l : X - i, l,t l → R denotes the restriction of g - i,l to X - i, l,t l . Here, if (g - i, l,t l ) -1 ({0}) = X - i, l,t l for some i, l, t l , then we set g - i, l,t l to the constant function -1 on the domain X - i, l,t l . Then, every g - i, l,t l is analytic on its connected open domain X - i, l,t l , and

(g - i, l,t l ) -1 ({0}) = X - i, l,t l . Finally, let X = i∈[I], t1,...,t L i ∈[∞] L i B i, t1,...,t L i B = {B i, t1,...,t L i | i ∈ [I], t 1 , . . . , t Li ∈ [∞] Li } C = {C i, t1,...,t L i | i ∈ [I], t 1 , . . . , t Li ∈ [∞] Li }.
Then, X is a subinterior of A, and B is a subanalytic partition of X , because of the following:

• B is a partition of X . • { i, t 1 , . . . , t Li | i ∈ [I], t 1 , . . . , t Li ∈ [∞] Li } is a countable set. • For all i ∈ [I] and t 1 , . . . , t Li ∈ [∞] Li , B i, t1,...,t L i is subanalytic. • C is a finer partition of X than A. This holds because {A i } i∈[I] is a partition of X , and {C i, t1,...,t L i } t1,...,t L i ∈[∞] L i is a partition of A i for all i ∈ [I]
, by its construction.

This completes the proof that subint(A) = ∅.

We now prove the remaining claims. Let X ∈ subint(A) and B = {B t } t∈[T ] be a subanalytic partition of X that satisfies the equations in Definition 10.

Proof of (a). By the definition of subanalytic partition, and since h(x) < 0 ⇐⇒ -h(x) > 0 for any function h and input x, B is an analytic partition of X with T ∈ (Z >0 ∪ {∞}). We argue that for any t ∈ [T ], B t is open in R n . Recall the equation ( 5):

B t = j∈[Jt] (g + t,j ) -1 (R >0 ) ∩ l∈[Lt] (g - t,l ) -1 (R <0 ) .
Since g + t,j : X + t,j → R and g - t,l : X - t,l → R are continuous, and R >0 and R <0 are open in R, we have that (g + t,j ) -1 (R >0 ) and (g - t,l ) -1 (R <0 ) are open in X + t,j and X - t,l , respectively, by the definition of continuity. Furthermore, since X + t,j and X - t,l are open in R n , we have that

(g + t,j ) -1 (R >0 ) and (g - t,l ) -1 (R <0 ) are open in R n as well. Since any finite intersection of open subsets is again open, B t is open in R n . Hence, int(B) = t∈[T ] int(B t ; R n ) = t∈[T ] B t = X .
Proof of (b). We continue the proof from (a). Since B t is open in R n , and B t ⊆ A i for some i ∈ [I] (by the definition of subanalytic partition), we have B t ⊆ int(A i ; R n ). From this, we obtain

X = t∈[T ] B t ⊆ i∈[I] int(A i ; R n ) = int(A).

Moreover, since any union of open sets is again open

, X = t∈[T ] B t is open in R n .
Proof. Let U = int(γ f ) ∩ int(γ g ), and consider any x ∈ U . Since x ∈ U and U is open in R n , we have D(f )(x) = D(g)(x) if both sides are well-defined. Indeed, they are well-defined by Lemma 15 with k = 1, since γ f and γ g are PAP representations of f and g, respectively. Lemma 18. Let f : X → Y be a PAP function. Then, for any intensional derivative df ∈ ∂ • f , there exists a PAP representation γ df of df such that df (x) = D(f )(x) for all x ∈ int(γ df ).

Proof. By the definition of ∂ • f , there exists a PAP representation γ f of f such that df = Dγ f . By Lemma 15 with k = 1, we have D(f )(x) = Dγ f (x) = df (x) for all x ∈ int(γ f ). Let γ df = Dγ f . Since df = Dγ f = γ df and γ f is PAP, γ df is a PAP representation of df . Moreover, by the definition of Dγ f , we have int(γ df ) = int(γ f ). Hence, the claim holds with γ df .

Definition 12 (Refinement of Representation). Let γ f = { A i , f i } i∈[I] be a representation of a function from X f to Y, and B = {B j } j∈[J] be a partition of X g . The refinement of γ f with B is defined by: refine(γ

f ; B) = { A i ∩ B j , f i } i,j ∈[I]×[J] .
Moreover, for any representation γ g = { C l , g l } l∈[L] of a function from X g to Z, the refinement of γ f with γ g is defined by: refine(γ f ; γ g ) = refine(γ f ; {C l } l∈[L] ).

(A i ∩ B j ) = ( i∈[I] A i ) ∩ ( j∈[J] B j ) = X f ∩ X g ,
γ is a representation of f | X f ∩Xg . Finally, we obtain the last claim as follows:

int(γ ) = i,j ∈[I]×[J] int(A i ∩ B j ; R n ) = i,j ∈[I]×[J] int(A i ; R n ) ∩ int(B j ; R n ) = i∈[I] int(A i ; R n ) ∩ j∈[J] int(B j ; R n ) = int(γ) ∩ int(B).
For the second equality, we use the following fact: int(S 1 ∩ S 2 ; X) = int(S 1 ; X) ∩ int(S 2 ; X) for any S 1 , S 2 ⊆ X. Lemma 20. Let f : X → Y be a PAP function. Consider any PAP representation γ of f , and any subinterior X ∈ subint(γ). Then, X ⊆ X is open in R n and X \ X is contained in a measure-zero set. Moreover, for all k ∈ Z ≥0 , D (k) (f | X ) is a total function on X , and there exists a PAP representation γ k D of D (k) (f | X ) such that int(γ k D ) = X . Proof. Let k ∈ Z ≥0 . By Lemma 14(b) and 14(c), X ⊆ int(γ) ⊆ X is open in R n and X \ X is contained in a measure-zero set. This proves the first claim. Since X ⊆ int(γ), Lemma 15 implies that D (k) (f )(x) exists for all x ∈ X . Since X is open in R n , D (k) (f | X )(x) = D (k) (f )(x) for all x ∈ X . This proves the second claim that D (k) (f | X ) is a total function on X .

We now prove the last claim. By Lemma 14(a), there exists an analytic partition B = {B j } j∈[J] of X such that J ∈ (Z >0 ∪ {∞}) and int(B) = X . Let γ = refine(γ; B). By Lemma 19, γ is a PAP representation of f | X with int(γ ) = int(γ) ∩ int(B) = X . Consider

γ k D = D (k) (γ ).
We show that it satisfies the last claim. Since f | X : X → Y is a PAP function with a PAP representation γ , Lemma 15 implies that D (k) (f | X )(x) = D (k) (γ ) (x) = γ k D (x) for all x ∈ int(γ ) = X . Hence, γ k D is a representation of D (k) (f | X ). The rest of the claim also holds as follows: γ k D is PAP since γ is PAP; and int(γ k D ) = int(γ ) = X by the definition of D(γ ). Lemma 21. Let f : X → Y be a PAP function and X ⊆ X be a set described in Lemma 20, which has full measure in X . Consider any k ∈ Z ≥0 . Then, for any df k ∈ ∂ k ). From this, we obtain the desired claim:

df k (x) = D (k) (f )(x)
for all x ∈ int(γ k d ) ∩ X .

Figure 1 :

 1 Figure 1: The graphs of φ 1 , f , and g that are described in the proof of Proposition 1.

B. 2

 2 Interior and subinterior of analytic partition Definition 9 (Interior of Analytic Partition). Let A = {A i } i∈[I] be an analytic partition of X . The interior of A, int(A), is defined by the following open subset of R n :

Lemma 19 .

 19 Let f : X f → Y be a PAP function, γ be a PAP representation of f , andB = {B j } j∈[J] be an analytic partition of X g with J ∈ (Z >0 ∪ {∞}). Let γ = refine(γ; B). Then, γ is a PAP representation of f | X f ∩Xg with int(γ ) = int(γ) ∩ int(B). Proof. Let γ = { A i , f i } i∈[I] . Since γ is PAP and B is an analytic partition, {A i ∩ B j } i,j ∈[I]×[J] is an analytic partition. Also, since [J] is countable, [I] × [J] is also countable. Thus, γ is PAP. Since i,j ∈[I]×[J]

1 •f 1 d) 1 d and γ k- 1 D 1 d) 1 d) 1 d) ∩ X . Now let γ k d = refine(γ k d ; γ k- 1 d).

 11111111 • f , there exists a PAP representation γ k d of df k such thatdf k (x) = D (k) (f )(x) for all x ∈ int(γ k d ) ∩ X .Proof. The proof proceeds by induction on k. For k = 0, we havedf k = D (k) (f ) = f . So any PAP representation γ k d of df k = f satisfies the claim. Now suppose k > 0. By the definition of ∂ k • f , there exists df k-1 ∈ ∂ k-such that df k ∈ ∂ • (df k-1 ). We construct the desired PAP representation γ k d as follows. First, focus on df k-1 ∈ ∂ k-1 • f . By the induction hypothesis on k -1 for df k-1 , there exists a PAP representation γ k-1 d of df k-1 such that df k-1 (x) = D (k-1) (f )(x) for all x ∈ int(γ k-1 d ) ∩ X .By Lemma 20, D (k-1) (f | X ) is a total function on X and there exists a PAP representationγ k-1 D of D (k-1) (f | X ) such that int(γ k-1 D ) = X . Since X is open in R n by Lemma 20, D (k-1) (f ) = D (k-1) (f | X ) over X . Combining the two results gives that df k-1 (x) = D (k-1) (f | X )(x) for all x ∈ int(γ k-∩ int(γ k-1 D ),where γ k-are PAP representations of df k-1 and D (k-1) (f | X ), respectively. By Lemma 17 applied to this result, we obtainD(df k-1 )(x) = D (k) (f | X )(x) for all x ∈ int(γ k-∩ int(γ k-1 D ). Since D (k) (f | X ) = D (k) (f ) over X (as X is open in R n ), and int(γ k-1 D ) = X , we have D(df k-1 )(x) = D (k) (f )(x) for all x ∈ int(γ k-∩ X .Next, focus on df k ∈ ∂ • (df k-1 ). By Lemma 18 applied to df k , there exists a PAP representationγ k d of df k such that df k (x) = D(df k-1 )(x) for all x ∈ int(γ k d ).Combining the last two equations, we obtaindf k (x) = D (k) (f )(x) for all x ∈ int(γ k d ) ∩ int(γ k-By Lemma 19 applied to γ k d , we have that γ k d is a PAP representation of df k with int(γ k d ) = int(γ k d ) ∩ int(γ k-1 d

Proposition 22 .

 22 Let f : X → Y be a PAP function and k ∈ Z ≥0 . Then, any k-th order intensional derivative df k ∈ ∂ k• f satisfies the following:df k (x) = D (k) (f )(x) for almost all x ∈ X .Proof. The claim follows from Lemma 21 and the following: X and int(γ k d ) described in Lemma 21 have the full measure in X , by Lemma 21 and Lemma 14(d).

34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

We thank an anonymous reviewer for coming up with this example.

On the other hand, we conjecture that for any PAP and locally Lipschitz f : R n → R, if a gradient descent follows an intensional derivative of f and starts at randomly chosen initial points, then it would be correct almost surely. A partial result confirming the conjecture was proven recently in[START_REF] Bolte | A mathematical model for automatic differentiation in machine learning[END_REF], concurrently with this work.

Acknowledgments and Disclosure of Funding

We thank anonymous reviewers for their insightful and constructive comments. Lee, Yang, and Yu were supported by the Engineering Research Center Program through the National Research Foundation of Korea (NRF) funded by the Korean Government MSIT (NRF-2018R1A5A1059921), and also by Next-Generation Information Computing Development Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT (2017M3C4A7068177). Rival was supported by a Facebook gift and by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 825492).

Proof of (c). For this, we use the following theorem [START_REF] Mityagin | The zero set of a real analytic function[END_REF]: for any open connected U ⊆ R n and analytic function f : U → R, the zero set {x ∈ U | f (x) = 0} of f is either U or contained in some measure-zero set. Observe that

Since each g - t,l is analytic, and not everywhere-zero, on its connected open domain X - t,l (by the definition of subanalytic partition), the above theorem and equation imply that (g - t,l ) -1 ({0}) is contained in some measure-zero set. Since any countable union of measure-zero sets has measure zero, X \ X is contained in some measure-zero set.

Proof of (d). This follows immediately from (b) and (c).

B.3 Proofs of Proposition 4 and Proposition 8 (part I)

We remind the reader that the notation D(f )(x) means the standard derivative of f at x. Definition 11 (Interior of PAP Representation). Let γ = { A i , f i } i∈[I] be a PAP representation from X to Y. The interior and subinterior of γ are defined by:

). Lemma 15. Let f : X → Y be a PAP function, γ be a PAP representation of f , and k ∈ Z ≥0 . Then, for all x ∈ int(γ), f has the k-th order standard derivative at x. Furthermore, the derivative agrees with the k-th order intensional derivative of γ at x:

where F (k) denotes the k-time composition of the operator F . Proof. Consider any x ∈ int(γ). By the definition of int(γ), we have x ∈ int(A i ; R n ) for some i ∈ [I]. So there exists an open neighbourhood U ⊆ R n of x such that U ⊆ A i . Since γ is a representation of f and U ⊆ A i , we have f = f i on U for the i-th component function of γ. Now focus on f i . Since f i is analytic on U (due to γ being PAP), f i is infinitely differentiable on U and, in particular, has the k-th order standard derivative at x, namely D (k) (f i )(x). By the definition of intensional derivative,

Proposition 16. Let f : X → Y be a PAP function and k ∈ Z ≥0 . Then, f has the k-th order standard derivative almost everywhere. Moreover, the first-order standard derivative Df agrees with any first-order intensional derivative df ∈ ∂ • f almost everywhere. Proof. By Lemma 14(d), the interior of any PAP representation of f has the full measure in X . Hence, Lemma 15 implies the first claim. For the second claim, let df ∈ ∂ • f . By the definition of ∂ • f , there exists a PAP representation γ of f such that df = Dγ . Applying Lemma 15 to f , γ, and k = 1 gives the second claim, since int(γ) has the full measure in X .

B.4 Proof of Proposition 8 (part II)

Lemma 17. Let f : X f → Y and g : X g → Y be PAP functions, and γ f and γ g be their PAP representations. If f (x) = g(x) for all x ∈ int(γ f ) ∩ int(γ g ), then D(f )(x) = D(g)(x) for all x ∈ int(γ f ) ∩ int(γ g ), where both sides are well-defined for each x.

then it could be uncountable. Proof. Suppose n = 1. Recall the following two well-known results: (i) if g : U → R is an analytic function on an open interval U ⊆ R and is not everywhere-zero, then its zero set Z g = {x ∈ U | g(x) = 0} contains none of the limit points of Z g [25, Corollary 1.2.7]; (ii) if X is a second-countable space and S ⊆ X contains none of the limit points of S, then S is countable. Since R is second-countable, every g satisfying the assumption of (i) has at most countably many zeros. Now return to our claim. By the statement and proof of Lemma 14(c) and Lemma 15, there are countably many analytic functions {g j : U j → R} j defined over connected open subsets of R, such that every g j is not everywhere-zero and N f,k ⊆ j Z gj . Since any connected open subset of R is an open interval, g j satisfies the assumption of (i), and thus each Z gj is countable by the above result. Hence, N f,k is countable, since a countable union of countable sets is countable.

Suppose n > 1. Consider f : R 2 → R defined by f (x) = |x 1 -x 2 |, and k = 1. Then, f is PAP, since the following is a PAP representation of f :


Alinoe Lavillaureix
email: alinoe.lavillaureix@chu-rennes.fr

Gauthier Foulon

Erika Launay

Marc-Antoine Belaud-Rotureau

Ronan Thibault

Cécile Lambe

Dominique Aussel

Laurent Pasquier

Sylvie Odent

Alexis Arnaud

Alinoë Lavillaureix

Gauthier

Marc- Antoine Belaud-Rotureau (

Edouard Habonimana

Alain Dabadie

Dr Alinoë Lavillaureix

Keywords: Antenatal finding of 16q24.1 duplication including FOXF1, revealing an autosomal dominant familial pathology with congenital short bowel, malrotation and renal abnormalities

come

patients or their parents (legal representatives of minor patients) according to the Declaration of Helsinki and the national legal regulations. Patients with congenital short-bowel syndrome (CSBS) are born with a substantial shortening of the small intestine, and malrotation of the small bowel is always present. Patients with CSBS develop intestinal failure and malabsorption, requiring long term home parenteral nutrition (PN). CSBS was first described by Hamilton et al and it is thought to have a genetic cause [START_REF] Hamilton | Short small intestine associated with malrotation: a newly described congenital cause of intestinal malabsorption[END_REF]. Mutations in CLMP and FLNA cause recessive and X-linked forms of CSBS, respectively [START_REF] Van Der Werf | Congenital Short Bowel Syndrome: from clinical and genetic diagnosis to the molecular mechanisms involved in intestinal elongation[END_REF]. We describe the antenatal finding of a 16q24.1 duplication including FOXF1, revealing an autosomal dominant familial pathology with CSBS, malrotation and renal abnormalities.

Family tree is described in figure 1. The proband (III-2) is the second male child of a nonconsanguineous couple. He was antenatally diagnosed with 16q24.1 duplication and has intestinal malrotation, CSBS, unilateral kidney duplicity with cysts.

His mother (II-2) presented with volvulus at three weeks of age, and CSBS (65cm) with a complete intestinal malrotation diagnosed during the laparotomy. She had fifteen months of PN. She also had kidney abnormalities, with unilateral renal duplication, kidney cysts, several episodes of pyelonephritis and renal lithiasis in childhood and adulthood. During the pregnancy, antenatal ultrasound examinations in the second trimester showed high suspicion of intestinal malrotation and kidney duplication. The possibility of an autosomal dominant pathology inherited from the mother (II-2) was explained to the parents, who accepted an amniocentesis. Array-CGH analysis performed on DNA obtained from amniotic liquid revealed heterozygous 16q24.1 duplication (768 kb) including FOXF1. The variant nomenclature, according to ISCN 2016 [START_REF]International Standing Committee on Human Cytogenomic Nomenclature[END_REF], was 46,XY.arr[GRCh37] 16q24.1(86220144_86988149)x3. This duplication, considered pathogenic, was inherited from the mother.

A c c e p t e d m a n u s c r i p t

The child was born at 39 weeks' gestation with normal birth parameters: weight 3075g (25th percentile), length 50cm (52th p), head circumference 35,3cm (66th p). The meconium passed within 24 hours after birth. He was exclusively breastfed. Abdominal ultrasonography at day five suspected an intestinal malrotation as mesenteric artery was on the right of mesenteric vein without any sign of volvulus, and found left kidney nephromegaly with pyelic duplication and multiple bilateral cysts. CSBS was suspected because of diarrhea, familial history and genetic findings. At two months old, height was 57cm, weight 4kg, and laparotomy confirmed incomplete 180° rotation and CSBS with normal ileocecal valve. A Ladd band was resected. Repositioning of the intestine and mesentery, and an appendectomy were performed. Small bowel length (SBL) was 85 cm, 41% of the mean estimated SBL for height and age, as a length superior to 165cm was expected (mean estimated SBL: 207 cm; 95% CI: [165 -250]) [START_REF] Struijs | Establishing norms for intestinal length in children[END_REF]. Prolonged PN was provided via central venous catheter. At two years old, height and weight development were normal with partial home PN maintained.

Cognitive skills and emotional and social behaviors were consistent with age. During the first year, he had two pyelonephritis and has a follow up with a nephropediatrician.

His older brother (III-1) has no digestive symptoms and was not tested. A maternal uncle (II-3) without digestive or renal symptoms was found to be negative for the duplication. The younger brother III-3 was tested after birth, he doesn't carry the familial duplication, he has no digestive symptoms at six months old. The maternal uncle (II-4) had diarrhea and malabsorption with long term PN during his first year and chronic abdominal pain afterwards.

He had a unilateral nephrectomy due to kidney damage associated with recurrent pyelonephritis and renal dysplasia. Unfortunately he could not be informed of the genetic disease to be tested.

The familial duplication was also confirmed in the symptomatic maternal grandmother (I-4); she was diagnosed with intestinal malrotation at age 62, during a pancreatitis surgery. She A c c e p t e d m a n u s c r i p t probably had CSBS, as she suffered from chronic diarrhea with malabsorption and failure to thrive in infancy. She had multiple episodes of pyelonephritis and developed chronic interstitial nephropathy by renal dysplasia, and had undergone a renal transplantation at the age of 31. After the age of 50, she had recurrent episodes of acute pancreatitis, with six hospitalisations and no etiology was found even though extensive tests were performed.

The dorsal mesentery is important in generating the left-right asymmetry that allows rotation of the midgut during embryological development to take place [START_REF] Martin | Review of genetic factors in intestinal malrotation[END_REF]. Point mutations and genomic deletions of FOXF1, a key gene in the establishment of the dorsal mesentery, are associated with intestinal malrotation and CSBS has been reported in one case [START_REF] Stankiewicz | Genomic and Genic Deletions of the FOX Gene Cluster on 16q24.1 and Inactivating Mutations of FOXF1 Cause Alveolar Capillary Dysplasia and Other Malformations[END_REF]. These patients have a severe developmental lung abnormality, alveolar capillary dysplasia with misalignment of pulmonary veins (ACD/MPV) causing early death.

16q24.1 duplications of different sizes encompassing FOXF1 have been described in four unrelated families [START_REF] Dharmadhikari | Molecular and clinical analyses of 16q24.1 duplications involving FOXF1 identify an evolutionarily unstable large minisatellite[END_REF] without pulmonary problems. Interestingly in one family, with duplication similar in size and genomic location to the one we have identified, the daughter, mother and maternal grandfather presented with malrotation; the daughter also had short bowel. In the other families with larger duplications, the patients had developmental delay but no significant gastrointestinal problems or malrotation are specified. A 1.5 Mb de novo duplication on 16q24 involving FOXF1 has been described more recently in one patient presenting with intestinal malrotation, mild intellectual disability, short stature and pulmonary artery stenosis [START_REF] Salehi Karlslätt | Rare copy number variants contribute pathogenic alleles in patients with intestinal malrotation[END_REF].

Pathogenicity of genomic duplications is often not explained by changes in gene dosage, but can be linked to the formation of new chromatin domains [START_REF] Franke | Formation of new chromatin domains determines pathogenicity of genomic duplications[END_REF] with changes in the structure and function of topologically associated domains (TADs). TADs are chromosomal regions with an elevated frequency of internal chromatin interactions, such as interactions between genes A c c e p t e d m a n u s c r i p t and their distal regulatory elements. For example, duplications within TADs can increase interactions between (duplicated) regulatory elements and their target genes, which can cause changes in gene expression and consequently disease.

Reinterpretation of the familial history combined with the genetic findings during the pregnancy led to close surveillance of the proband after birth. It also allowed for the parents to be informed of the increased risk of volvulus and CSBS in their child. Parenteral nutrition was started before the laparoscopic CSBS confirmation, so it permitted early care and avoided diagnostic delay of this rare condition. The mother also agreed to resume medical nutrition follow-up, her digestive symptoms improved and she had no renal lithiasis since supplementations.

These findings allowed for appropriate genetic counseling to be provided to the family; as prior to the diagnosis during the second pregnancy, the parents were not aware of the 50% risk of recurrence of the 16q24.1 duplication and CSBS transmission. The parents did not ask for prenatal diagnosis for the third pregnancy, but the child (III-3) was tested shortly after birth, he doesn't carry the familial duplication and has no digestive symptoms.

Array-CGH could be recommended for all patients with CSBS, as the prevalence of this condition is unknown.

Funding

A

  c c e p t e d m a n u s c r i p t This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors. Disclosure of interest: The authors declare that they have no competing interest. Authorship Conception and design of study: AL, EL. Acquisition of data or analysis and interpretation of data: AL, GF, EL, MB, RT, CL, DA, LP, SO, AA, EH, AD, SJ Drafting of manuscript: AL, AD, SJ. Critical revision and final approvement: AL, GF, EL, MB, RT, CL, DA, LP, SO, AA, EH, AD, SJ Data Availability Statement : The 16q24.1 duplication and the associated phenotype have been submitted to the DECIPHER database at https://decipher.sanger.ac.uk/, (ID LDC367088). Further data supporting the findings of this study are available from the corresponding author upon reasonable request.

  .1 duplication; Malrotation; Short Bowel Syndrome; Renal dysplasia; Renal Insufficiency; A c c e p t e d m a n u s c r i p t

Figure 1 :

 1 Figure 1: Family tree

Figure 1 A c c e p t e d m a n u s c r i p t

 1 Figure 1

ACKNOWLEDGEMENTS

The authors are grateful to the members of the family who participated in this study. Clinical data and samples were obtained with informed consent of the

Declaration of interests

☒ The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

☐The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: