一种能够实现随机和全局方差缩减算法的双层优化框架
我们研究了一类随机二级优化问题,引入了一种新颖的随机二级优化方法,通过随机切割平面局部逼近下层问题的解集,并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下,我们的方法需要最多 $\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
本文提出了快速随机化算法来解决非凸随机双层优化问题,在 Lipschitz 连续条件下建立了单一下层问题和具有 $m>1$ 个下层问题(多任务 SBO)的非凸 SBO 的样本复杂度,以及在梯度主导函数下的更快收敛结果。
May, 2021
本文研究使用零阶随机逼近算法解决双层问题,无论是上 / 下目标值还是它们的无偏梯度估计都不可用。通过利用斯坦恩恒等式,首先使用高斯平滑估计具有两个独立块变量的函数的一阶和二阶偏导数。然后,在随机逼近算法框架中使用这些估计来解决双层优化问题,并建立其非渐近收敛分析。据我们所知,这是第一次为完全随机零阶双层优化算法建立样本复杂度界限。
Mar, 2024
该论文提出了两种新的随机算法,使用先进的分块方差减少技术来跟踪 Hessian 矩阵,解决了多块双层优化问题的挑战,证明了其收敛性和高效性,在机器学习等领域具有重要的应用。
May, 2023
本研究提出一种全一阶随机逼近方法用于解决双层无约束随机优化问题,该方法具有收敛性及优异的实际性能,并且可以使用动量辅助的梯度估计器进一步提高收敛速度。
Jan, 2023
本文研究分布式环境下的联邦双层优化问题,并针对性地提出了 FedBiO 和 FedBiOAcc 两种优化算法,用于解决团体公平的联邦学习任务,数值实验表明,与其他基线算法相比,该算法在性能上表现更优。
May, 2022
本文针对双层 (随机) 优化问题,探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系,并在一般性情形下给出了稳定性界限的分析,通过实验证明了迭代次数对泛化误差的影响。
Oct, 2022