# Super-efficiency of automatic differentiation for functions defined as a minimum

arXiv: https://arxiv.org/abs/2002.03722 · HTML: https://mlsanity.com/paper/2002.03722/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2020.

## Built on by (most cited first, 24 of 24)

- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [Gradients are Not All You Need](https://mlsanity.com/paper/2111.05803/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [Trajectory Inference via Mean-field Langevin in Path Space](https://mlsanity.com/paper/2205.07146/) (2022)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [One-step differentiation of iterative algorithms](https://mlsanity.com/paper/2305.13768/) (2023)
- [Automatic differentiation of nonsmooth iterative algorithms](https://mlsanity.com/paper/2206.00457/) (2022)
- [Implicit differentiation for fast hyperparameter selection in non-smooth convex learning](https://mlsanity.com/paper/2105.01637/) (2021)
- [Functional Bilevel Optimization for Machine Learning](https://mlsanity.com/paper/2403.20233/) (2024)
- [Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation](https://mlsanity.com/paper/2111.12193/) (2021)
- [The Curse of Unrolling: Rate of Differentiating Through Optimization](https://mlsanity.com/paper/2209.13271/) (2022)
- [A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk Minimization](https://mlsanity.com/paper/2302.08766/) (2023)
- [Stable and Interpretable Unrolled Dictionary Learning](https://mlsanity.com/paper/2106.00058/) (2021)
- [Let Go of Your Labels with Unsupervised Transfer](https://mlsanity.com/paper/2406.07236/) (2024)
- [Understanding approximate and unrolled dictionary learning for pattern recovery](https://mlsanity.com/paper/2106.06338/) (2021)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Learning Energy Networks with Generalized Fenchel-Young Losses](https://mlsanity.com/paper/2205.09589/) (2022)
- [Debiasing a First-order Heuristic for Approximate Bi-level Optimization](https://mlsanity.com/paper/2106.02487/) (2021)
- [Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games](https://mlsanity.com/paper/2110.01773/) (2021)
- [Auto-Differentiation of Relational Computations for Very Large Scale Machine Learning](https://mlsanity.com/paper/2306.00088/) (2023)
- [Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models](https://mlsanity.com/paper/2306.03249/) (2023)
- [Enhancing Hypergradients Estimation: A Study of Preconditioning and Reparameterization](https://mlsanity.com/paper/2402.16748/) (2024)
- [Automatic Differentiation of Optimization Algorithms with Time-Varying Updates](https://mlsanity.com/paper/2410.15923/) (2024)
- [Derivatives of Stochastic Gradient Descent in parametric optimization](https://mlsanity.com/paper/2405.15894/) (2024)

## Abstract (arXiv)

In min-min optimization or max-min optimization, one has to compute the gradient of a function defined as a minimum. In most cases, the minimum has no closed-form, and an approximation is obtained via an iterative algorithm. There are two usual ways of estimating the gradient of the function: using either an analytic formula obtained by assuming exactness of the approximation, or automatic differentiation through the algorithm. In this paper, we study the asymptotic error made by these estimators as a function of the optimization error. We find that the error of the automatic estimator is close to the square of the error of the analytic estimator, reflecting a super-efficiency phenomenon. The convergence of the automatic estimator greatly depends on the convergence of the Jacobian of the algorithm. We analyze it for gradient descent and stochastic gradient descent and derive convergence rates for the estimators in these cases. Our analysis is backed by numerical experiments on toy problems and on Wasserstein barycenter computation. Finally, we discuss the computational complexity of these estimators and give practical guidelines to chose between them.