Theoretical properties of bilevel problems are well studied when the
lower-level problem is strongly convex. In this work, we focus on bilevel
optimization problems without the strong-convexity assumption. In these cases,
we first show that the common local optimality measures such as KKT condition
or regularization can lead to undesired consequences. Then, we aim to identify
the mildest conditions that make bilevel problems tractable. We identify two
classes of growth conditions on the lower-level objective that leads to
continuity. Under these assumptions, we show that the local optimality of the
bilevel problem can be defined via the Goldstein stationarity condition of the
hyper-objective. We then propose the Inexact Gradient-Free Method (IGFM) to
solve the bilevel problem, using an approximate zeroth order oracle that is of
independent interest. Our non-asymptotic analysis demonstrates that the
proposed method can find a $(\delta, \varepsilon)$ Goldstein stationary point
for bilevel problems with a zeroth order oracle complexity that is polynomial
in $d, 1/\delta$ and $1/\varepsilon$.

本文关注于无强凸性假设的双层优化问题中局部最优性条件的探讨，提出了两类下层目标的增长条件从而推导出 Goldstein 稳定性条件，并引入了 Inexact Gradient-Free Method 方法进行求解。