mlsanityData to 7 Oct 2026

Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing

arXiv 2404.00158 ↗First posted 29 Mar 2024math.OC cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

39 of 101 references.

References · 39

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2017Prototypical Networks for Few-shot Learningcited by 3,001
  3. 2016Matching Networks for One Shot Learningcited by 2,246
  4. 2018On First-Order Meta-Learning Algorithmscited by 1,003
  5. 2020Meta-Learning in Neural Networks: A Surveycited by 944
  6. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  7. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 499
  8. 2018Bilevel Programming for Hyperparameter Optimization and Meta-Learningcited by 403
  9. 2018Approximation Methods for Bilevel Programmingcited by 231
  10. 2020Bilevel Optimization: Convergence Analysis and Enhanced Designcited by 219
  11. 2021Learning to Optimize: A Primer and A Benchmarkcited by 206
  12. 2020Coresets via Bilevel Optimization for Continual Learning and Streamingcited by 191
27 more
  1. 2021Meta-learning via Language Model In-context Tuningcited by 163
  2. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 160
  3. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  4. 2018AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networkscited by 137
  5. 2019Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functionscited by 104
  6. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 103
  7. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  8. 2020Transfer Learning without Knowing: Reprogramming Black-box Machine Learning Models with Scarce Data and Limited Resourcescited by 83
  9. 2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
  10. 2019ES-MAML: Simple Hessian-Free Meta Learningcited by 57
  11. 2019Model Agnostic Contrastive Explanations for Structured Datacited by 41
  12. 2022How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspectivecited by 39
  13. 2019Bi-level Actor-Critic for Multi-agent Coordinationcited by 38
  14. 2021On the Convergence Theory for Hessian-Free Bilevel Algorithmscited by 33
  15. 2021Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimizationcited by 32
  16. 2023Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditionscited by 31
  17. 2021On Fast Adversarial Robustness Adaptation in Model-Agnostic Meta-Learningcited by 29
  18. 2019Contrasting Exploration in Parameter and Action Space: A Zeroth-Order Optimization Perspectivecited by 26
  19. 2023Learning to Learn from APIs: Black-Box Data-Free Meta-Learningcited by 18
  20. 2021ZARTS: On Zero-order Optimization for Neural Architecture Searchcited by 17
  21. 2021Optimizing Large-Scale Hyperparameters via Automated Learning Algorithmcited by 13
  22. 2020Bilevel Continual Learningcited by 10
  23. 2019Learning to Learn by Zeroth-Order Oraclecited by 9
  24. 2023Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimizationcited by 8
  25. 2020Inexact Derivative-Free Optimization for Bilevel Learningcited by 7
  26. 2023Achieving O(ε-1.5) Complexity in Hessian/Jacobian-free Stochastic Bilevel Optimizationcited by 2
  27. 2021On the Numerical Performance of Derivative-Free Optimization Methods Based on Finite-Difference Approximationscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 2.

6 papers.

  1. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  2. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  3. 2024Fully First-Order Methods for Decentralized Bilevel Optimizationcited by 1
  4. 2025Information-Theoretic Bayesian Optimization for Bilevel Optimization Problemscited by 0
  5. 2026Feed m Birds with One Scone: Accelerating Multi-task Gradient Balancing via Bi-level Optimizationcited by 0
  6. 2026Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lenscited by 0