双层优化中寻找静止点的近最优全一阶算法
通过使用 y^*-aware oracle,我们提出了一种简单的一阶方法,它可以使用 O (ε^{-6}),O (ε^{-4}) 的一阶 y^*-aware oracles 来收敛到一个 ε 稳定点。
Feb, 2024
具有有限时间超梯度稳定性保证的一阶线性约束优化方法在双层优化中遇到了带有高维度的 Hessian 计算,尽管最近的研究提供了非约束双层问题的一阶方法,但约束设置仍然相对较少探讨。我们提出了一种具有有限时间超梯度稳定性保证的一阶线性约束优化方法,在线性等式约束下,我们可以在 O (ϵ^{-2}) 次梯度预言调用中获得 ϵ- 稳定性,这几近是最优的。在线性不等式约束下,我们可以在 O (dδ^{-1}ϵ^{-3}) 次梯度预言调用中获得 (δ,ϵ)-Goldstein 稳定性,其中 d 是上层维度。最后,我们在额外假设有对最优对偶变量的 oracle 访问的情况下,在线性不等式设置下获得无维度的 O (δ^{-1}ϵ^{-4}) 的 oracle 复杂度。在此过程中,我们发展了新的非平滑非凸优化方法来处理不完全的预言。我们通过初步的数值实验验证了这些保证。
Jun, 2024
本研究提出一种全一阶随机逼近方法用于解决双层无约束随机优化问题,该方法具有收敛性及优异的实际性能,并且可以使用动量辅助的梯度估计器进一步提高收敛速度。
Jan, 2023
本文主要研究双层优化的一阶算法,目标函数在两个层次上都是光滑但可能非凸的,变量限制在闭凸集合中。首先通过罚函数方法,研究了双层优化的景观,并建立了罚函数与超目标之间的强连接。接着,提出了一阶算法来优化罚函数,以找到一个 ε- 稳定解。在满足小误差近似条件的情况下,算法以 O (ε^{-3}) 和 O (ε^{-7}) 程度的复杂度达到 ε- 稳定点。在随机预言机的额外假设下,算法的实现可以完全使用单循环方式,并分别达到 O (ε^{-3}) 和 O (ε^{-5}) 的优化复杂度。
Sep, 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
本文提出了一种新的 Hessian/Jacobian-free 双层优化器 FdeHBO,通过每次迭代使用 O (1) 个样本和仅一阶梯度信息,在非凸 - 强凸随机双层优化中实现了 O (ε^(-1.5)) 样本复杂度,达到 ε- 精确的稳定点。
Dec, 2023
本文关注于无强凸性假设的双层优化问题中局部最优性条件的探讨,提出了两类下层目标的增长条件从而推导出 Goldstein 稳定性条件,并引入了 Inexact Gradient-Free Method 方法进行求解。
Jan, 2023
本文提出了一种基于一阶梯度信息的简单双层优化算法,适用于深度学习中大规模的非凸函数,无需隐式微分,并有指导其在非凸优化问题上收敛于驻点的收敛性分析证明,实验结果表明其优越的性能表现。
Sep, 2022
设计了一种名为 BO-REP 的新的双层优化算法,用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下,该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点,结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。
Jan, 2024
本文针对双层 (随机) 优化问题,探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系,并在一般性情形下给出了稳定性界限的分析,通过实验证明了迭代次数对泛化误差的影响。
Oct, 2022