In this work, we study first-order algorithms for solving Bilevel
Optimization (BO) where the objective functions are smooth but possibly
nonconvex in both levels and the variables are restricted to closed convex
sets. As a first step, we study the landscape of BO through the lens of penalty
methods, in which the upper- and lower-level objectives are combined in a
weighted sum with penalty parameter $\sigma > 0$. In particular, we establish a
strong connection between the penalty function and the hyper-objective by
explicitly characterizing the conditions under which the values and derivatives
of the two must be $O(\sigma)$-close. A by-product of our analysis is the
explicit formula for the gradient of hyper-objective when the lower-level
problem has multiple solutions under minimal conditions, which could be of
independent interest. Next, viewing the penalty formulation as
$O(\sigma)$-approximation of the original BO, we propose first-order algorithms
that find an $\epsilon$-stationary solution by optimizing the penalty
formulation with $\sigma = O(\epsilon)$. When the perturbed lower-level problem
uniformly satisfies the small-error proximal error-bound (EB) condition, we
propose a first-order algorithm that converges to an $\epsilon$-stationary
point of the penalty function, using in total $O(\epsilon^{-3})$ and
$O(\epsilon^{-7})$ accesses to first-order (stochastic) gradient oracles when
the oracle is deterministic and oracles are noisy, respectively. Under an
additional assumption on stochastic oracles, we show that the algorithm can be
implemented in a fully {\it single-loop} manner, i.e., with $O(1)$ samples per
iteration, and achieves the improved oracle-complexity of $O(\epsilon^{-3})$
and $O(\epsilon^{-5})$, respectively.

本文主要研究双层优化的一阶算法，目标函数在两个层次上都是光滑但可能非凸的，变量限制在闭凸集合中。首先通过罚函数方法，研究了双层优化的景观，并建立了罚函数与超目标之间的强连接。接着，提出了一阶算法来优化罚函数，以找到一个 ε- 稳定解。在满足小误差近似条件的情况下，算法以 O (ε^{-3}) 和 O (ε^{-7}) 程度的复杂度达到 ε- 稳定点。在随机预言机的额外假设下，算法的实现可以完全使用单循环方式，并分别达到 O (ε^{-3}) 和 O (ε^{-5}) 的优化复杂度。