Stochastic Bilevel Optimization with Heavy-Tailed Noise

Summary

This paper studies smooth bilevel optimization with a strongly convex lower-level problem and a possibly nonconvex upper-level problem, under stochastic gradients with heavy-tailed noise. The authors propose a nested-loop method, N$^2$SBA, reaching an $\epsilon$-stationary point with SFO complexity $\tilde{\mathcal{O}}\big(\kappa^{\frac{7p-3}{p-1}} \sigma^{\frac{p}{p-1}} \epsilon^{-\frac{4 p - 2}{p-1}}\big)$, where $p\in(1,2]$ is the noise moment order. For nonconvex-strongly-concave minimax problems the method achieves a matching-style bound, and all bounds match the best known results at $p=2$.