# Learning Theory for Kernel Bilevel Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 82 references that are in the map.
- First posted on arXiv 12 Feb 2025.

## Builds on (most cited first, 30 of 34)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Generalizing to Unseen Domains: A Survey on Domain Generalization](https://mlsanity.com/paper/2103.03097/) (2021)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Meta-learning with differentiable closed-form solvers](https://mlsanity.com/paper/1805.08136/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [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)
- [Efficient and Modular Implicit Differentiation](https://mlsanity.com/paper/2105.15183/) (2021)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Kernel Instrumental Variable Regression](https://mlsanity.com/paper/1906.00232/) (2019)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [On Penalty-based Bilevel Gradient Descent Method](https://mlsanity.com/paper/2302.05185/) (2023)
- [Learning Deep Features in Instrumental Variable Regression](https://mlsanity.com/paper/2010.07154/) (2020)
- [Towards Gradient-based Bilevel Optimization with Non-convex Followers and Beyond](https://mlsanity.com/paper/2110.00455/) (2021)
- [Amortized Implicit Differentiation for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2111.14580/) (2021)
- [On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation](https://mlsanity.com/paper/2309.01753/) (2023)
- [Density Estimation in Infinite Dimensional Exponential Families](https://mlsanity.com/paper/1312.3516/) (2013)
- [Provable Representation Learning for Imitation Learning via Bi-level Optimization](https://mlsanity.com/paper/2002.10544/) (2020)
- [Control-Oriented Model-Based Reinforcement Learning with Implicit Differentiation](https://mlsanity.com/paper/2106.03273/) (2021)
- [Stability and Generalization of Bilevel Programming in Hyperparameter Optimization](https://mlsanity.com/paper/2106.04188/) (2021)
- [Non-Convex Bilevel Games with Critical Point Selection Maps](https://mlsanity.com/paper/2207.04888/) (2022)
- [Value-Function-based Sequential Minimization for Bi-level Optimization](https://mlsanity.com/paper/2110.04974/) (2021)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Functional Bilevel Optimization for Machine Learning](https://mlsanity.com/paper/2403.20233/) (2024)
- [Generalization Guarantees for Neural Architecture Search with Train-Validation Split](https://mlsanity.com/paper/2104.14132/) (2021)
- [Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms](https://mlsanity.com/paper/2405.14778/) (2024)
- [Physics-informed kernel learning](https://mlsanity.com/paper/2409.13786/) (2024)

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

- [Functional Natural Policy Gradients](https://mlsanity.com/paper/2603.28681/) (2026)
- [Semiparametric Efficient Bilevel Gradient Estimation](https://mlsanity.com/paper/2605.21341/) (2026)

## Abstract (arXiv)

Bilevel optimization has emerged as a technique for addressing a wide range of machine learning problems that involve an outer objective implicitly determined by the minimizer of an inner problem. While prior works have primarily focused on the parametric setting, a learning-theoretic foundation for bilevel optimization in the nonparametric case remains relatively unexplored. In this paper, we take a first step toward bridging this gap by studying Kernel Bilevel Optimization (KBO), where the inner objective is optimized over a reproducing kernel Hilbert space. This setting enables rich function approximation while providing a foundation for rigorous theoretical analysis. In this context, we derive novel finite-sample generalization bounds for KBO, leveraging tools from empirical process theory. These bounds further allow us to assess the statistical accuracy of gradient-based methods applied to the empirical discretization of KBO. We numerically illustrate our theoretical findings on a synthetic instrumental variable regression task.