# Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 101 references that are in the map.
- First posted on arXiv 29 Mar 2024.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [Matching Networks for One Shot Learning](https://mlsanity.com/paper/1606.04080/) (2016)
- [On First-Order Meta-Learning Algorithms](https://mlsanity.com/paper/1803.02999/) (2018)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Bilevel Optimization: Convergence Analysis and Enhanced Design](https://mlsanity.com/paper/2010.07962/) (2020)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Meta-learning via Language Model In-context Tuning](https://mlsanity.com/paper/2110.07814/) (2021)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions](https://mlsanity.com/paper/1903.03088/) (2019)
- [BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach](https://mlsanity.com/paper/2209.08709/) (2022)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Transfer Learning without Knowing: Reprogramming Black-box Machine Learning Models with Scarce Data and Limited Resources](https://mlsanity.com/paper/2007.08714/) (2020)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [ES-MAML: Simple Hessian-Free Meta Learning](https://mlsanity.com/paper/1910.01215/) (2019)
- [Model Agnostic Contrastive Explanations for Structured Data](https://mlsanity.com/paper/1906.00117/) (2019)
- [Bi-level Actor-Critic for Multi-agent Coordination](https://mlsanity.com/paper/1909.03510/) (2019)
- [How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/2203.14195/) (2022)
- [On the Convergence Theory for Hessian-Free Bilevel Algorithms](https://mlsanity.com/paper/2110.07004/) (2021)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions](https://mlsanity.com/paper/2306.12067/) (2023)
- [On Fast Adversarial Robustness Adaptation in Model-Agnostic Meta-Learning](https://mlsanity.com/paper/2102.10454/) (2021)
- [Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspective](https://mlsanity.com/paper/1901.11503/) (2019)

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

- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)
- [Fully First-Order Methods for Decentralized Bilevel Optimization](https://mlsanity.com/paper/2410.19319/) (2024)
- [Information-Theoretic Bayesian Optimization for Bilevel Optimization Problems](https://mlsanity.com/paper/2509.21725/) (2025)
- [Feed m Birds with One Scone: Accelerating Multi-task Gradient Balancing via Bi-level Optimization](https://mlsanity.com/paper/2603.07389/) (2026)
- [Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens](https://mlsanity.com/paper/2605.30960/) (2026)

## Abstract (arXiv)

In this paper, we study and analyze zeroth-order stochastic approximation algorithms for solving bilvel problems, when neither the upper/lower objective values, nor their unbiased gradient estimates are available. In particular, exploiting Stein's identity, we first use Gaussian smoothing to estimate first- and second-order partial derivatives of functions with two independent block of variables. We then used these estimates in the framework of a stochastic approximation algorithm for solving bilevel optimization problems and establish its non-asymptotic convergence analysis. To the best of our knowledge, this is the first time that sample complexity bounds are established for a fully stochastic zeroth-order bilevel optimization algorithm.