On Correctness of Automatic Differentiation for Non-Differentiable Functions

Introduction

Automatic differentiation or autodiff is one of the key technologies behind the dramatic progress of deep learning in recent years . 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 . Effective autodiff systems have been developed for popular programming languages . They have enabled the development of sophisticated models and algorithms in machine learning that, in particular, involve deep neural networks .

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.

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 :

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.

If $f$ and $g$ are differentiable almost everywhere and continuous, then $g\circ f$ should be differentiable almost everywhere.

A rationale for the claim goes as follows. In order for $g\circ 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:

There exist functions $f:{(0,1)}\to{(0,1)}$ and $g:{(0,1)}\to{}$ such that $f$ and $g$ are differentiable almost everywhere and continuous, but $g\circ f$ fails to be almost-everywhere differentiable.

Returning to the proof, let $f$ be the inverse of the homeomorphism $F\,{:}\,{(0,1)}\,{\to}\,{(0,1)}$ defined by $F(x)\,{=}\,\frac{1}{2}(\phi_{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)}\to$ 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}\cdot[1-(y-(r_{i}+l_{i})/2)^{2}/((r_{i}-l_{i})/2)^{2}]$ ($i\in[2^{k-1}]$); and define $g$ over $C_{1}$ as $g(y)=0$. See Figure 1 for the graphs of $\phi_{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 as $k\to\infty$, and $g(C_{1})=\{0\}$ (see Appendix A for the details). Hence, $g\circ f$ is continuous. Note that $f$ is even Lipschitz continuous. To prove this, observe that $f$ can be constructed similarly to $\phi_{1/2}$, and repeat the proof of the Lipschitz continuity of $\phi_{1/2}$ .

We now show that $f$ and $g$ are differentiable almost everywhere, but $g\circ f$ is not. First, since $f$ is Lipschitz continuous, it is differentiable almost everywhere by Rademacher’s theorem [41, Theorem 2.2.4]. Next, since $g$ is differentiable on ${(0,1)}\,\setminus C_{1}$ by its construction, it is differentiable almost everywhere (as $C_{1}$ has measure ). Lastly, $g\circ 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\to\infty$; $g(C_{1})=\{0\}$; and $f$ is a homeomorphism with $f(C_{1/2})=C_{1}$ (see Appendix A for the details). ∎

If $f$, $g$, and $g\circ f$ are differentiable almost everywhere and continuous, then the standard chain rule for $g\circ f$ should hold almost everywhere. In particular, if $f,g:{(0,1)}\to{(0,1)}$, then $(g\circ f)^{\prime}(x_{0})=g^{\prime}(f(x_{0}))\cdot f^{\prime}(x_{0})$ for almost all $x_{0}\in{(0,1)}$.

Note that all of $f$, $g$, and $g\circ 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\circ 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 almost-everywhere differentiability of $f$, $g$, and $g\circ f$ does not stop $g^{\prime}(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:

There exist functions $f,g:{(0,1)}\to{(0,1)}$ such that $f$, $g$, and $g\circ f$ are differentiable almost everywhere and continuous, but it is not that $g^{\prime}(f(x))$ is defined for almost all $x\in{(0,1)}$.

Let $f(x)=1/2$ and $g(y)={\rm ReLU}(y-1/2)+1/2$. Then, $(g\circ f)(x)=1/2$. Certainly, $f$, $g$, and $g\circ f$ are differentiable almost everywhere and Lipschitz continuous. But, $g$ is not differentiable at $f(x)=1/2$ for all $x\in(0,1)$. So, it is not that $g^{\prime}(f(x))$ is defined for almost all $x\in(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.

The functions $\mathit{df}$ and $\mathit{dg}$ in the claim are the extensions of $f^{\prime}$ and $g^{\prime}$ that set $\mathit{df}(x)$ and $\mathit{dg}(y)$ to arbitrary values whenever $f^{\prime}(x)$ and $g^{\prime}(y)$ are undefined. The chain rule in the claim is phrased in terms of these extensions $\mathit{df}$ and $\mathit{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:

There exist functions $f,g:{(0,1)}\to{(0,1)}$ such that $f$, $g$, and $g\circ f$ are differentiable almost everywhere and continuous, but for some measurable subset $A\subseteq{(0,1)}$ with non-zero measure, they satisfy the following property: $f^{\prime}(x)=0$ and $(g\circ f)^{\prime}(x)\neq 0$ for all $x\in A$.

Consider the function $f$ in the proof of Proposition 1. Let $g$ be the $1$-Cantor function $\phi_{1}$. Then, $g\circ f$ is the $(1/2)$-Cantor function $\phi_{1/2}$. We already showed $f$ is differentiable almost everywhere and even Lipschitz continuous. Since $g$ and $g\circ 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\subseteq C_{1/2}$ with the desired properties. Since $C_{1/2}$ has measure $1/2$, it suffices to prove $f^{\prime}(x)=0$ and $(g\circ f)^{\prime}(x)=2$ for almost all $x\in C_{1/2}$. The claim indeed holds due to the following: $f$ and $g\circ f$ are Lipschitz, so absolutely continuous; $f^{\prime}(x)=2$ and $(g\circ f)^{\prime}(x)=0$ for all $x\notin C_{1/2}$; $f^{\prime}(x)\geq 0$ and $(g\circ f)^{\prime}(x)\leq 2$ for all $x\in C_{1/2}$ whenever these derivatives exist; and $C_{1/2}$ has measure $1/2$. For the details, see [8, Example 2.3.2] and . ∎

The proposition implies the third claim is doomed. The claim says that $\mathit{df}(x_{0})=f^{\prime}(x_{0})$ and $(g\circ f)^{\prime}(x_{0})=\mathit{dg}(f(x_{0}))\cdot\mathit{df}(x_{0})$ for almost all $x_{0}\in A$. But both equalities cannot hold simultaneously: if they do, by Proposition 3, $(g\circ f)^{\prime}(x_{0})=\mathit{dg}(f(x_{0}))\cdot\mathit{df}(x_{0})=\mathit{dg}(f(x_{0}))\cdot f^{\prime}(x_{0})=\mathit{dg}(f(x_{0}))\cdot 0=0,$ but the same proposition also entails $(g\circ f)^{\prime}(x_{0})\neq 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:

A representation $\gamma=\{\langle A^{i},f^{i}\rangle\}_{i\in[I]}$ from $\mathcal{X}$ to $\mathcal{Y}$ is piecewise analytic under analytic partition (in short, PAP) if and only if $\{A^{i}\}_{i\in[I]}$ is an analytic partition of $\mathcal{X}$ and $f^{i}$ is analytic over its domain $\mathcal{X}^{i}$ for all $i\in[I]$.

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).

All PAP functions are differentiable almost everywhere.

The proof extends the one for a similar result in . 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 . 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\in\mathcal{X}$, then $x$ belongs to the zero set of some $g_{j}$. For the details, see Appendix B.3. ∎

There is a continuous almost-everywhere differentiable yet non-PAP function.

Nearly all the requirements for $D\gamma$ to be a PAP representation directly follow from the fact that $\gamma$ 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]. ∎

By Proposition 6, only PAP functions live in $\partial_{\bullet}{f}$. Thus, we can also take intensional derivatives of functions in $\partial_{\bullet}{f}$. We push this observation further and define higher-order intensional derivatives:

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\in\mathcal{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 $\mathit{df}^{k}\in\partial_{\bullet}^{{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 $\mathit{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. ∎

Since $f$ and $g$ are PAP, they have PAP representations $\gamma_{f}=\{\langle A^{i},f^{i}\rangle\}_{i\in[I]}$ and $\gamma_{g}=\{\langle B^{j},g^{j}\rangle\}_{j\in[J]}$. Define their composition as follows: $\gamma_{g}\circ\gamma_{f}=\{\langle C^{\langle i,j\rangle},g^{j}\circ f^{i}\rangle\}_{\langle i,j\rangle\in[I]\times[J]}$ where $C^{\langle i,j\rangle}=\{x\in\mathcal{X}\mid x\in A^{i}\land f^{i}(x)\in B^{j}\}$. Then, $\gamma_{g}\circ\gamma_{f}$ is a representation of $g\circ f$. Also, it is PAP as the composition of analytic functions is analytic [25, Proposition 2.2.8]. Thus, $g\circ f$ is PAP. ∎

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},\ldots,x_{N}$ and has the following syntax for programs: $e\,::=\,{c}\,\mid\,{x}_{i}\,\mid\,\accentset{\rule{2.79996pt}{0.8pt}}{\mathtt{f}}(e_{1},\ldots,e_{n})\,\mid\,\mathtt{if}~{}(e_{1}>0)~{}e_{2}~{}e_{3}.$

\begin{array}[]{@{}c@{}}\llbracket{c}\rrbracket v=c,\qquad\llbracket{x_{i}}\rrbracket v=v_{i},\qquad\llbracket{\accentset{\rule{2.79996pt}{0.8pt}}{\mathtt{f}}(e_{1},\ldots,e_{n})}\rrbracket v={\mathtt{f}}(\llbracket{e_{1}}\rrbracket v,\ldots,\llbracket{e_{n}}\rrbracket v),\\[3.00003pt] \llbracket{\mathtt{if}~{}(e_{1}>0)~{}e_{2}~{}e_{3}}\rrbracket v=\text{if }(\llbracket{e_{1}}\rrbracket v>0)\text{ then }\llbracket{e_{2}}\rrbracket v\text{ else }\llbracket{e_{3}}\rrbracket v.\end{array}

\begin{array}[]{@{}c@{}}\llbracket{c}\rrbracket^{\nabla}\;\!\!v=\vec{0}_{1\times N},\quad\llbracket{\accentset{\rule{2.79996pt}{0.8pt}}{\mathtt{f}}(e_{1},\ldots,e_{n})}\rrbracket^{\nabla}\;\!\!v=(\mathchoice{\accentset{\displaystyle\text{\smash[b]{\raisebox{-6.24301pt}{\widetildesym}}}}{D}}{\accentset{\textstyle\text{\smash[b]{\raisebox{-6.24301pt}{\widetildesym}}}}{D}}{\accentset{\scriptstyle\text{\smash[b]{\raisebox{-4.37012pt}{\widetildesym}}}}{D}}{\accentset{\scriptscriptstyle\text{\smash[b]{\raisebox{-3.1215pt}{\widetildesym}}}}{D}}\mathtt{f})(\llbracket{e_{1}}\rrbracket v,\ldots,\llbracket{e_{n}}\rrbracket v)\cdot[\llbracket{e_{1}}\rrbracket^{\nabla}\;\!\!v;\,\ldots;\,\llbracket{e_{n}}\rrbracket^{\nabla}\;\!\!v],\\[3.00003pt] \llbracket{x_{i}}\rrbracket^{\nabla}\;\!\!v\,{=}\,[\vec{0}_{(i-1)\times 1};\vec{1}_{1\times 1};\vec{0}_{(N-i)\times 1}]^{\top}\!\!,\ \;\llbracket{\mathtt{if}\,(e_{1}{>}0)\,e_{2}\,e_{3}}\rrbracket^{\nabla}\;\!\!v\,{=}\,\text{if}\,(\llbracket{e_{1}}\rrbracket v{>}0)\,\text{then}\,{\llbracket{e_{2}}\rrbracket^{\nabla}\;\!\!}v\text{ else}\,{\llbracket{e_{3}}\rrbracket^{\nabla}\;\!\!}v.\end{array}

If \mathchoice{\accentset{\displaystyle\text{\smash[b]{\raisebox{-6.24301pt}{\widetildesym}}}}{D}}{\accentset{\textstyle\text{\smash[b]{\raisebox{-6.24301pt}{\widetildesym}}}}{D}}{\accentset{\scriptstyle\text{\smash[b]{\raisebox{-4.37012pt}{\widetildesym}}}}{D}}{\accentset{\scriptscriptstyle\text{\smash[b]{\raisebox{-3.1215pt}{\widetildesym}}}}{D}}\mathtt{f}\in\partial_{\bullet}{{\mathtt{f}}} for all primitive functions $\accentset{\rule{2.79996pt}{0.8pt}}{\mathtt{f}}$, then $\llbracket{e}\rrbracket^{\nabla}\;\!\!\in\partial_{\bullet}{\llbracket{e}\rrbracket}$ for all programs $e$.

Related Work and Discussion

Autodiff has a long history with a large body of literature . Its community has been aware of some issues with non-differentiable functions [20, 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 . 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.

Recently and concurrently with this work, Bolte and Pauwels 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, 9, 10, 11 and 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).

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.

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).

References

Appendix A Comments on Results in §2

First, we elaborate on our proof in Proposition 1 that $g$ is continuous on $(0,1)$. Since $g$ is continuous on $(0,1)\setminus C_{1}$ by its construction, we only need to show that $g$ is continuous on $C_{1}$. Consider any $x\in C_{1}$ and $\epsilon>0$. It suffices to show that there is $\delta\in(0,x)$ such that

Let $k>0$ be an integer with $2^{-k}<\epsilon$. Consider the set

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^{\prime}(\leq k)$-th step of $g$’s construction.) Hence,

is positive. We now show that $\delta$ satisfies (1). Consider any $x^{\prime}$ with $0<|x-x^{\prime}|<\delta$. If $x^{\prime}\in C_{1}$, then $g(x^{\prime})=0$. If $x^{\prime}\notin C_{1}$, then $x^{\prime}\in(0,1)\setminus C_{1}$ and $x^{\prime}\notin S$ by the definition of $\delta$, and thus $g(x^{\prime})<2^{-k}<\epsilon$ 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\circ f$ is not differentiable on $C_{1/2}$. Consider any $x\in C_{1/2}$. It suffices to show that for any $\delta\in(0,x)$, there exist $x_{1},x_{2}\in(x-\delta,x+\delta)\setminus\{x\}$ such that

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

We claim that there exists $x_{2}\in(0,1)$ such that

and thus the second equality in (2) holds. Hence, finding $x_{2}\in(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

so the length of each of those closed intervals is $\frac{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

Let $x_{2}\in(0,1)$ be the midpoint of $I$. By the construction of $f$ and $g$, we have $(g\circ f)(x_{2})=2^{-k}$. Furthermore, since the length of $I$ is $3^{-k}/2$, we have

Hence, $x_{2}\in(0,1)$ satisfies (4), and this concludes the proof. ∎

Next, we make a remark on non-differentiable inputs of $f$, $g$, and $g\circ f$ in the proof. One might guess that $f$ should be non-differentiable exactly on $C_{1/2}$, given that $f$ maps ${(0,1)}\,\setminus C_{1/2}$ onto ${(0,1)}\,\setminus 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\circ 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\circ 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\circ f$ is PAP and so almost-everywhere differentiable. In fact, $g\circ f$ is non-PAP, since $g\circ 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\circ f$ is so). Although $g^{\prime}$ is undefined at , we can extend it to an intensional derivative $\mathit{dg}\in\partial_{\bullet}{g}$ such that $\mathit{dg}$ is defined everywhere (even at ) and coincides with $g^{\prime}$ at all but countably many inputs. With such $\mathit{dg}$, the following version of the chain rule holds almost everywhere:

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

A.3 Comments on the proof of Proposition 3

The functions $f$, $g$, and $g\circ 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\circ f$.

Appendix B Comments on and Proofs for Results in §3

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.

has positive measure. For the $\lambda$-Cantor function $\phi_{\lambda}$ with $\lambda\in(0,1)$, $S$ is a full measure subset of $C_{\lambda}$ due to the following: $\phi_{\lambda}^{\prime}(x)=1/(1-\lambda)\neq 0$ for almost all $x\in C_{\lambda}$; $\phi_{\lambda}^{\prime}(x)=0$ for all $x\notin C_{\lambda}$; and $C_{\lambda}\subset(0,1)$ has no interior. Since $C_{\lambda}$ has measure $1-\lambda>0$, the claim holds for $\phi_{\lambda}$. 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 [18, Example 8.35]. So the claim holds for Volterra’s function.

B.2 Interior and subinterior of analytic partition

Then, $C=\{C^{t}\}_{t\in[T]}$ is a finer partition of $\mathcal{X}$ than $\{A^{i}\}_{i\in[I]}$. That is, $C$ is a partition of $\mathcal{X}$, and for all $t\in[T]$, $C^{t}\subseteq A^{i}$ for some $i\in[I]$.

We call the set $\mathcal{X}^{\prime}$ a subinterior of $A$, and the partition $B$ a subanalytic partition of $\mathcal{X}^{\prime}$. We use ${\rm subint}({A})$ to denote the set of all subinteriors of $A$.

$\mathcal{X}\setminus\mathcal{X}^{\prime}$ is contained in some measure-zero set.

$\mathcal{X}\setminus{\rm int}({A})$ is contained in some measure-zero set.

Then, $\mathcal{X}^{\prime}$ is a subinterior of $A$, and $B$ is a subanalytic partition of $\mathcal{X}^{\prime}$, because of the following:

$B$ is a partition of $\mathcal{X}^{\prime}$.

$\{\langle i,t_{1},\ldots,t_{L_{i}}\rangle\mid i\in[I],\;\langle t_{1},\ldots,t_{L_{i}}\rangle\in[\infty]^{L_{i}}\}$ is a countable set.

For all $i\in[I]$ and $\langle t_{1},\ldots,t_{L_{i}}\rangle\in[\infty]^{L_{i}}$, $B^{i,\langle t_{1},\ldots,t_{L_{i}}\rangle}$ is subanalytic.

$C$ is a finer partition of $\mathcal{X}$ than $A$. This holds because $\{A^{i}\}_{i\in[I]}$ is a partition of $\mathcal{X}$, and $\{C^{i,\langle t_{1},\ldots,t_{L_{i}}\rangle}\}_{\langle t_{1},\ldots,t_{L_{i}}\rangle\in[\infty]^{L_{i}}}$ is a partition of $A^{i}$ for all $i\in[I]$, by its construction.

This completes the proof that ${\rm subint}({A})\neq\varnothing$.

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

Since each $g^{-}_{t,l}$ is analytic, and not everywhere-zero, on its connected open domain $\mathcal{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, $\mathcal{X}\setminus\mathcal{X}^{\prime}$ 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$.

Let $\gamma=\{\langle A^{i},f^{i}\rangle\}_{i\in[I]}$ be a PAP representation from $\mathcal{X}$ to $\mathcal{Y}$. The interior and subinterior of $\gamma$ are defined by:

where $F^{(k)}$ denotes the $k$-time composition of the operator $F$.

B.4 Proof of Proposition 8 (part II)

Let $f:\mathcal{X}_{f}\to\mathcal{Y}$ and $g:\mathcal{X}_{g}\to\mathcal{Y}$ be PAP functions, and $\gamma_{f}$ and $\gamma_{g}$ be their PAP representations. If $f(x)=g(x)$ for all $x\in{\rm int}({\gamma_{f}})\cap{\rm int}({\gamma_{g}})$, then

where both sides are well-defined for each $x$.

Let $f:\mathcal{X}\to\mathcal{Y}$ be a PAP function. Then, for any intensional derivative $\mathit{df}\in\partial_{\bullet}{f}$, there exists a PAP representation $\gamma_{\mathit{df}}$ of $\mathit{df}$ such that

Let $\gamma_{f}=\{\langle A^{i},f^{i}\rangle\}_{i\in[I]}$ be a representation of a function from $\mathcal{X}_{f}$ to $\mathcal{Y}$, and $B=\{B^{j}\}_{j\in[J]}$ be a partition of $\mathcal{X}_{g}$. The refinement of $\gamma_{f}$ with $B$ is defined by:

Moreover, for any representation $\gamma_{g}=\{\langle C^{l},g^{l}\rangle\}_{l\in[L]}$ of a function from $\mathcal{X}_{g}$ to $\mathcal{Z}$, the refinement of $\gamma_{f}$ with $\gamma_{g}$ is defined by:

Let $\gamma=\{\langle A^{i},f^{i}\rangle\}_{i\in[I]}$. Since $\gamma$ is PAP and $B$ is an analytic partition, $\{A^{i}\cap B^{j}\}_{\langle i,j\rangle\in[I]\times[J]}$ is an analytic partition. Also, since $[J]$ is countable, $[I]\times[J]$ is also countable. Thus, $\gamma^{\prime}$ is PAP. Since

$\gamma^{\prime}$ is a representation of ${f|_{\mathcal{X}_{f}\cap\mathcal{X}_{g}}}$. Finally, we obtain the last claim as follows:

For the second equality, we use the following fact: ${\rm int}({S_{1}\cap S_{2};X})={\rm int}({S_{1};X})\cap{\rm int}({S_{2};X})$ for any $S_{1},S_{2}\subseteq X$. ∎

The proof proceeds by induction on $k$. For $k=0$, we have $\mathit{df}^{k}=D^{(k)}(f)=f$. So any PAP representation $\gamma_{d}^{k}$ of $\mathit{df}^{k}=f$ satisfies the claim. Now suppose $k>0$. By the definition of $\partial_{\bullet}^{{k}}{f}$, there exists $\mathit{df}^{k-1}\in\partial_{\bullet}^{{k-1}}{f}$ such that $\mathit{df}^{k}\in\partial_{\bullet}{(\mathit{df}^{k-1})}$. We construct the desired PAP representation $\gamma_{d}^{k}$ as follows. First, focus on $\mathit{df}^{k-1}\in\partial_{\bullet}^{{k-1}}{f}$. By the induction hypothesis on $k-1$ for $\mathit{df}^{k-1}$, there exists a PAP representation $\gamma_{d}^{k-1}$ of $\mathit{df}^{k-1}$ such that

The claim follows from Lemma 21 and the following: $\mathcal{X}^{\prime}$ and ${\rm int}({\gamma_{d}^{k}})$ described in Lemma 21 have the full measure in $\mathcal{X}$, by Lemma 21 and Lemma 14(d). ∎

B.5 Additional property on PAP functions