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}) 的优化复杂度。

非凸双层优化与一阶随机逼近的惩罚方法

On Penalty Methods for Nonconvex Bilevel Optimization and First-Order  Stochastic Approximation

In this paper, we propose a class of penalty methods with stochastic
approximation for solving stochastic nonlinear programming problems. We assume
that only noisy gradients or function values of the objective function are
available via calls to a stochastic first-order or zeroth-order oracle. In each
iteration of the proposed methods, we minimize an exact penalty function which
is nonsmooth and nonconvex with only stochastic first-order or zeroth-order
information available. Stochastic approximation algorithms are presented for
solving this particular subproblem. The worst-case complexity of calls to the
stochastic first-order (or zeroth-order) oracle for the proposed penalty
methods for obtaining an $\epsilon$-stochastic critical point is analyzed.

提出一种基于随机逼近的罚函数方法来解决非线性规划问题，利用噪声梯度或函数值来调用随机一阶或零阶神经网络，通过最小化随机一阶或零阶信息可用的非光滑、非凸罚函数的方法来优化。分析了该罚函数方法通过调用随机一阶（或零阶）神经网络获取 ε- 随机临界点的最坏情况复杂度。