Stochastic Bilevel optimization usually involves minimizing an upper-level
(UL) function that is dependent on the arg-min of a strongly-convex lower-level
(LL) function. Several algorithms utilize Neumann series to approximate certain
matrix inverses involved in estimating the implicit gradient of the UL function
(hypergradient). The state-of-the-art StOchastic Bilevel Algorithm (SOBA) [16]
instead uses stochastic gradient descent steps to solve the linear system
associated with the explicit matrix inversion. This modification enables SOBA
to match the lower bound of sample complexity for the single-level counterpart
in non-convex settings. Unfortunately, the current analysis of SOBA relies on
the assumption of higher-order smoothness for the UL and LL functions to
achieve optimality. In this paper, we introduce a novel fully single-loop and
Hessian-inversion-free algorithmic framework for stochastic bilevel
optimization and present a tighter analysis under standard smoothness
assumptions (first-order Lipschitzness of the UL function and second-order
Lipschitzness of the LL function). Furthermore, we show that by a slight
modification of our approach, our algorithm can handle a more general
multi-objective robust bilevel optimization problem. For this case, we obtain
the state-of-the-art oracle complexity results demonstrating the generality of
both the proposed algorithmic and analytic frameworks. Numerical experiments
demonstrate the performance gain of the proposed algorithms over existing ones.

本文提出了一种新的完全单循环和免除海森矩阵的算法框架，用于随机双层优化，并在标准光滑性假设下提出了更紧密的分析，进而展示了算法的普遍性。