paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Automatic differentiation in PCF

PCF 中的自动微分
POPL 5(POPL)2021匹配度 4/10 · 论文属于 PL 与 ML 交叉的形式语义研究,讨论高阶语言中自动微分的正确性,理论上与机器学习系统相关。但用户核心关注的是静态分析、Agentic/LLM 程序、浮点程序分析和贝叶斯程序分析,该论文并未直接涉及这些方向,且偏纯理论、缺少工程落地与 benchmark。引用 47 inbox
Damiano Mazza, Michele Pagani
crossref: 2026-09-10

AI 速览

一句话:证明 PCF(含实数的高阶图灵完备语言)中前向与反向自动微分在温和假设下几乎处处正确。

论文研究高阶、图灵完备且含实数的语言 PCF 中自动微分(AD)的正确性,涵盖前向与反向模式。作者不假设程序处处可微,而是在对基本函数施加温和假设后,通过语义分析证明 AD 几乎处处正确:AD 计算的导数或梯度仅可能在一组 Lebesgue 测度为零的输入上失败,因此随机取到错误输入的概率为零。结果还更精确地刻画失败点集;例如当基本函数仅为常数、加法和乘法时,AD 失败点包含在一列多项式零点集的并集之中。该工作表明 AD 虽非绝对正确,但在测度意义下对一大类高阶程序可靠。

问题
在高阶、图灵完备且含实数的语言中,自动微分(尤其是前向与反向模式)是否正确地计算程序的导数或梯度?
方法
在 PCF 上形式化前向与反向 AD,对基本函数作温和假设,并通过语义分析与数学证明刻画 AD 失败点集。
评估
以理论证明为主,给出几乎处处正确性定理;并针对常数、加法、乘法等基本函数显式描述失败点集为测度零集或多项式零点集的并集。
原文摘要(Abstract)

We study the correctness of automatic differentiation (AD) in the context of a higher-order, Turing-complete language (PCF with real numbers), both in forward and reverse mode. Our main result is that, under mild hypotheses on the primitive functions included in the language, AD is almost everywhere correct, that is, it computes the derivative or gradient of the program under consideration except for a set of Lebesgue measure zero. Stated otherwise, there are inputs on which AD is incorrect, but the probability of randomly choosing one such input is zero. Our result is in fact more precise, in that the set of failure points admits a more explicit description: for example, in case the primitive functions are just constants, addition and multiplication, the set of points where AD fails is contained in a countable union of zero sets of polynomials.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1153,
  title = {Automatic differentiation in PCF},
  author = {Damiano Mazza and Michele Pagani},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {5},
  number = {POPL},
  year = {2021},
  doi = {10.1145/3434309}
}