Jan, 2023

关于非下层强凸性的双层优化问题

PDF
TL;DR本文关注于无强凸性假设的双层优化问题中局部最优性条件的探讨，提出了两类下层目标的增长条件从而推导出 Goldstein 稳定性条件，并引入了 Inexact Gradient-Free Method 方法进行求解。
发现论文，激发创造
  • 无投影方法用于具有凸下层问题的随机简单双层优化

    我们研究了一类随机二级优化问题，引入了一种新颖的随机二级优化方法，通过随机切割平面局部逼近下层问题的解集，并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下，我们的方法需要最多 $\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

  • 一种通用的交替方法用于满足 Polyak-Łojasiewicz 条件的二层优化

    提出了一种推广后的交替优化方法（GALET）用于双层优化问题，可以适用于具有非凸下层目标函数的问题，并具有与一阶梯度下降相同的收敛速度。

    Jun, 2023

  • 用于简单双层优化的加速梯度方法和凸下层问题

    本研究关注简单的双层优化问题，提出一种新的双层优化方法，利用切割平面方法局部近似解决方案集合，应用加速梯度更新来减小上层目标函数，以实现子优性和不可行性错误的非渐近收敛保证。

    Feb, 2024

  • 双层规划的近似方法

    本文研究一类内部目标函数为强凸函数的双层规划问题，给出了一种求解该问题的逼近算法，并在外部目标函数为不同凸性的情况下提供了其有限时间收敛分析。同时，提出了一种加速变体以提高收敛速度，并推广了结果到只有有限的信息可用的随机情况下。本文是第一次为双层规划提供了已确定的迭代复杂度（样本复杂度）的（随机）逼近算法。

    Feb, 2018

  • 双层优化中寻找静止点的近最优全一阶算法

    本文讨论了双层优化问题，提出了第一和第二阶段方法，探究了优化的复杂度和速度，并提出了适用于分布式双层问题的简单算法。

    Jun, 2023

  • 经由高斯平滑的全零阶双层规划

    本文研究使用零阶随机逼近算法解决双层问题，无论是上 / 下目标值还是它们的无偏梯度估计都不可用。通过利用斯坦恩恒等式，首先使用高斯平滑估计具有两个独立块变量的函数的一阶和二阶偏导数。然后，在随机逼近算法框架中使用这些估计来解决双层优化问题，并建立其非渐近收敛分析。据我们所知，这是第一次为完全随机零阶双层优化算法建立样本复杂度界限。

    Mar, 2024

  • 双层优化的下界和加速算法

    该论文从两个方面揭示双层优化的收敛率：提出首个双层加速优化器 AccBiO 并给出无梯度边界假设的复杂度上限，同时得出更紧的下限。此外，论文还证明在某些情况下，双层优化比极大极小问题更具有挑战性。关键词包括双层优化、收敛率、下限复杂度、AccBiO 和二次型条件数。

    Feb, 2021

  • 关于双层优化问题的稳定性和泛化性

    本文针对双层 (随机) 优化问题，探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系，并在一般性情形下给出了稳定性界限的分析，通过实验证明了迭代次数对泛化误差的影响。

    Oct, 2022

  • 非凸双层优化与一阶随机逼近的惩罚方法

    本文主要研究双层优化的一阶算法，目标函数在两个层次上都是光滑但可能非凸的，变量限制在闭凸集合中。首先通过罚函数方法，研究了双层优化的景观，并建立了罚函数与超目标之间的强连接。接着，提出了一阶算法来优化罚函数，以找到一个 ε- 稳定解。在满足小误差近似条件的情况下，算法以 O (ε^{-3}) 和 O (ε^{-7}) 程度的复杂度达到 ε- 稳定点。在随机预言机的额外假设下，算法的实现可以完全使用单循环方式，并分别达到 O (ε^{-3}) 和 O (ε^{-5}) 的优化复杂度。

    Sep, 2023

  • 线性约束双层优化的一阶方法

    具有有限时间超梯度稳定性保证的一阶线性约束优化方法在双层优化中遇到了带有高维度的 Hessian 计算，尽管最近的研究提供了非约束双层问题的一阶方法，但约束设置仍然相对较少探讨。我们提出了一种具有有限时间超梯度稳定性保证的一阶线性约束优化方法，在线性等式约束下，我们可以在 O (ϵ^{-2}) 次梯度预言调用中获得 ϵ- 稳定性，这几近是最优的。在线性不等式约束下，我们可以在 O (dδ^{-1}ϵ^{-3}) 次梯度预言调用中获得 (δ,ϵ)-Goldstein 稳定性，其中 d 是上层维度。最后，我们在额外假设有对最优对偶变量的 oracle 访问的情况下，在线性不等式设置下获得无维度的 O (δ^{-1}ϵ^{-4}) 的 oracle 复杂度。在此过程中，我们发展了新的非平滑非凸优化方法来处理不完全的预言。我们通过初步的数值实验验证了这些保证。

    Jun, 2024