One-step differentiation of iterative algorithms

Abstract

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.

References in corpus (11)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Deep Equilibrium Models
• Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters
• Differential Properties of Sinkhorn Approximation for Learning with Wasserstein Distance
• Implicit Graph Neural Networks
• Is Attention Better Than Matrix Decomposition?
• Implicit differentiation of Lasso-type models for hyperparameter optimization
• Nonsmooth Implicit Differentiation for Machine Learning and Optimization
• Backpropagation through Combinatorial Algorithms: Identity with Projection Works
• Automatic differentiation of nonsmooth iterative algorithms
• The Curse of Unrolling: Rate of Differentiating Through Optimization