Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing

We are particularly interested in the setting where neither ex plicit knowledge about f,g are available nor their unbiased stochastic derivatives. In this zeroth-order setting, we assume that only noisy evaluations of f and g are available upon query to an oracle. The BLP problem was first introduced by Bracken and McGill in t he 1970s [7] followed by a more general form of problem involving joint constraints of outer and inner variables. This is a fundamental problem in engineering and economics with dire ct applications in problems such as decision making [48], supply chain [61, 59], network design [51, 43], transportation and planning [16, 83], and optimal design [4, 32]. More recently, BLP has f ound applications in many areas of machine learning and artificial intelligence. Zeroth-order methods apply to many optimization problems ( including the BLP) where for various reasons such as complexity, lack of access to an accurat e model, or computational limitations, there is no or limited access to the objective gradient.