Automatic differentiation (AD) in frameworks like PyTorch and TensorFlow is the engine behind backpropagation. However, AD differentiates programs, not mathematical functions. This distinction can produce mathematically inconsistent "spurious" gradients for nonsmooth functions depending on how the function is coded. This paper provides a rigorous mathematical model for how AD operates on programs and proves that despite AD creating artificial critical points, stochastic gradient descent (SGD) avoids these traps with probability one.
The Problem: Differentiating Programs vs. Functions
For smooth functions, the distinction between a program and a mathematical function doesn't matter. But for nonsmooth functions (like ReLU or max-pooling), different code implementations of the exact same mathematical function can yield completely different gradients at non-differentiable points (e.g., at $x=0$).
For example, coding a standard relu(x) versus a mathematically equivalent 0.5 * (relu(x) + relu(-x) + x) yields different derivatives at zero in AD frameworks.
This quirk means AD can generate "artificial critical points"—places where the AD gradient is zero, but the actual mathematical function is not at a local minimum or maximum. The paper addresses the lack of a stable mathematical theory to explain this widespread phenomenon and asks a critical question: Do these artificial traps ruin the optimization process in practice?
Bridging Computer Science and Calculus
To bridge the gap between code execution and mathematics, the authors introduce a novel theoretical framework:
- Elementary Selections: They define a vast class of functions that rigorously models machine learning programs. These functions are essentially piecewise combinations of basic smooth operations (log, exp, arithmetic) dictated by logical branching (like
if x > 0). - Selection Derivatives: Instead of using traditional subgradients (like Clarke subgradients), they define a "selection derivative." This means taking the derivative of the specific active branch of the program that was executed, freezing all other logical branches.
- Algorithmic Differentiation Modeling: They mathematically prove that calling forward or backward AD on a program computes exactly this selection derivative.
- Dynamical Systems Analysis: Using the theory of conservative set-valued fields, they analyze the asymptotic behavior of stochastic approximation algorithms (like mini-batch SGD) guided by these selection derivatives.
Key Insights and Results
The paper establishes several foundational results for the theory of automatic differentiation in machine learning:
- AD is Not a Standard Mathematical Operator: The authors prove that it is impossible to define AD as a standard mathematical operator on functions. Because AD's output depends on the specific syntax of the code, it must be analyzed as an operation on programs. When you call
.backward()on a nonsmooth loss landscape, you are getting a "selection derivative" tied to your specific code path, not necessarily a mathematically rigorous subgradient. - Formalization of AD: The authors successfully proved that algorithmic differentiation of a given program outputs a selection derivative of the underlying numerical function. Furthermore, they established that the index closure of these selection derivatives forms a "conservative field," a crucial property needed to guarantee that optimization algorithms will converge.
- The "Aha!" Moment - Insignificance of Artifacts: Even though AD creates parasitic, artificial critical points where the gradient evaluates to zero incorrectly, these points are essentially harmless in a stochastic setting. The most impactful practical result shows that for an SGD-like algorithm with random initialization, the sequence of parameters converges. More importantly, almost surely (with probability 1), the points it converges to are true Clarke critical points. The noise of random initialization and mini-batch sampling ensures that the optimizer avoids the artificial traps created by AD entirely.
Limitations and Future Work
The current theoretical framework is strictly limited to continuous functions. Furthermore, while the paper proves that SGD eventually avoids artificial traps and converges, it does not tackle convergence rates or the computational complexity of finding these stationary points.
The authors suggest extending this theory to discontinuous functions as a highly relevant future direction. Modern machine learning increasingly relies on differentiating through discontinuous operations like sorting, ranking (ubiquitous in recommendation systems), or argmax functions, which require a broader theoretical foundation.
Summary updated