双层优化的下界和加速算法
本研究关注简单的双层优化问题,提出一种新的双层优化方法,利用切割平面方法局部近似解决方案集合,应用加速梯度更新来减小上层目标函数,以实现子优性和不可行性错误的非渐近收敛保证。
Feb, 2024
本论文提出了两种新的双层优化算法,第一种采用基于动量的递归迭代算法,第二种采用嵌套循环中的递归梯度估计以减少方差。我们表明,两种算法都实现了 Ω(ε^ -1.5)计算量的复杂度,超越了所有现有算法一个数量级。本文的实验证明了我们算法在超参数优化应用中的优越性能。
Jun, 2021
设计了一种名为 BO-REP 的新的双层优化算法,用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下,该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点,结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。
Jan, 2024
本文研究一类内部目标函数为强凸函数的双层规划问题,给出了一种求解该问题的逼近算法,并在外部目标函数为不同凸性的情况下提供了其有限时间收敛分析。同时,提出了一种加速变体以提高收敛速度,并推广了结果到只有有限的信息可用的随机情况下。本文是第一次为双层规划提供了已确定的迭代复杂度(样本复杂度)的(随机)逼近算法。
Feb, 2018
本文研究非凸强凸双层优化问题,提供了两种基于近似隐式导数和迭代导数的算法以及一种名为 stocBiO 的新型算法,并对它们进行了收敛性分析和比较,实验表明这些优化算法在元学习、超参数优化等方面表现出良好效果。
Oct, 2020
本篇论文提供了多方面的双层优化算法收敛速度分析,包括问题和算法两个方面,提出了更加高效可扩展的算法设计,并最终提出了新的随机双层优化算法降低了实践中的复杂度并提高其效率。
Jul, 2021
本文提出了一种使用 Bregman 距离、具有低计算复杂度的增强型双层优化方法 BiO-BreD 和 SBiO-BreD,以解决双层优化问题,该问题的外部子问题非凸且可能非光滑,内部子问题强凸。通过数据超清理任务和超表征学习任务,证明了所提出的算法优于相关的双层优化方法。
Jul, 2021
本文针对双层 (随机) 优化问题,探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系,并在一般性情形下给出了稳定性界限的分析,通过实验证明了迭代次数对泛化误差的影响。
Oct, 2022
研究了分散设置下非凸强凸双层优化问题,在确定性和随机双层优化问题上设计了分散算法。分析了算法的收敛速度,包括在代理间观察到数据异构性的情况。通过对合成和真实数据的数值实验表明,所提出的方法是有效的。
Jun, 2022
本文探讨了多块最小最大双层优化问题,提出了一种单循环随机算法,其样本复杂性为 O(1/ϵ^4),应用于多任务深度 AUC 最大化和多任务深度局部 AUC 最大化。
Jun, 2022