Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationSimilar Papers 제목 키워드 기반
Bilevel ZOFO: Bridging Parameter-Efficient and Zeroth-Order Techniques for Efficient LLM Fine-Tuning and Meta-Training
Fine-tuning pre-trained Large Language Models (LLMs) for downstream tasks using First-Order (FO) optimizers presents significant computational challenges. Parameter-Efficient Fine-Tuning(PEFT) methods have been proposed …
Bilevel Optimizationparameter-efficient fine-tuningOn the Convergence Theory for Hessian-Free Bilevel Algorithms
Bilevel optimization has arisen as a powerful tool in modern machine learning. However, due to the nested structure of bilevel optimization, even gradient-based methods require second-order derivative approximations via …
Bilevel OptimizationMeta-LearningStochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Online bilevel optimization (OBO) is a powerful framework for machine learning problems where both outer and inner objectives evolve over time, requiring dynamic updates. Current OBO approaches rely on deterministic \tex…
Bilevel OptimizationImplicit Bilevel Optimization: Differentiating through Bilevel Optimization Programming
Bilevel Optimization Programming is used to model complex and conflicting interactions between agents, for example in Robust AI or Privacy-preserving AI. Integrating bilevel mathematical programming within deep learning …
Bilevel OptimizationPrivacy PreservingBiGrad: Differentiating through Bilevel Optimization Programming
Integrating mathematical programming, and in particular Bilevel Optimization Programming, within deep learning architectures has vast applications in various domains from machine learning to engineering. Bilevel program…
BIG-bench Machine LearningBilevel OptimizationCombinatorial Optimization