BOME! 一种简单的一阶方法实现双层优化

Sep, 2022

BOME! 一种简单的一阶方法实现双层优化

BOME! Bilevel Optimization Made Easy: A Simple First-Order Approach

Mao Ye, Bo Liu, Stephen Wright, Peter Stone, Qiang Liu

TL;DR本文提出了一种基于一阶梯度信息的简单双层优化算法，适用于深度学习中大规模的非凸函数，无需隐式微分，并有指导其在非凸优化问题上收敛于驻点的收敛性分析证明，实验结果表明其优越的性能表现。

Abstract

bilevel optimization (BO) is useful for solving a variety of important machine learning problems including but not limited to hyperparameter optimization, meta-learning, continual learning, and reinforcement learning. Conventional BO methods need to differentiate through the low-level

bilevel optimization first-order bo algorithm non-convex functions deep learning convergence

发现论文，激发创造

通过 Bregman 距离增强双层优化

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

Jul, 2021

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

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

Sep, 2023

双动量方法用于下层约束双层优化

通过利用非光滑隐函数定理，提出一种新的双层约束双目标函数优化的超梯度方法，并基于双动量方法和自适应步长方法提出了一种单循环单时间尺度算法，经证明它可以返回一个（δ，ε）- 稳定点，迭代次数约为 O (d2^2ε^-4)，在两个应用上的实验证明了该方法的有效性。

Jun, 2024

无界平滑的双层优化：一种新算法和收敛性分析

设计了一种名为 BO-REP 的新的双层优化算法，用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下，该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点，结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。

Jan, 2024

机器学习中的双层优化：算法设计与收敛分析

本篇论文提供了多方面的双层优化算法收敛速度分析，包括问题和算法两个方面，提出了更加高效可扩展的算法设计，并最终提出了新的随机双层优化算法降低了实践中的复杂度并提高其效率。

Jul, 2021

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

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

Jun, 2023

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

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

Oct, 2022

隐式双层优化：通过双层优化规划进行求导

本篇研究提出 Differentiating through Bilevel Optimization Programming (BiGrad) 模型，旨在将 Bi-level Programming 加入到神经网络中，通过类别估计算法以降低计算复杂度并支持对于连续变量的处理。实验结果表明，该模型成功地将传统单层方法扩展到了 Bi-level Programming

Feb, 2023

双层优化：收敛分析与增强设计

本文研究非凸强凸双层优化问题，提供了两种基于近似隐式导数和迭代导数的算法以及一种名为 stocBiO 的新型算法，并对它们进行了收敛性分析和比较，实验表明这些优化算法在元学习、超参数优化等方面表现出良好效果。

Oct, 2020

ScaleBiO: 面向 LLM 数据重新加权的可扩展的双层优化

本研究提出了第一种可扩展实例，称为 ScaleBiO，通过与一种称为 LISA 的新型算法相结合，使软件在八个 A40 GPU 上扩展到 34 亿参数的大型语言模型（LLM），标志着在实际应用场景中首次成功应用双层优化于大型 LLM。从实证上来说，对于不同规模的模型，包括 GPT-2，LLaMA-3-8B，GPT-NeoX-20B 和 Yi-34B，通过数据重加权广泛实验验证了 ScaleBiO 的有效性，其中双层优化成功地过滤了无关的数据样本，并选择了信息量较大的样本。从理论上来说，ScaleBiO 确保了学习到的数据权重的最优性，并具有匹配传统的一阶平滑凸优化双层优化范式的收敛保证。

Jun, 2024