Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions

Understand

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.