📊 statistics

Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization

本文提出了一种新颖的搜索方向，使得一阶和零随机随机双层优化算法均能在无需窗口平滑的情况下实现次线性随机遗憾，同时通过降低对Oracle的依赖和统一变量更新来提升效率。

原作者： Parvin Nazari, Bojian Hou, Davoud Ataee Tarzanagh, Li Shen, George Michailidis

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Parvin Nazari, Bojian Hou, Davoud Ataee Tarzanagh, Li Shen, George Michailidis

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在与一位对手进行一场复杂且高风险的国际象棋对弈，而这位对手却在同时玩着跳棋，但两种游戏的规则每一秒都在发生变化。

这就是**在线双层优化（OBO）**的世界。在这个场景中，你是“领导者”（做出重大战略决策），而你的对手是“追随者”（对你的决策做出即时反应，以优化他们自己的小局）。问题在于，棋盘不断移动，棋子的价值瞬息万变，而且你事先并不知道规则。你必须走一步棋，观察对手如何反应，然后立即调整下一步，而与此同时，游戏本身也在不断演变。

本文将通过简单的类比，解释如何应对这种混乱的局面。

问题：“窗口”陷阱

以往的方法试图通过观察最近几步棋（一个“窗口”）并对其进行平滑处理来预测趋势。

类比：想象你试图在暴风雨中驾驶汽车，却只依赖一张模糊的、基于过去 10 英里路况平均化后的地图。如果道路突然急转弯或桥梁坍塌，那张平滑后的地图就毫无用处。你需要对眼前的确切路况做出反应，而不是对过去位置的平滑平均值做出反应。
本文的解决方案：作者提出“停止平滑”。他们引入了一种计算下一步的新方法，能够即时应对当前的混乱，而无需等待一个“过去数据窗口”来进行平均化。这使得他们能够更好地处理快速变化。

两种新策略

本文提出了两种具体的“搜索方向”（即决定下一步的方法），具体取决于你拥有哪些可用信息。

1. “知情导航员”（一阶方法）

这适用于你能够获取某些“梯度”信息的情况（就像有一个指南针告诉你哪边是上坡或下坡）。

创新点：以往每次移动时都需要解决一个复杂的嵌套谜题（这既缓慢又计算成本高昂），而作者设计了一种“同步在线梯度下降”（SOGD）方法。
类比：想象一场接力赛，领导者、追随者和一位“系统助手”（负责解决数学问题）同时奔跑。在旧方法中，领导者要等追随者跑完，再等助手完成，然后自己再跑。而新方法让所有人同步奔跑。他们同时更新各自的位置，使过程更快、更高效。
结果：作者从数学上证明，即使不对数据进行平滑处理，这支同步协作的团队也能保持较低的“遗憾值”（即其表现与完美表现之间的差距），即便游戏在快速变化。

2. “盲探者”（零阶方法）

这适用于“黑盒”场景，即你没有指南针、没有梯度信息，也不知道哪边是上。你只知道在做出移动后的得分。

创新点：这是最困难的场景。作者创造了一种方法，仅通过“试探”环境并观察得分变化，就能估算出“指南针”（梯度、海森矩阵和雅可比矩阵）。
类比：想象你在一个黑暗的房间里寻找出口。你看不到路，所以只能向不同方向轻轻敲击墙壁。如果向左敲击让房间感觉“更好”（得分更高），你就知道应该向左走。本文的方法就像一种超高效的敲击策略，让你无需看见墙壁就能绘制出房间地图并找到出口。
结果：他们表明，即使只有这种有限的“试探 - 观察”反馈，你仍然能够快速学习和适应以赢得游戏，而无需对数据进行平滑处理。

为何这很重要（根据本文观点）

作者在两个具体的现实世界“游戏”中测试了这些想法：

黑盒对抗攻击：试图通过向图像添加微小且不可见的变化来欺骗神经网络（如人脸识别系统）。本文表明，他们的方法能够比以往方法更快、更有效地发现系统的这些“弱点”，即使系统的内部规则是隐藏的。
不平衡数据的参数损失调节：想象一个医疗人工智能，它在诊断常见病方面表现出色，但在罕见病方面却表现糟糕。本文的方法有助于实时调节人工智能的“损失函数”（其内部评分系统），以平衡所有疾病类型的准确率，即使数据分布发生偏移。

核心结论

本文声称构建了一个用于在混乱、变化的环境中进行决策的新引擎。

不再“平滑”：它针对当下时刻做出反应，而非过去的平均值。
不再等待：它同时更新所有变量（领导者、追随者和助手）。
在黑暗中运作：即使你看不到梯度，只能看到最终得分，它也能发挥作用。

通过这样做，作者保证他们的算法即使在环境快速变化时也能表现良好（次线性遗憾），而无需承担回顾漫长移动历史所带来的沉重计算成本。

技术摘要：在线零阶与一阶双层优化的随机遗憾保证

问题陈述

本文探讨了在线双层优化（OBO），这是一个外层和内层目标均随时间演变的框架，要求在不知晓未来结果的情况下动态更新决策变量。在标准的离线设置中，双层优化旨在最小化外层目标 $f(x, y^*(x))$ ，其中 $y^*(x)$ 是内层最小化问题 $g(x, y)$ 的解。而在在线设置中，函数 $f_t$ 和 $g_t$ 在每个回合 $t$ 都会发生变化，智能体必须按顺序选择 $x_t$ 和 $y_t$ 。

现有 OBO 文献中的一个关键挑战是对确定性窗口平滑遗憾最小化的依赖。当前方法（例如 OAGD、SOBOW）通过对窗口 $w$ 内的目标进行平均来实现次线性遗憾界。然而，作者认为，当函数快速变化时，窗口平滑可能会歪曲系统性能，且无法捕捉真实的遗憾行为。此外，现有方法通常需要访问精确的梯度、海森矩阵和雅可比矩阵，或者依赖昂贵的迭代求解器（如共轭梯度法）来近似超梯度，这限制了其在大规模或黑盒场景中的可扩展性。

本文聚焦于随机 OBO，其中仅可获得函数、梯度和海森矩阵的含噪评估值。目标是在无需窗口平滑且仅有限制性预言机访问（具体而言，在零阶设置中仅访问函数值预言机）的情况下，最小化随机双层遗憾。

方法论

作者提出了一个以新搜索方向为核心的新颖框架，该方向能够在无需窗口平滑的情况下实现次线性遗憾。该框架通过两种主要算法实现：

1. 同步在线梯度下降（SOGD）

针对可访问一阶及内层二阶预言机的设置，本文引入了SOGD（算法 1）。

新颖的搜索方向： 与以往使用窗口平滑梯度或交替循环的方法不同，SOGD 采用了一种递归动量型搜索方向（公式 7），该方向结合了当前梯度与先前梯度的差值。该方向用于同时更新跟随者变量 $y$ 、辅助变量 $v$ （求解线性系统）以及领导者变量 $x$ 。
单循环结构： 该算法在每个回合中通过单个循环更新所有变量（ $x_t, y_t, v_t$ ），避免了 SOBOW 等方法所需的多重内层循环迭代带来的计算开销。
线性系统近似： SOGD 并非精确求解线性系统 $\nabla^2_y g_t v + \nabla_y f_t = 0$ ，而是利用单步梯度更新辅助变量 $v_t$ ，从而有效地解耦了超梯度的非线性结构。

2. 零阶 SOGD（ZO-SOGD）

针对梯度不可用的黑盒设置，本文提出了ZO-SOGD（算法 2）。

函数值预言机： 该方法仅依赖含噪的函数值评估。它利用高斯平滑和有限差分近似，构建梯度、海森矩阵和雅可比矩阵的无偏估计量。
估计策略：
- 梯度通过两点函数评估进行估计（公式 24-25）。
- 海森矩阵 - 向量积和雅可比矩阵 - 向量积通过估计梯度的有限差分进行近似（公式 26）。
收敛控制： 该算法对辅助变量 $v$ 采用投影步骤以限制其范数，从而控制更新过程中的方差。

主要贡献

无需窗口平滑的随机遗憾最小化：
本文引入了一种新颖的搜索方向，并证明了所提出的一阶（SOGD）和零阶（ZO-SOGD）算法在窗口大小 $w=1$ 的情况下均能实现次线性随机双层遗憾。这消除了对窗口平滑的需求，而窗口平滑在快速变化的环境中往往具有局限性。遗憾界取决于底层序列的路径长度和函数变化。
预言机依赖的高效性：
该框架显著降低了对预言机的依赖。
- 一阶： 它避免了对内层线性系统进行精确求解的需求，转而使用单步更新来处理辅助变量。
- 零阶： 这是首个仅使用函数值预言机（针对领导者和跟随者目标）为 OBO 提供遗憾保证的方法。它成功地从函数值中估计出海森矩阵、雅可比矩阵和梯度，解决了双层问题中嵌套结构的挑战。
单次子问题求解器迭代：
所提出的算法每回合仅需一次子问题求解器迭代。这与使用共轭梯度法且迭代次数不断增加的 SOBOW 等方法形成对比，从而提高了计算效率和可扩展性。

结果与遗憾界

本文在标准假设下（内层目标的强凸性、平滑性以及随机估计量的有界方差）为两种算法建立了理论遗憾界。

SOGD（一阶）：
定理 2.6 保证了双层局部遗憾界为：
$BL\text{-}Reg_T \le O\left( T^{1/3}(\sigma^2 + \Delta_T) + T^{2/3}\Psi_T \right)$
其中 $\sigma^2$ 代表随机估计量的方差， $\Delta_T$ 和 $\Psi_T$ 捕捉了环境的变化（函数值、梯度、海森矩阵和雅可比矩阵）。在环境变化呈次线性增长的适当条件下，平均动态遗憾是次线性的（ $o(T)$ ）。值得注意的是，这改进了以往随机 OBO 方法的 $O(T^{-1/2}\sigma^2)$ 速率。
ZO-SOGD（零阶）：
定理 3.2 提供了首个仅基于含噪函数评估的 OBO 遗憾保证。其界为：
$BL\text{-}Reg_T \le O\left( (d_1 + d_2)^{3/4} T^{1/3}(\hat{\sigma}^2 + \hat{\Delta}_T) + (d_1 + d_2)^{3/2} T^{2/3}\hat{\Psi}_T \right)$
对维度 $(d_1 + d_2)$ 的依赖性与离线极小极大问题的最优结果一致。该界还依赖于批量大小和平滑参数。

实验验证

作者在两个应用上验证了其方法：

在线黑盒对抗攻击（BBAA）： 使用 MNIST 数据，将 ZO-SOGD 和 ZO-SOGD（Adam）与单层零阶基线（ZO-O-GD、ZO-O-Adam 等）进行了比较。结果表明，ZO-SOGD 实现了更优越的攻击准确率，并在外层优化增加的复杂性下保持了有效的扰动。
不平衡数据的参数化损失调整： 算法在不平衡数据集的对数调整（logit adjustments）任务上进行了测试。SOGD 展示了比 SOBOW 更快的运行时间（得益于单循环结构），并在数据分布发生偏移时实现了具有竞争力的类别平衡准确率。

意义与主张

本文声称克服了现有 OBO 算法依赖大量预言机信息和高计算成本的局限性。通过引入新颖的搜索方向并利用有限反馈（包括零阶反馈），所提出的方法实现了无需窗口平滑的次线性双层遗憾。

作者将这项工作定位为迈向动态、非凸和黑盒设置下高效在线双层优化的重要一步。他们明确指出了一个局限性：结果聚焦于非凸遗憾界，并未将保证扩展到凸设置。这项工作被呈现为一个基础框架，用于处理传统平滑技术无法准确反映性能的动态双层问题。