# Convergence Properties of Stochastic Hypergradients

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2020.

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

- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [iDARTS: Differentiable Architecture Search with Stochastic Implicit Gradients](https://mlsanity.com/paper/2106.10784/) (2021)
- [On Implicit Bias in Overparameterized Bilevel Optimization](https://mlsanity.com/paper/2212.14032/) (2022)
- [Probabilistic Bilevel Coreset Selection](https://mlsanity.com/paper/2301.09880/) (2023)
- [Implicit differentiation for fast hyperparameter selection in non-smooth convex learning](https://mlsanity.com/paper/2105.01637/) (2021)
- [Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start](https://mlsanity.com/paper/2202.03397/) (2022)
- [Reward Optimization for Neural Machine Translation with Learned Metrics](https://mlsanity.com/paper/2104.07541/) (2021)
- [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024)
- [Analyzing Inexact Hypergradients for Bilevel Learning](https://mlsanity.com/paper/2301.04764/) (2023)
- [Passage-Mask: A Learnable Regularization Strategy for Retriever-Reader Models](https://mlsanity.com/paper/2211.00915/) (2022)
- [BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization](https://mlsanity.com/paper/2305.18666/) (2023)
- [Simple and Effective Gradient-Based Tuning of Sequence-to-Sequence Models](https://mlsanity.com/paper/2209.04683/) (2022)
- [Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates](https://mlsanity.com/paper/2403.11687/) (2024)
- [Bilevel Learning with Inexact Stochastic Gradients](https://mlsanity.com/paper/2412.12049/) (2024)
- [A Challenge in Reweighting Data with Bilevel Optimization](https://mlsanity.com/paper/2310.17386/) (2023)
- [Derivatives of Stochastic Gradient Descent in parametric optimization](https://mlsanity.com/paper/2405.15894/) (2024)

## Abstract (arXiv)

Bilevel optimization problems are receiving increasing attention in machine learning as they provide a natural framework for hyperparameter optimization and meta-learning. A key step to tackle these problems is the efficient computation of the gradient of the upper-level objective (hypergradient). In this work, we study stochastic approximation schemes for the hypergradient, which are important when the lower-level problem is empirical risk minimization on a large dataset. The method that we propose is a stochastic variant of the approximate implicit differentiation approach in (Pedregosa, 2016). We provide bounds for the mean square error of the hypergradient approximation, under the assumption that the lower-level problem is accessible only through a stochastic mapping which is a contraction in expectation. In particular, our main bound is agnostic to the choice of the two stochastic solvers employed by the procedure. We provide numerical experiments to support our theoretical analysis and to show the advantage of using stochastic hypergradients in practice.