Jan, 2024

受约束的双层优化：近端拉格朗日值函数方法与无 Hessian 算法

PDF
TL;DR针对一类具有上下级变量耦合的约束双层优化问题，本研究提出了一种新的方法和算法。通过设计平滑的近端 Lagrangian 值函数来处理约束的下层问题，并将原始问题转化为具有平滑约束的等价优化问题，从而实现了一种适用于机器学习应用的基于近端 Lagrangian 值函数的非 Hessian 梯度算法。此外，还针对 LV-HBA 进行了收敛性分析，不需要对下层问题进行传统的强凸性假设，并且能够处理非单例情况。实证结果验证了该算法在实际性能上的优越性。
constrained bi-level optimizationmachine learningproximal lagrangian value functionsmooth constraintshessian-free gradient-based algorithm
发现论文，激发创造
  • 基于原始 - 对偶辅助罚函数的耦合约束双层优化方法

    我们的论文研究了具有耦合约束的双层优化问题，并开发了一种名为 BLOCC 的（完全）一阶算法，实现对这一具有挑战性但较少被探索的场景的解决。我们为所提算法建立了严格的收敛理论，并通过使用塞维利亚城市的真实数据，对 SVM 中的超参数选择和交通网络的基础设施规划这两个知名的实际应用进行了有效性验证。

    Jun, 2024

  • 多目标双层优化的一阶多梯度算法

    本研究针对多目标双层优化问题，提出了一种高效的一阶多梯度方法 FORUM，将 MOBLO 问题重新构造为约束的多目标优化问题，并通过一种新颖的多梯度聚合方法解决了具有挑战性的约束的多目标优化问题。理论上，我们提供了复杂度分析来展示所提出方法的效率以及非渐近收敛结果。实证上，广泛的实验表明了 FORUM 方法在不同的学习问题中的有效性和高效性，尤其在三个多任务学习基准数据集上取得了最先进的性能。

    Jan, 2024

  • 松弛平滑条件下随机双层优化的最优算法

    本文提出了一种新的完全单循环和免除海森矩阵的算法框架，用于随机双层优化，并在标准光滑性假设下提出了更紧密的分析，进而展示了算法的普遍性。

    Jun, 2023

  • LancBiO：基于 Krylov 子空间的动态 Lanczos 辅助双层优化

    通过 Lanczos 方法构建低维近似 Krylov 子空间，解决偏导数求逆问题，提高双层优化问题的效率，并在合成问题和深度学习任务中展示了收敛速度和效率。

    Apr, 2024

  • 具有非光滑低层问题的基于梯度的双层优化技术

    本研究提出了一种技术，用于近似具有非唯一解的非光滑下层问题的双层优化问题。通过迭代算法代替下层最小化问题的极小化器的表达式，使用适当的非线性近端距离函数，可以使迭代算法的更新映射可微。

    Feb, 2016

  • 通过 Bregman 距离增强双层优化

    本文提出了一种使用 Bregman 距离、具有低计算复杂度的增强型双层优化方法 BiO-BreD 和 SBiO-BreD，以解决双层优化问题，该问题的外部子问题非凸且可能非光滑，内部子问题强凸。通过数据超清理任务和超表征学习任务，证明了所提出的算法优于相关的双层优化方法。

    Jul, 2021

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

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

    Sep, 2023

  • 非凸双层优化的 Moreau 包络：一种单循环且无 Hessian 的解决策略

    该研究聚焦于解决大规模非凸双层优化问题中的两个主要挑战，即确保计算效率和提供理论保证，并通过引入一种创新的基于梯度的单循环算法、利用 Moreau 包络重构以及针对一般非凸双层优化问题提供的非渐进收敛分析，同时解决计算和理论挑战。该算法仅依赖一阶梯度信息，增强了其实用性和效率，特别适用于大规模双层优化学习任务，并通过在各种合成问题、两个典型超参数学习任务和一个真实的神经架构搜索应用上的实验证实了其卓越性能。

    May, 2024

  • 基于梯度的非凸跟随者双层优化及其拓展

    本文提出了一种名为 IAPTT-GM 的算法框架，旨在解决具有非凸跟随结构的 Bi-Level Optimization 模型在解决高复杂度实际问题时的有效解决方案和可靠的近似版本建构问题，并通过理论研究证明了该算法的收敛性和运用 LLC 时 Nesterov 加速动力学的质量。

    Oct, 2021

  • 一种基于价值函数的内点法用于非凸双层优化

    本文提出了一种新的基于值函数内点法的双层优化模型求解方法 BVFIM，通过对正则化值函数进行惩罚，进而获得一个连续可微的无约束逼近问题序列，解决了复杂的学习问题，数值实验验证了该方法的高效性和信噪比。

    Jun, 2021