双层优化方法最新进展第9部分（机器学习2024）| 通过 Monodeep Mukherjee | 2024年4月

1. 具有时变目标函数的非凸双层优化 (arXiv)

作者 ： 林森, 达乌达母猪, Kaiyi Ji, Yingbin Liang, 内斯·史罗夫

摘要：双层优化已成为解决各种机器学习问题的强大工具。 然而，当前的非凸双层优化考虑了离线数据集和静态函数，这可能不适用于具有流数据和时变函数的新兴在线应用程序。 在这项工作中，我们研究了在线双层优化（OBO），其中函数可以随时间变化，并且代理通过在线流数据不断更新决策。 为了解决 OBO 中函数变化和真实超梯度不可用的问题，我们提出了一种带窗口平均的单循环在线双层优化器（SOBOW），它根据最近超梯度估计的窗口平均值更新外层决策存储在内存中。 与现有算法相比，SOBOW 计算效率高，并且不需要知道以前的函数。 为了解决 OBO 的单循环更新和函数变化所带来的独特技术困难，我们开发了一种新颖的分析技术，可以解开决策变量之间的复杂耦合，并仔细控制超梯度估计误差。 我们证明 SOBOW 在温和条件下可以实现亚线性双层局部遗憾。 跨多个领域的广泛实验证实了 SOBOW 的有效性。

2.非凸双层优化和一阶随机逼近的惩罚方法(arXiv)

作者 ： 权正烈, 权道贤, 史蒂芬赖特, 罗伯特·诺瓦克

摘要：在这项工作中，我们研究了求解双层优化（BO）的一阶算法，其中目标函数是平滑的，但在两个层面上都可能是非凸的，并且变量仅限于闭凸集。 第一步，我们通过惩罚方法的视角来研究 BO 的情况，其中上层和下层目标以加权和的形式组合，惩罚参数 σ>0。 特别是，我们通过明确描述两者的值和导数必须接近 O(σ) 的条件，在罚函数和超目标之间建立了牢固的联系。 我们分析的副产品是当较低级别的问题在最小条件下有多个解决方案时超目标梯度的显式公式，这可能是独立的兴趣。 接下来，将惩罚公式视为原始 BO 的 O(σ) 近似，我们提出一阶算法，通过使用 σ=O(ε) 优化惩罚公式来找到 ε-平稳解。 当扰动的低级问题一致满足小误差近端误差界（EB）条件时，我们提出了一种一阶算法，该算法收敛到罚函数的 ε-驻点，总共使用 O(ε−3 ) 和 O(ε−7) 分别在预言机是确定性的和预言机有噪声时访问一阶（随机）梯度预言机。 在随机预言的附加假设下，我们表明该算法可以以完全{it单循环}的方式实现，即每次迭代使用 O(1) 个样本，并实现改进的预言复杂度 O(ε −3) 和 O(ε−5) 分别。