Stochastic Bilevel Optimization with Heavy-Tailed Noise

arXiv:2509.14952v3 Announce Type: replace Abstract: This paper considers the smooth bilevel optimization in which the lower-level problem is strongly convex and the upper-level problem is possibly nonconvex. We focus on the stochastic setting where the algorithm can access the unbiased stochastic gradient evaluation with heavy-tailed noise, which is prevalent in many machine learning applications, such as training large language models and reinforcement learning. We propose a nested-loop normalized stochastic bilevel approximation (N^2SBA) for finding an epsilon-stationary point with the stochastic first-order oracle (SFO) complexity of ilde{O}ig(kappa^{frac{7p-3}{p-1}} sigma^{frac{p}{p-1}} epsilon^{-frac{4 p - 2}{p-1}}ig), where kappa is the condition number, pin(1,2] is the order of central moment for the noise, and sigma is the noise level. Furthermore, we specialize our idea to solve the nonconvex-strongly-concave minimax optimization problem, achieving an epsilon-stationary point with the SFO complexity of~ilde{mathcal O}ig(kappa^{frac{2p-1}{p-1}} sigma^{frac{p}{p-1}} epsilon^{-frac{3p-2}{p-1}}ig). All the above upper bounds match the best-known results under the special case of the bounded variance setting, i.e., p=2. We also conduct the numerical experiments to show the empirical superiority of the proposed methods.

Source: arXiv cs.LG | 2026-09-28