Lune

NeurIPS2020Top-tier venue

On Correctness of Automatic Differentiation for Non-Differentiable Functions

Wonyeol Lee, Hangyeol Yu, Xavier Rival, Hongseok Yang

Abstract

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

14 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Automatic differentiation in PCF cites A simple differentiable programming language
  • Automatic differentiation of nonsmooth iterative algorithms cites A mathematical model for automatic differentiation in machine learning
  • Automatic differentiation of nonsmooth iterative algorithms cites Nonsmooth Implicit Differentiation for Machine-Learning and Optimization
  • Nonsmooth Implicit Differentiation for Machine-Learning and Optimization cites A mathematical model for automatic differentiation in machine learning
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers14

  1. Nonsmooth Implicit Differentiation for Machine-Learning and OptimizationJérôme Bolte, Tam Le, Edouard Pauwels, Antonio Silveti-FallsNeurIPS 2021 · 85 citations
  2. A mathematical model for automatic differentiation in machine learningJérôme Bolte, Edouard PauwelsNeurIPS 2020 · 84 citations
  3. Automatic differentiation in PCFDamiano Mazza, Michele PaganiPOPL 2021 · 47 citations
  4. A Simple and Efficient Tensor CalculusSören Laue, Matthias Mitterreiter, Joachim GiesenAAAI 2020 · 40 citations
  5. Automatic differentiation of nonsmooth iterative algorithmsJérôme Bolte, Edouard Pauwels, Samuel VaiterNeurIPS 2022 · 33 citations

Builds on2

  1. A mathematical model for automatic differentiation in machine learningJérôme Bolte, Edouard PauwelsNeurIPS 2020 · 84 citations
  2. A simple differentiable programming languageMartín Abadi, Gordon D. PlotkinPOPL 2020 · 49 citations

Related papers

  1. What does automatic differentiation compute for neural networks?Sejun Park, Sanghyuk Chun, Wonyeol LeeICLR 2024
  2. On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable ParametersWonyeol Lee, Sejun Park, Alex AikenICML 2023 · 6 citations
  3. Floating-Point Networks with Automatic Differentiation Can Represent Almost All Floating-Point Functions and Their GradientsSejun Park, Yeachan Park, Geonho HwangICML 2026
  4. ωPAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable ProgramsMathieu Huot, Alexander K. Lew, Vikash K. Mansinghka, Sam StatonLICS 2023 · 5 citations
  5. 𝜆ₛ: computable semantics for differentiable programming with higher-order functions and datatypesBenjamin Sherman, Jesse Michel, Michael CarbinPOPL 2021 · 11 citations
Dusk over the sea between two cliffs drawn in fine vertical lines