One-step differentiation of iterative algorithms

2023/05/23 by Bolte, Jérôme, Pauwels, Edouard, Vaiter, Samuel · 5 citations
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2305.13768

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.

Cited by

• A Fully First-Order Layer for Differentiable Optimization
• Bilevel Learning via Inexact Stochastic Gradient Descent
• Learning Regularization Functionals for Inverse Problems: A Comparative Study
• End-to-End Training of High-Dimensional Optimal Control with Implicit Hamiltonians via Jacobian-Free Backpropagation
• Differentiable Expectation-Maximisation and Applications to Gaussian Mixture Model Optimal Transport

Related

• Gradients without Backpropagation
• On the complexity of nonsmooth automatic differentiation
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning
• A Fully First-Order Layer for Differentiable Optimization
• Automatic Differentiation Tools in Optimization Software