具有非光滑低层问题的基于梯度的双层优化技术
本研究关注简单的双层优化问题,提出一种新的双层优化方法,利用切割平面方法局部近似解决方案集合,应用加速梯度更新来减小上层目标函数,以实现子优性和不可行性错误的非渐近收敛保证。
Feb, 2024
本文研究一类内部目标函数为强凸函数的双层规划问题,给出了一种求解该问题的逼近算法,并在外部目标函数为不同凸性的情况下提供了其有限时间收敛分析。同时,提出了一种加速变体以提高收敛速度,并推广了结果到只有有限的信息可用的随机情况下。本文是第一次为双层规划提供了已确定的迭代复杂度(样本复杂度)的(随机)逼近算法。
Feb, 2018
本文提出了一种使用 Bregman 距离、具有低计算复杂度的增强型双层优化方法 BiO-BreD 和 SBiO-BreD,以解决双层优化问题,该问题的外部子问题非凸且可能非光滑,内部子问题强凸。通过数据超清理任务和超表征学习任务,证明了所提出的算法优于相关的双层优化方法。
Jul, 2021
本文提出了一种一阶 Bi-Sub-Gradient 方法,它被广泛应用于凸性双层优化问题中,具有易于实现、内外两个目标函数均能取得亚线性收敛速度等特点,并且证明了所生成的序列与双层问题最优解的距离趋于零。
Jul, 2023
设计了一种名为 BO-REP 的新的双层优化算法,用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下,该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点,结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。
Jan, 2024
本文研究凸双层优化问题,其中内层最小化平滑函数和非凸函数的和,外层旨在在内层问题的最优解集合上最小化平滑且强凸的函数。我们分析了一个基于现有不动点算法的一阶方法,通过内部目标函数值建立了方法的全局次线性收敛率。
Feb, 2017
提出了一种推广后的交替优化方法(GALET)用于双层优化问题,可以适用于具有非凸下层目标函数的问题,并具有与一阶梯度下降相同的收敛速度。
Jun, 2023
我们提出了一类基于镜像下降的高效自适应双层优化方法,用于求解非凸双层优化问题,其中上层问题可能是非凸的且具有非光滑正则化,而下层问题也是非凸的但满足 Polyak-Lojasiewicz 条件。我们提出了一种基于镜像下降的高效自适应投影梯度方法来解决确定性双层问题,并证明其在寻找非凸双层问题的 ε- 稳定解时具有已知最好的梯度复杂度 O (ε^(-1))。为了解决随机双层问题,我们提出了一种基于镜像下降和方差约减技术的高效自适应随机投影梯度方法,并证明其在寻找 ε- 稳定解时具有已知最好的梯度复杂度 O (ε^(-3/2))。由于 Polyak-Lojasiewicz 条件放宽了强凸性,我们的算法可以用于非凸强凸双层优化问题。从理论上讲,我们在一些温和条件下提供了有用的收敛性分析框架,并证明了我们的方法具有较快的收敛速度 O (1/T),其中 T 表示迭代次数。
Nov, 2023
本文研究使用零阶随机逼近算法解决双层问题,无论是上 / 下目标值还是它们的无偏梯度估计都不可用。通过利用斯坦恩恒等式,首先使用高斯平滑估计具有两个独立块变量的函数的一阶和二阶偏导数。然后,在随机逼近算法框架中使用这些估计来解决双层优化问题,并建立其非渐近收敛分析。据我们所知,这是第一次为完全随机零阶双层优化算法建立样本复杂度界限。
Mar, 2024
我们研究了一类随机二级优化问题,引入了一种新颖的随机二级优化方法,通过随机切割平面局部逼近下层问题的解集,并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下,我们的方法需要最多 $\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