Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimization

Understand

Stochastic bilevel optimization, which captures the inherent nested structure of machine learning problems, is gaining popularity in many recent applications.

• Existing works on bilevel optimization mostly consider either unconstrained problems or constrained upper-level problems.
• This paper considers the stochastic bilevel optimization problems with equality constraints both in the upper and lower levels.
• By leveraging the special structure of the equality constraints problem, the paper first presents an alternating implicit projected SGD approach and establishes the $\tilde{\cal O}(\epsilon^{-2})$ sample complexity that matches the state-of-the-art complexity of ALSET \citep{chen2021closing} for unconstrained bilevel problems.