Feb, 2024

随机双层优化中一阶方法的复杂度研究

PDF
TL;DR通过使用 y^*-aware oracle，我们提出了一种简单的一阶方法，它可以使用 O (ε^{-6})，O (ε^{-4}) 的一阶 y^*-aware oracles 来收敛到一个 ε 稳定点。
bilevel optimizationstationary pointsgenie algorithmoraclelower-level solution
发现论文，激发创造
  • 双层优化中寻找静止点的近最优全一阶算法

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

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

    Jun, 2024

  • 一种用于随机双层优化的全一阶方法

    本研究提出一种全一阶随机逼近方法用于解决双层无约束随机优化问题，该方法具有收敛性及优异的实际性能，并且可以使用动量辅助的梯度估计器进一步提高收敛速度。

    Jan, 2023

  • 随机凸优化中梯度变小的复杂性

    本文探讨了在随机凸优化问题中寻找近似驻点的 oracle 复杂度问题和其和全局 oracle 模型的关系，并提出了一种扩展的递归正则化算法以实现接近最优率，并揭示了 stochastic optimization 和 learning 的复杂度之间的一些惊人区别。

    Feb, 2019

  • 非凸随机优化下的下限界

    采用随机一阶方法找到梯度范数不超过 ε 的 ε- 稳定点的复杂度下界，使用具有有界方差的无偏随机梯度预言机访问光滑但可能非凸函数的一种模型，证明任何算法在最坏情况下需要至少 ε^-4 个查询才能找到 ε- 稳定点。对于噪声梯度估计满足均方光滑性质的更严格模型，我们证明了 ε^ -3 个查询的下界，建立了最近提出的方差缩减技术的最优性。

    Dec, 2019

  • 寻找静态点的下界 I

    该研究论文证明了在高维、潜在非凸函数上找到 ε- 稳态点的复杂性下界，并探讨了基于 Oracle 算法的复杂度测量方法，显示出梯度下降、三次正则化牛顿法和广义 p 次正则化在自然函数类中是最优的。

    Oct, 2017

  • 在无 Hessian/Jacobian 的随机双层优化中实现 ${O}(ε^{-1.5})$ 复杂度

    本文提出了一种新的 Hessian/Jacobian-free 双层优化器 FdeHBO，通过每次迭代使用 O (1) 个样本和仅一阶梯度信息，在非凸 - 强凸随机双层优化中实现了 O (ε^(-1.5)) 样本复杂度，达到 ε- 精确的稳定点。

    Dec, 2023

  • 非凸强凹 Min-Max 优化的复杂度下界

    我们通过使用第一阶 oracle 及条件数，提供了寻找 min-max 优化问题中目标函数在最小化变量上是非凸及在最大化变量上是强凸时的稳定点的复杂度的下界，这既适用于确定性 oracle 也适用于随机 oracle，并提供了各自的下界，并与其他文献的上界进行了比较。

    Apr, 2021