针对噪声分布极重尾的双层优化问题，提出高效算法并证明其理论性能。
Stochastic Bilevel Optimization with Heavy-Tailed Noise
- 设计带归一化的嵌套循环随机算法，处理重尾噪声下的双层优化
- 首次在重尾噪声下实现最优阶的复杂度，比传统方法更鲁棒
- 适用于大模型训练和强化学习等实际场景，尤其适合噪声不稳定的任务
本文研究平滑的双层优化问题，其中下层问题为强凸，上层问题可能非凸。在随机设置下，算法仅能访问带有重尾噪声的无偏随机梯度，这在训练大语言模型和强化学习中普遍存在。我们提出一种嵌套循环归一化随机双层近似（N²SBA）算法，求解 ε-驻点的随机一阶预言机（SFO）复杂度为 $ ilde{ ext{O}}ig(κ^{ rac{7p-3}{p-1}} σ^{ rac{p}{p-1}} ε^{- rac{4 p - 2}{p-1}}ig)$，其中 $κ$ 为条件数，$packslashin(1,2]$ 为噪声的中心矩阶数，$σ$ 为噪声水平。进一步将该思想应用于非凸-强凹极小极大优化问题，获得 $ε$-驻点的 SFO 复杂度为 $ ilde{ ext{O}}ig(κ^{ rac{2p-1}{p-1}} σ^{ rac{p}{p-1}} ε^{- rac{3p-2}{p-1}}ig)$。所有上界在 $p=2$（有界方差）的特殊情形下达到已知最优。数值实验验证了所提方法的实证优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。