Combinatory Adjoints and Differentiation
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Combinatory Adjoints and Differentiation. / Elsman, Martin; Henglein, Fritz; Kaarsgaard, Robin; Mathiesen, Mikkel Kragh; Schenck, Robert.
Proceedings Ninth Workshop on Mathematically Structured Functional Programming (MSFP 2022).. Vol. 360 EPTCS, 2022. p. 1-26 (Electronic Proceedings in Theoretical Computer Science, EPTCS, Vol. 360).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Combinatory Adjoints and Differentiation
AU - Elsman, Martin
AU - Henglein, Fritz
AU - Kaarsgaard, Robin
AU - Mathiesen, Mikkel Kragh
AU - Schenck, Robert
N1 - Funding Information: Acknowledgements. This work was made possible by Independent Research Fund Denmark grants FUTHARK: Functional Technology for High-performance Architectures, Deep Probabilistic Programming for Protein Structure Prediction (DPP), and DFF–International Postdoc 0131-00025B. We would like to thank Gabriele Keller, Ken Friis Larsen and Dimitrios Vytionitis for collaborative discussions over the last six years that have greatly helped in developing the foundations of combinatory differentiation and our colleagues on FUTHARK and DPP, in particular Cosmin Oancea, Troels Henriksen, Thomas Hamelryck and Ola Rønning. Furthermore, the second author would like to thank Conal Elliott for stimulating exchanges on AD in the period he was working on his ICFP 2018 paper [13]. We greatly appreciate and thank the three anonymous referees for their recommendations. Funding Information: This work was made possible by Independent Research Fund Denmark grants FUTHARK: Functional Technology for High-performance Architectures, Deep Probabilistic Programming for Protein Structure Prediction (DPP), and DFF-International Postdoc 0131-00025B.We would like to thank Gabriele Keller, Ken Friis Larsen and Dimitrios Vytionitis for collaborative discussions over the last six years that have greatly helped in developing the foundations of combinatory differentiation and our colleagues on FUTHARK and DPP, in particular Cosmin Oancea, Troels Henriksen, Thomas Hamelryck and Ola Rønning. Furthermore, the second author would like to thank Conal Elliott for stimulating exchanges on AD in the period he was working on his ICFP 2018 paper [13]. We greatly appreciate and thank the three anonymous referees for their recommendations. Publisher Copyright: © 2022 Elsman, Henglein, Kaarsgaard, Mathiesen, Schenck.
PY - 2022
Y1 - 2022
N2 - 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échet 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.
AB - 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échet 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.
UR - http://www.scopus.com/inward/record.url?scp=85134255618&partnerID=8YFLogxK
U2 - 10.4204/EPTCS.360.1
DO - 10.4204/EPTCS.360.1
M3 - Article in proceedings
AN - SCOPUS:85134255618
VL - 360
T3 - Electronic Proceedings in Theoretical Computer Science, EPTCS
SP - 1
EP - 26
BT - Proceedings Ninth Workshop on Mathematically Structured Functional Programming (MSFP 2022).
PB - EPTCS
T2 - 9th Workshop on Mathematically Structured Functional Programming, MSFP 2022
Y2 - 2 April 2022
ER -
ID: 342682513