技术摘要：用于在线非凸双层优化的完全一阶算法

问题表述

本工作针对**在线非凸双层优化（OBO）**问题，该场景要求智能体生成决策序列 $\{x_t\}_{t=1}^T$，以在流式环境中跟踪随时间变化的最优解。问题表述如下：
$$\min_{x \in \mathcal{X}} F_t(x) := f_t(x, y^*_t(x)) \quad \text{s.t.} \quad y^*_t(x) = \arg\min_{y \in \mathbb{R}^{d_2}} g_t(x, y)$$
其中，上层目标 $f_t$ 是光滑但可能非凸的，而下层目标 $g_t$ 是光滑且 $\mu_g$-强凸的。挑战在于问题的动态特性：$f_t$ 和 $g_t$ 均随时间变化，且内部解 $y^*_t(x)$ 会发生漂移。

现有的 OBO 方法通常依赖超梯度下降，这需要隐式微分来计算二阶信息（Hessian-向量积，HVPs）。这导致了高昂的计算成本，并在 HVPs 不可用或昂贵时限制了其适用性。本文专注于开发仅依赖完全一阶梯度（一阶预言机）的双层算法。

方法论

核心方法论贡献是将原始双层问题重构为带不等式约束的单层在线优化问题。通过引入拉格朗日函数 $L_t(x, y, \lambda_t) = f_t(x, y) + \lambda_t (g_t(x, y) - g_t(x, y^*_t(x)))$，作者将问题转化为拉格朗日函数的极小 - 极大优化问题。

关键在于，这种重构消除了标准超梯度计算中所需的隐式项 $\nabla y^*_t(x)$。只要拉格朗日乘子 $\lambda_t$ 足够大，拉格朗日最优值函数的梯度 $\nabla L^*_t(x)$ 就可以仅利用 $f_t$ 和 $g_t$ 的一阶梯度进行近似。

本文提出了三种具体算法：

1. F2OBO（完全一阶在线双层优化器）：

   • 结构： 采用嵌套内循环方法，通过梯度下降同时求解内部解 $y^*_t(x_t)$ 和拉格朗日解 $y^*_{\lambda_t, t}(x_t)$。
   • 机制： 利用从拉格朗日函数导出的近似超梯度更新上层变量 $x_t$。乘子 $\lambda_t$ 遵循非递减调度 $\Lambda(t, \lambda_t) = (1 + 1/t)^\tau \lambda_1$。
   • 复杂度： 总迭代次数为 $O(T \log T)$。

2. 单循环 F2OBO：

   • 结构： 将内循环限制为单次迭代（$K_t = 1$），以减少计算开销。
   • 机制： 为了控制不精确内部解带来的误差，该变体在遗憾分析中引入了额外的梯度变化项（$E_{f,y,T}$ 和 $E_{g,y,T}$），用于衡量内部目标一阶梯度随时间的变化。

3. AF2OBO（自适应迭代完全一阶在线双层优化器）：

   • 结构： F2OBO 的改进变体，采用自适应内迭代方案。
   • 机制： 内循环不再运行固定次数的迭代，而是持续运行直到梯度范数低于特定容差阈值（$\delta_y, \delta_z$）。这种动态调整使算法能够在遗憾界中消除对内部解漂移变化（$H_{2,T}$）的依赖，代价是可能需要更多的迭代次数。

4. SF2OBO（随机完全一阶在线双层优化器）：

   • 结构： 将 F2OBO 扩展到随机场景，其中梯度含有噪声。
   • 机制： 对内层和外层循环均使用批处理的随机梯度。批处理大小随时间增加以控制方差和偏差，从而避免了先前随机方法中使用的窗口平均遗憾分析。

主要贡献与理论结果

本文建立了双层局部遗憾（$BLReg(T) = \sum_{t=1}^T \|G_\mathcal{X}(x_t, \nabla F_t(x_t), \gamma)\|^2$）的理论保证，定义为梯度映射平方和。

• 确定性遗憾界：

  • F2OBO： 在 $O(T \log T)$ 次迭代下实现了 $O(1 + V_T + H_{2,T})$ 的遗憾界，其中 $V_T$ 是函数值的变化，$H_{2,T}$ 是内部最优解的漂移。这在不依赖 HVPs 的情况下达到了与二阶方法相当的性能。
  • 单循环 F2OBO： 实现了 $O(T^{1/3}(1 + V_T) + T^{2/3}P_T)$ 的次线性遗憾，其中 $P_T$ 包含梯度变化项。这证明了在单循环结构下的可行性，尽管其界较弱且依赖于梯度的稳定性。
  • AF2OBO： 实现了 $O(\log T + V_T)$ 的遗憾，有效消除对 $H_{2,T}$ 的依赖。这对于内部解发生剧烈漂移的场景（例如 $H_{2,T} = O(T)$）具有重要意义。

• 随机遗憾界：

  • SF2OBO： 建立了 $O(T^{2/3}(1 + \sigma^2) + V_T + H_{2,T})$ 的遗憾界。与依赖窗口平均遗憾或有界二阶梯度方差的先前随机方法（如 SOBBO, SOGD）不同，SF2OBO 在更温和的环境变化假设和标准一阶方差下实现了这一结果。

实验验证

作者在两项任务上验证了其算法：

1. 不平衡数据的参数损失调整： 在类别分布漂移下优化 MNIST 上 CNN 的类别权重。AF2OBO 取得了最佳平衡测试准确率。
2. 在线超参数优化： 在标签噪声和分布漂移下优化 20 Newsgroups 数据集上的 L2 正则化系数。与 SOBBO 和 SOGD 相比，SF2OBO 展现了更优越的测试准确率和具有竞争力的效率。

意义与主张

本文声称其主要贡献是开发了完全一阶算法，这些算法在无需 HVPs 的情况下实现了与现有二阶方法相当的遗憾界，同时计算效率更高，且适用于无法获取二阶信息的场景。

• 消除 HVPs： 通过拉格朗日松弛重构问题，作者绕过了对隐式微分和 Hessian-向量积的需求。
• 对漂移的鲁棒性： 自适应变体（AF2OBO）提供了针对内部层解严重漂移的鲁棒性，克服了静态迭代方法的局限性。
• 实用性： 单循环和随机变体表明，完全一阶方法可以部署在实际、动态和嘈杂的环境中，而不会牺牲理论上的次线性遗憾保证。

作者承认，其理论分析目前仅限于具有强凸内部目标的问题，并建议将结果扩展到满足 Polyak-Łojasiewicz (PL) 条件的非凸内部目标，作为未来工作的方向。