# Combinatory Adjoints and Differentiation

arXiv: https://arxiv.org/abs/2207.00847 · HTML: https://mlsanity.com/paper/2207.00847/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 2 Jul 2022.

## Builds on (most cited first, 11 of 11)

- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Caffe: Convolutional Architecture for Fast Feature Embedding](https://mlsanity.com/paper/1408.5093/) (2014)
- [Don't Unroll Adjoint: Differentiating SSA-Form Programs](https://mlsanity.com/paper/1810.07951/) (2018)
- [The simple essence of automatic differentiation](https://mlsanity.com/paper/1804.00746/) (2018)
- [Reverse derivative categories](https://mlsanity.com/paper/1910.07065/) (2019)
- [Demystifying Differentiable Programming: Shift/Reset the Penultimate Backpropagator](https://mlsanity.com/paper/1803.10228/) (2018)
- [Getting to the Point. Index Sets and Parallelism-Preserving Autodiff for Pointful Array Programming](https://mlsanity.com/paper/2104.05372/) (2021)
- [A Benchmark of Selected Algorithmic Differentiation Tools on Some Problems in Computer Vision and Machine Learning](https://mlsanity.com/paper/1807.10129/) (2018)
- [Automatic Differentiation in PCF](https://mlsanity.com/paper/2011.03335/) (2020)
- [Reverse AD at Higher Types: Pure, Principled and Denotationally Correct](https://mlsanity.com/paper/2007.05283/) (2020)

## Abstract (arXiv)

We develop a compositional approach for automatic and symbolic differentiation based on categorical constructions in functional analysis where derivatives are linear functions on abstract vectors rather than being limited to scalars, vectors, matrices or tensors represented as multi-dimensional arrays. We show that both symbolic and automatic differentiation can be performed using a differential calculus for generating linear functions representing Fr'echet derivatives based on rules for primitive, constant, linear and bilinear functions as well as their sequential and parallel composition. Linear functions are represented in a combinatory domain-specific language. Finally, we provide a calculus for symbolically computing the adjoint of a derivative without using matrices, which are too inefficient to use on high-dimensional spaces. The resulting symbolic representation of a derivative retains the data-parallel operations from the input program. The combination of combinatory differentiation and computing formal adjoints turns out to be behaviorally equivalent to reverse-mode automatic differentiation. In particular, it provides opportunities for optimizations where matrices are too inefficient to represent linear functions.