# Bilevel Optimization with a Lower-level Contraction: Optimal Sample Complexity without Warm-start arXiv: https://arxiv.org/abs/2202.03397 · HTML: https://mlsanity.com/paper/2202.03397/ ## Key facts - Cited by 17 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 51 references that are in the map. - First posted on arXiv 7 Feb 2022. ## Builds on (most cited first, 30 of 31) - [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019) - [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017) - [Matching Networks for One Shot Learning](https://mlsanity.com/paper/1606.04080/) (2016) - [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018) - [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016) - [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019) - [Meta-Learning with Implicit Gradients](https://mlsanity.com/paper/1909.04630/) (2019) - [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018) - [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015) - [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019) - [Optimizing Millions of Hyperparameters by Implicit Differentiation](https://mlsanity.com/paper/1911.02590/) (2019) - [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018) - [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017) - [Hyperparameter optimization with approximate gradient](https://mlsanity.com/paper/1602.02355/) (2016) - [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020) - [Towards Poisoning of Deep Learning Algorithms with Back-gradient Optimization](https://mlsanity.com/paper/1708.08689/) (2017) - [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020) - [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021) - [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021) - [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020) - [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021) - [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021) - [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016) - [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021) - [Implicit differentiation of Lasso-type models for hyperparameter optimization](https://mlsanity.com/paper/2002.08943/) (2020) - [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021) - [A General Descent Aggregation Framework for Gradient-based Bi-level Optimization](https://mlsanity.com/paper/2102.07976/) (2021) - [Implicit differentiation for fast hyperparameter selection in non-smooth convex learning](https://mlsanity.com/paper/2105.01637/) (2021) - [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021) - [Convergence Properties of Stochastic Hypergradients](https://mlsanity.com/paper/2011.07122/) (2020) ## Built on by (most cited first, 17 of 17) - [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023) - [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022) - [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024) - [Bilevel reinforcement learning via the development of hyper-gradient without lower-level convexity](https://mlsanity.com/paper/2405.19697/) (2024) - [On The Sample Complexity Bounds In Bilevel Reinforcement Learning](https://mlsanity.com/paper/2503.17644/) (2025) - [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024) - [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024) - [Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation](https://mlsanity.com/paper/2402.02857/) (2024) - [Taught Well Learned Ill: Towards Distillation-conditional Backdoor Attack](https://mlsanity.com/paper/2509.23871/) (2025) - [BLISS: A Lightweight Bilevel Influence Scoring Method for Data Selection in Language Model Pretraining](https://mlsanity.com/paper/2510.06048/) (2025) - [TANDEM: Bi-Level Data Mixture Optimization with Twin Networks](https://mlsanity.com/paper/2606.04401/) (2026) - [Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates](https://mlsanity.com/paper/2403.11687/) (2024) - [Improved Sample Complexity For Diffusion Model Training Without Empirical Risk Minimizer Access](https://mlsanity.com/paper/2505.18344/) (2025) - [BLADE: Scalable Bi-level Adaptive Data Selection for LLM Training](https://mlsanity.com/paper/2606.18650/) (2026) - [Derivatives of Stochastic Gradient Descent in parametric optimization](https://mlsanity.com/paper/2405.15894/) (2024) - [Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning](https://mlsanity.com/paper/2602.00282/) (2026) - [Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity](https://mlsanity.com/paper/2607.28849/) (2026) ## Abstract (arXiv) We analyse a general class of bilevel problems, in which the upper-level problem consists in the minimization of a smooth objective function and the lower-level problem is to find the fixed point of a smooth contraction map. This type of problems include instances of meta-learning, equilibrium models, hyperparameter optimization and data poisoning adversarial attacks. Several recent works have proposed algorithms which warm-start the lower-level problem, i.e.~they use the previous lower-level approximate solution as a staring point for the lower-level solver. This warm-start procedure allows one to improve the sample complexity in both the stochastic and deterministic settings, achieving in some cases the order-wise optimal sample complexity. However, there are situations, e.g., meta learning and equilibrium models, in which the warm-start procedure is not well-suited or ineffective. In this work we show that without warm-start, it is still possible to achieve order-wise (near) optimal sample complexity. In particular, we propose a simple method which uses (stochastic) fixed point iterations at the lower-level and projected inexact gradient descent at the upper-level, that reaches an ε-stationary point using O(ε-2) and tildeO(ε-1) samples for the stochastic and the deterministic setting, respectively. Finally, compared to methods using warm-start, our approach yields a simpler analysis that does not need to study the coupled interactions between the upper-level and lower-level iterates.