# Provably Correct Automatic Subdifferentiation for Qualified Programs

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2018.

## Built on by (most cited first, 8 of 8)

- [Nonsmooth Implicit Differentiation for Machine Learning and Optimization](https://mlsanity.com/paper/2106.04350/) (2021)
- [Automatic differentiation of nonsmooth iterative algorithms](https://mlsanity.com/paper/2206.00457/) (2022)
- [Flexible Differentiable Optimization via Model Transformations](https://mlsanity.com/paper/2206.06135/) (2022)
- [On the complexity of nonsmooth automatic differentiation](https://mlsanity.com/paper/2206.01730/) (2022)
- [On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters](https://mlsanity.com/paper/2301.13370/) (2023)
- [Deep Learning as the Disciplined Construction of Tame Objects](https://mlsanity.com/paper/2509.18025/) (2025)
- [On the numerical reliability of nonsmooth autodiff: a MaxPool case study](https://mlsanity.com/paper/2401.02736/) (2024)
- [On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2409.10323/) (2024)

## Abstract (arXiv)

The Cheap Gradient Principle (Griewank 2008) --- the computational cost of computing the gradient of a scalar-valued function is nearly the same (often within a factor of 5) as that of simply computing the function itself --- is of central importance in optimization; it allows us to quickly obtain (high dimensional) gradients of scalar loss functions which are subsequently used in black box gradient-based optimization procedures. The current state of affairs is markedly different with regards to computing subderivatives: widely used ML libraries, including TensorFlow and PyTorch, do not correctly compute (generalized) subderivatives even on simple examples. This work considers the question: is there a Cheap Subgradient Principle? Our main result shows that, under certain restrictions on our library of nonsmooth functions (standard in nonlinear programming), provably correct generalized subderivatives can be computed at a computational cost that is within a (dimension-free) factor of 6 of the cost of computing the scalar function itself.