{"ID":2869349,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.14952","arxiv_id":"2509.14952","title":"Stochastic Bilevel Optimization with Heavy-Tailed Noise","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$^2$SBA) for finding an $ε$-stationary point with the stochastic first-order oracle (SFO) complexity of $\\tilde{\\mathcal{O}}\\big(κ^{\\frac{7p-3}{p-1}} σ^{\\frac{p}{p-1}} ε^{-\\frac{4 p - 2}{p-1}}\\big)$, where $κ$ is the condition number, $p\\in(1,2]$ is the order of central moment for the noise, and $σ$ is the noise level. Furthermore, we specialize our idea to solve the nonconvex-strongly-concave minimax optimization problem, achieving an $ε$-stationary point with the SFO complexity of~$\\tilde{\\mathcal O}\\big(κ^{\\frac{2p-1}{p-1}} σ^{\\frac{p}{p-1}} ε^{-\\frac{3p-2}{p-1}}\\big)$. 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.","short_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 ma...","url_abs":"https://arxiv.org/abs/2509.14952","url_pdf":"https://arxiv.org/pdf/2509.14952v2","authors":"[\"Zhuanghua Liu\",\"Luo Luo\"]","published":"2025-09-18T13:37:40Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[\"Reinforcement Learning\",\"Language Model\"]","has_code":false}