One-step differentiation of iterative algorithms
This work addresses a key efficiency problem for researchers and practitioners in machine learning and optimization who rely on iterative algorithms, offering a practical solution that is incremental in improving differentiation techniques.
The paper tackles the computational burden of automatic differentiation for iterative algorithms by proposing one-step differentiation, a method that is as easy to use as automatic differentiation and as performant as implicit differentiation for fast algorithms like superlinear optimization methods, with theoretical analysis and numerical examples demonstrating its effectiveness.
In appropriate frameworks, automatic differentiation is transparent to the user at the cost of being a significant computational burden when the number of operations is large. For iterative algorithms, implicit differentiation alleviates this issue but requires custom implementation of Jacobian evaluation. In this paper, we study one-step differentiation, also known as Jacobian-free backpropagation, a method as easy as automatic differentiation and as performant as implicit differentiation for fast algorithms (e.g., superlinear optimization methods). We provide a complete theoretical approximation analysis with specific examples (Newton's method, gradient descent) along with its consequences in bilevel optimization. Several numerical examples illustrate the well-foundness of the one-step estimator.