On Correctness of Automatic Differentiation for Non-Differentiable
  Functions
  Differentiation lies at the core of many machine-learning algorithms, and is
well-supported 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 non-differentiable 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 often-used 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
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. 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.
