Bilevel optimization has various applications such as hyper-parameter
optimization and meta-learning. Designing theoretically efficient algorithms
for bilevel optimization is more challenging than standard optimization because
the lower-level problem defines the feasibility set implicitly via another
optimization problem. One tractable case is when the lower-level problem
permits strong convexity. Recent works show that second-order methods can
provably converge to an $\epsilon$-first-order stationary point of the problem
at a rate of $\tilde{\mathcal{O}}(\epsilon^{-2})$, yet these algorithms require
a Hessian-vector product oracle. Kwon et al. (2023) resolved the problem by
proposing a first-order method that can achieve the same goal at a slower rate
of $\tilde{\mathcal{O}}(\epsilon^{-3})$. In this work, we provide an improved
analysis demonstrating that the first-order method can also find an
$\epsilon$-first-order stationary point within $\tilde
{\mathcal{O}}(\epsilon^{-2})$ oracle complexity, which matches the upper bounds
for second-order methods in the dependency on $\epsilon$. Our analysis further
leads to simple first-order algorithms that can achieve similar near-optimal
rates in finding second-order stationary points and in distributed bilevel
problems.

本文讨论了双层优化问题，提出了第一和第二阶段方法，探究了优化的复杂度和速度，并提出了适用于分布式双层问题的简单算法。