# On the complexity of nonsmooth automatic differentiation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 63 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 22 of 22)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Monotone operator equilibrium networks](https://mlsanity.com/paper/2006.08591/) (2020)
- [Differentiating Through a Cone Program](https://mlsanity.com/paper/1904.09043/) (2019)
- [Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning](https://mlsanity.com/paper/1909.10300/) (2019)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [A mathematical model for automatic differentiation in machine learning](https://mlsanity.com/paper/2006.02080/) (2020)
- [Nonsmooth Implicit Differentiation for Machine Learning and Optimization](https://mlsanity.com/paper/2106.04350/) (2021)
- [Implicit differentiation of Lasso-type models for hyperparameter optimization](https://mlsanity.com/paper/2002.08943/) (2020)
- [Automatic Differentiation of Some First-Order Methods in Parametric Optimization](https://mlsanity.com/paper/1910.05696/) (2019)
- [Provably Correct Automatic Subdifferentiation for Qualified Programs](https://mlsanity.com/paper/1809.08530/) (2018)
- [Efficient approximation of Jacobian matrices involving a non-uniform fast Fourier transform (NUFFT)](https://mlsanity.com/paper/2111.02912/) (2021)
- [The structure of conservative gradient fields](https://mlsanity.com/paper/2101.00699/) (2021)
- [Conservative and semismooth derivatives are equivalent for semialgebraic maps](https://mlsanity.com/paper/2102.08484/) (2021)

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

- [On the Correctness of Automatic Differentiation for Neural Networks with Machine-Representable Parameters](https://mlsanity.com/paper/2301.13370/) (2023)
- [The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling](https://mlsanity.com/paper/2605.24477/) (2026)
- [On the numerical reliability of nonsmooth autodiff: a MaxPool case study](https://mlsanity.com/paper/2401.02736/) (2024)
- [Dual Certified White-Box Inference for Input Convex Neural Networks](https://mlsanity.com/paper/2605.04722/) (2026)

## Abstract (arXiv)

Using the notion of conservative gradient, we provide a simple model to estimate the computational costs of the backward and forward modes of algorithmic differentiation for a wide class of nonsmooth programs. The overhead complexity of the backward mode turns out to be independent of the dimension when using programs with locally Lipschitz semi-algebraic or definable elementary functions. This considerably extends Baur-Strassen's smooth cheap gradient principle. We illustrate our results by establishing fast backpropagation results of conservative gradients through feedforward neural networks with standard activation and loss functions. Nonsmooth backpropagation's cheapness contrasts with concurrent forward approaches, which have, to this day, dimensional-dependent worst-case overhead estimates. We provide further results suggesting the superiority of backward propagation of conservative gradients. Indeed, we relate the complexity of computing a large number of directional derivatives to that of matrix multiplication, and we show that finding two subgradients in the Clarke subdifferential of a function is an NP-hard problem.