双层优化的可证明更快算法
设计了一种名为 BO-REP 的新的双层优化算法,用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下,该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点,结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。
Jan, 2024
该论文从两个方面揭示双层优化的收敛率:提出首个双层加速优化器 AccBiO 并给出无梯度边界假设的复杂度上限,同时得出更紧的下限。此外,论文还证明在某些情况下,双层优化比极大极小问题更具有挑战性。关键词包括双层优化、收敛率、下限复杂度、AccBiO 和二次型条件数。
Feb, 2021
本篇论文提供了多方面的双层优化算法收敛速度分析,包括问题和算法两个方面,提出了更加高效可扩展的算法设计,并最终提出了新的随机双层优化算法降低了实践中的复杂度并提高其效率。
Jul, 2021
在本论文中,我们提出了一种新的快速自适应双层框架 (BiAdam) 来解决随机双层优化问题,其中外层问题可能是非凸的,内层问题是强凸的。使用统一自适应矩阵,包括多种自适应学习率,并可灵活使用动量和方差减少技术。同时,我们提出了 BiAdam 算法和 VR-BiAdam 算法,这两种算法的采样复杂度分别为 O(1 /epsilon ^ 4)和 O(1 /epsilon ^ 3)。实验证明了我们算法的高效性。
Jun, 2021
通过利用非光滑隐函数定理,提出一种新的双层约束双目标函数优化的超梯度方法,并基于双动量方法和自适应步长方法提出了一种单循环单时间尺度算法,经证明它可以返回一个(δ,ε)- 稳定点,迭代次数约为 O (d2^2ε^-4),在两个应用上的实验证明了该方法的有效性。
Jun, 2024
本文针对双层 (随机) 优化问题,探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系,并在一般性情形下给出了稳定性界限的分析,通过实验证明了迭代次数对泛化误差的影响。
Oct, 2022
提出了一种推广后的交替优化方法(GALET)用于双层优化问题,可以适用于具有非凸下层目标函数的问题,并具有与一阶梯度下降相同的收敛速度。
Jun, 2023
本文研究分布式环境下的联邦双层优化问题,并针对性地提出了 FedBiO 和 FedBiOAcc 两种优化算法,用于解决团体公平的联邦学习任务,数值实验表明,与其他基线算法相比,该算法在性能上表现更优。
May, 2022
在这篇论文中,我们考虑了分散网络中的双层优化问题,提出了一种针对具有强凸下层问题的分散式双层优化的新型单循环算法。我们的算法完全是单循环算法,在逼近超梯度时不需要进行复杂的矩阵向量乘法。此外,与现有的分散式双层优化和联邦双层优化方法不同的是,我们的算法不需要任何梯度异质性假设。我们的分析结果显示,该算法达到了迄今为止双层优化算法的最佳收敛速度。
Nov, 2023
本文提出了一种新算法:单时间尺度双动量随机逼近算法(SUSTAIN),用于解决随机无约束双层优化问题,重点关注下层子问题为强凸的双层问题和上层目标函数光滑情况下的解决方案,通过设计一种随机动量辅助梯度估计器来控制解决子问题的不准确性带来的随机梯度更新的误差,从而实现解决双层最优化问题的目的,其样本复杂度与传统单层随机梯度算法的最优复杂度相当。
Feb, 2021