nucleation

LIT-827: Backprop as Functor: A compositional perspective on supervised learning

3 min read

Properties4
StatusActive — read 2026-10-09 (NOTE-625); worth reading as the paper that makes supervised learners composable: a learner A → B is a parameter set with implement, update and request functions, learners form a symmetric monoidal category Learn, and for a fixed step size and an error function whose derivative in its first argument is invertible, gradient descent with backpropagation is a faithful strong symmetric monoidal functor from differentiable parametrised functions to Learn. The backward message is a requested input, not a gradient step; cross-entropy falls outside the theorem.
Tagsmathematics, compositionality, anthology-candidate
Cited as “paper” byNOTE-625 — Backprop as Functor
Cited as “source” byTHEORY-519 — Supervised learners compose only once each carries a request function that passes a corrected input upstream; with it they form a symmetric monoidal category, and for a fixed step size and an error whose derivative in its first argument is invertible, gradient descent with backpropagation is a faithful strong symmetric monoidal functor into it from differentiable parametrised functions

Graph View

Brendan Fong, David I. Spivak, Rémy Tuyéras (2017; LICS 2019) — ARXIV-1711.10455

Key takeaways

  • What fails without a request. Two learners A → B and B → C, each a parametrised function with an update rule, do not compose: the upstream learner needs a training pair in A × B and nothing supplies the b. Adding a request function r : P × A × B → A, which returns the input the learner “would rather have had”, fixes this. Learners (P, I, U, r), up to bijection of parameter sets, are the morphisms of a symmetric monoidal category Learn (Proposition II.4); the request is superfluous for a stand-alone learner and essential for composition.
  • Backprop is a functor. Theorem III.2: fix ε > 0 and a differentiable e(x, y) with ∂e/∂x(x₀, −) invertible for every x₀. Then I ↦ (P, I, p − ε∇ₚE_I, f_a(∇ₐE_I)), with E_I the summed error and f_a the componentwise inverse of ∂e/∂x(aᵢ, −), is a faithful, injective-on-objects, strong symmetric monoidal functor L_{ε,e} : Para → Learn. Gradient descent on a composite equals the composite of the local updates passing requests: that is backpropagation, and the proof is the chain rule.
  • The backward message is an input, not a step. For quadratic error the request is a − ∇ₐE_I, with no ε. The likeness to the update is an artifact of that error function (Remark III.5); what matters is that the request inverts ∂e/∂x so that the upstream error’s gradient reproduces the composite’s.
  • Networks and wiring. An activation σ gives a functor NNet → Para; the bimonoid structure of linear maps carries over to Learn (Proposition V.1), so every neural network trained by quadratic-error gradient descent is generated by scalar multiplication, bias, activation and the split and merge maps. Weight tying is copying a parameter through the comonoid. The paper notes embeddings Lens ↪ Learn ↪ Game.
  • Limits it states. Cross-entropy fails the invertibility hypothesis at x = 0, 1 and is handled only approximately (§VII-A); Learn places no convergence requirement on learners.

Standing in the record

Filed on 2026-10-09 at the owner’s request, from the manuscript bibliography of 2026-10-09 (work what-survives-translation): one of the works the manuscript considered and dropped from its final reference list.

Read on 2026-10-09 (NOTE-625). It is a worked example of a functor that preserves composition from a syntax (parametrised functions) to a semantics (learning algorithms), the pattern Fong and Spivak’s book LIT-803 calls functorial semantics. It carries anthology-candidate because the anthology’s training-optimization topic could hold a paper on the structure of backpropagation; it carries no instruction for practice.

Backlinks