Data-Parallel Differentiation by Optic Composition

on YouTube ↗17m

" summary

Provides a concrete open hypergraphs representation (struct-of-arrays with segmented arrays) and parallel algorithms for tensor and composition via concatenation plus connected‑components renumbering, claiming reverse derivatives by optic composition that map each primitive to a forward, reverse and residual part. Algorithm runs O(log n) on PRAM and O(n) sequentially; construction avoids inductive blowup by wiring leaves then connecting. Demonstration includes a differentiable array language able to train a small GPT (nanogPT) on GPU.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 2:06GPU data structures
3. 5:17Tensor algorithms
4. 7:23Acyclicity and FBIA
5. 9:28Optic composition
6. 12:23Differentiable array languages
7. 13:04Q&A

" related talks

• 18m(De/Re)-Composition of Data-Parallel Computations via Multi-Dimensional(…)Ari Rasch · PLDI 2024
• 34mDifferentiable Functional ProgrammingNoel Welsh · Scala Days Berlin 2018
• 16mTHC: Accelerating Distributed Deep Learning Using Tensor Homomorphic CompressionMichael Mitzenmacher, Minlan Yu, Kevin Xu, Minghao Li, Ran Ben Basat, Shay Vargaftik, ChonLam Lao · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 39mDifferentiable Functional ProgrammingNoel Welsh · Scala Days New York 2018
• 29mParallelism-preserving automatic differentiation for second-order array languagesadam basker · FHPNC 2021
• 29mAutomatic Differentiation via Effects and Handlers in OCamlJesse Sigal · ML 2024
• 30mData-Parallel Flattening by ExpansionTroels Henriksen, Martin Elsman, Niels G. W. Serup · ARRAY 2019
• 29mReverse Automatic Differentiation for Accelerate (Extended Abstract)Tom J. Smeding · FHPNC 2021