Abstract
Automatic differentiation, as implemented today, does not have a simple mathematical model adapted to the needs of modern machine learning. In this work we articulate the relationships between differentiation of programs as implemented in practice and differentiation of nonsmooth functions. To this end we provide a simple class of functions, a nonsmooth calculus, and show how they apply to stochastic approximation methods. We also evidence the issue of artificial critical points created by algorithmic differentiation and show how usual methods avoid these points with probability one.
Introduction: The Gap Between Programs and Functions
Modern machine learning relies heavily on nonsmooth functions such as ReLU ($max(0, t)$), absolute value, and max-pooling. While standard calculus assumes smoothness, the "dirty secret" of deep learning is that Automatic Differentiation (AD)—the engine behind backpropagation—lacks a stable theory for these nonsmooth components.
Because AD operates on the program (the sequence of instructions) rather than the abstract mathematical function, two different programs representing the same function can yield different derivatives at nonsmooth points. For instance, depending on the implementation of a ReLU function, AD might return a derivative at zero of 0, 1, or 0.5. This discrepancy leads to the creation of artificial critical points: locations where the AD-generated gradient is zero, even if the function is not at a mathematical stationary point.
Methodology: Bridging Code and Calculus
The authors bridge the gap between computer science and mathematics by introducing several formal concepts:
- Elementary Selections: A broad class of "tame" functions built from elementary pieces (polynomials, logs, exponentials) and selections (like
max). - Selection Derivatives: A formal model of what tools like PyTorch or TensorFlow actually compute, corresponding to the specific branch of code being executed.
- Conservative Fields: Utilizing set-valued fields to show that selection derivatives allow for integration along paths, a prerequisite for proving optimization convergence.
- Tame Geometry: Leveraging o-minimal structures to ensure functions do not exhibit pathological oscillations (e.g., $sin(1/x)$), making "bad" points mathematically rare.
Key Insights: AD as a Program Operator
The fundamental insight is that AD is an operator on programs ($\mathcal{P}$), not functions ($J$). The mapping from program to function is a surjection; many programs can represent one function, but AD treats them as distinct entities. The "spurious" gradients produced at nonsmooth points are not numerical errors but a fundamental property of applying the chain rule to code branches.
Crucially, the authors demonstrate that stochasticity acts as a filter. While artificial critical points exist, they have a negligible footprint. Because stochastic gradient descent (SGD) involves random initialization and noisy updates, the probability of an algorithm becoming trapped at an artificial critical point is zero.
Theoretical Results
The paper establishes two landmark theorems:
- Theorem 2 (AD outputs a selection gradient): Proves that standard AD algorithms (forward or backward) produce valid "selection gradients" for the underlying function.
- Theorem 4 (Avoidance of Traps): Shows that for a wide class of stochastic approximation algorithms, iterates will converge to a Clarke critical point (a true mathematical stationary point) and ignore artificial ones, provided initialization is random.
Conclusion and Future Directions
This work provides a rigorous "safety certificate" for the common practice of using AD on nonsmooth losses. However, limitations remain. The current model requires continuity, excluding programs with discrete jumps or argmax operations. Furthermore, the results are asymptotic and do not yet provide specific convergence rates in the presence of nonsmooth artifacts. Future research will aim to extend this framework to handle discontinuous functions and explore the complexity of finding stationary points in these "tame" landscapes.
Summary updated