一种用于随机双层优化的单时间尺度方法
本文针对双层 (随机) 优化问题,探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系,并在一般性情形下给出了稳定性界限的分析,通过实验证明了迭代次数对泛化误差的影响。
Oct, 2022
本文提出了一种新算法:单时间尺度双动量随机逼近算法(SUSTAIN),用于解决随机无约束双层优化问题,重点关注下层子问题为强凸的双层问题和上层目标函数光滑情况下的解决方案,通过设计一种随机动量辅助梯度估计器来控制解决子问题的不准确性带来的随机梯度更新的误差,从而实现解决双层最优化问题的目的,其样本复杂度与传统单层随机梯度算法的最优复杂度相当。
Feb, 2021
本研究提出一种全一阶随机逼近方法用于解决双层无约束随机优化问题,该方法具有收敛性及优异的实际性能,并且可以使用动量辅助的梯度估计器进一步提高收敛速度。
Jan, 2023
我们研究了一类随机二级优化问题,引入了一种新颖的随机二级优化方法,通过随机切割平面局部逼近下层问题的解集,并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下,我们的方法需要最多 $\tilde {\mathcal {O}}(\max\{1/\epsilon_f^{2},1/\epsilon_g^{2}\})$ 个随机 oracle 查询,得到一个上层函数精度为 $\epsilon_f$、下层函数精度为 $\epsilon_g$ 的解,这一保证改进了之前已知的复杂性 $\mathcal {O}(\max\{1/\epsilon_f^{4},1/\epsilon_g^{4}\})$。此外,在上层函数为非凸函数的情况下,我们的方法需要最多 $\tilde {\mathcal {O}}(\max\{1/\epsilon_f^{3},1/\epsilon_g^{3}\})$ 个随机 oracle 查询,找到一个 $(\epsilon_f, \epsilon_g)$- 稳定点。在有限和问题设置中,对于凸和非凸情况下,我们的方法所需的随机 oracle 调用次数分别为 $\tilde {\mathcal {O}}(\sqrt {n}/\epsilon)$ 和 $\tilde {\mathcal {O}}(\sqrt {n}/\epsilon^{2})$,其中 $\epsilon=\min \{\epsilon_f,\epsilon_g\}$。
Aug, 2023
设计了一种名为 BO-REP 的新的双层优化算法,用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下,该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点,结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。
Jan, 2024
本文提出了快速随机化算法来解决非凸随机双层优化问题,在 Lipschitz 连续条件下建立了单一下层问题和具有 $m>1$ 个下层问题(多任务 SBO)的非凸 SBO 的样本复杂度,以及在梯度主导函数下的更快收敛结果。
May, 2021
本研究提出了一种新的方法来解决大规模实证风险最小化中双层优化问题的梯度计算难以求解的问题,设计了 SABA(基于 SAGA 算法的)全局方差缩减算法,该算法收敛速度达到了 $O (rac1T)$, 实现了线性收敛,并得到了实验证明。
Jan, 2022
在这篇论文中,我们考虑了分散网络中的双层优化问题,提出了一种针对具有强凸下层问题的分散式双层优化的新型单循环算法。我们的算法完全是单循环算法,在逼近超梯度时不需要进行复杂的矩阵向量乘法。此外,与现有的分散式双层优化和联邦双层优化方法不同的是,我们的算法不需要任何梯度异质性假设。我们的分析结果显示,该算法达到了迄今为止双层优化算法的最佳收敛速度。
Nov, 2023