Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization¶
会议: NeurIPS 2026
arXiv: 2602.06457
OpenReview: https://openreview.net/forum?id=xFpqYVlNo9
领域: 优化/理论
关键词: 在线双层优化, 局部遗憾界, 自适应内层迭代, 窗口平均超梯度, 隐式梯度近似
一句话总结¶
针对非凸-强凸在线双层优化（OBO），本文通过自适应追踪内层最优漂移与新颖的窗口平均超梯度分析，分别在标准局部遗憾与窗口平均局部遗憾下达成了匹配理论下界的最佳遗憾界与全单循环算法。
研究背景与动机¶
在线双层优化（Online Bilevel Optimization, OBO）在超参数调优、在线元学习、带噪数据超清洗以及动态类别不平衡损失调整等机器学习场景中展现出核心价值。其标准数学形式表现为外层目标关于决策变量非凸、内层目标强凸的双层极小化问题，外层变量的最优更新依赖于对隐式超梯度的精确估计。然而，当环境随着时间动态对抗演化时，内层最优点与外层目标函数均发生非平稳漂移，传统的双层优化方法面临严峻挑战。
现有研究在评估非凸 OBO 的收敛性时主要依赖两类局部遗憾：标准双层局部遗憾和时间窗口滑动平均局部遗憾。针对标准局部遗憾，既有工作（如基于动量搜索方向的 SOGD）通常需要极其严苛的变分正则性假设，且上界严重依赖内层解漂移量 \(H_{2,T}\)，其渐近界尚未达到理论最优；针对窗口平均局部遗憾，已有方法（如 OAGD、SOBOW、OBBO）仅对外层函数或超梯度进行滑动平均，忽略了内层函数本身的平滑演化，导致其遗憾界仍然受到内层最优解漂移累积项的额外拖累，缺乏对环境变化的内在鲁棒性。
这种理论局限性的核心矛盾在于：内层子问题在对抗环境下的漂移程度随时间高度不均匀，固定步数或固定精度的内层梯度更新策略无法自适应追踪剧烈突变，导致超梯度近似误差在时间轴上恶性累积。本文的核心 idea 是：将在线双层优化的内层迭代改造成由局部梯度范数阈值驱动的自适应追踪机制（AOBO），并针对滑动窗口构造兼具内外层联合平均的全新局部遗憾定义（WOBO），分别从标准遗憾和窗口平均遗憾两个维度彻底摆脱对内层漂移项的冗余依赖，达到理论最优的匹配下界。
方法详解¶
整体框架¶
本文针对非凸-强凸 OBO 问题分别提出了两种优化架构：面向标准局部遗憾的自适应内层优化器 AOBO（及其全单循环变体 FSOBO），以及面向滑动窗口平均局部遗憾的窗口平均优化器 WOBO（及其单循环变体 WOBO-SL）。整个算法流程由“接收在线函数反馈 \(\rightarrow\) 自适应追踪/滑动求解内层变量 \(\rightarrow\) 投影梯度下降求解超梯度伴随向量 \(\rightarrow\) 计算近似超梯度并执行外层投影梯度步”构成。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["在线环境输入<br/>时变目标函数 f_t 与 g_t"] --> B["自适应追踪内层最优解<br/>动态终止条件 ||∇_y g_t|| ≤ δ"]
B --> C["伴随变量近似求解<br/>欧氏球投影梯度下降法求解 Φ_t 极小点"]
C --> D["隐式超梯度构造与更新<br/>利用 AID 近似闭式解更新外层变量 x"]
D --> E["双层局部遗憾评估<br/>标准局部遗憾 / 窗口平均局部遗憾"]关键设计¶
1. 自适应追踪内层最优解：动态阈值解耦累积漂移误差
现有基于交替梯度的在线双层算法（如 OBBO、SOBOW）在每个时间步均执行固定次数（如 \(K\) 次）的内层梯度更新。然而，在非平稳环境中，当相邻两步的内层函数变化较大时，固定的迭代次数会产生巨大的近似残差。为解决此问题，AOBO 引入自适应迭代策略，在第 \(t\) 步以 \(\mathbf{y}_t\) 为起点，持续执行内层梯度下降： $\(\mathbf{y}_t^{k+1} \leftarrow \mathbf{y}_t^k - \alpha \nabla_{\mathbf{y}} g_t(\mathbf{x}_t, \mathbf{y}_t^k)\)$ 直到内层梯度范数满足动态终止条件 \(\|\nabla_{\mathbf{y}} g_t(\mathbf{x}_t, \mathbf{y}_{t+1})\| \leq \delta\)。由内层函数的 \(\mu_g\)-强凸性可知，此时近似误差被严格控制在 \(\|\mathbf{y}_{t+1} - \mathbf{y}_t^*(\mathbf{x}_t)\| \leq \delta / \mu_g\) 之内。当选取动态容忍度 \(\delta = 1/\sqrt{T}\) 时，算法将内层逼近误差引起的累积超梯度偏差从 \(O(H_{2,T})\) 降低至可忽略的常数阶 \(O(\delta^2 T) = O(1)\)，从而在标准局部遗憾上达成了最优的 \(O(1 + V_T)\) 上界，且内层总迭代开销仅为 \(\mathcal{I}_T \leq O(T \log T)\)。
2. 伴随变量近似求解：有界欧氏球上的投影梯度迭代
根据隐式函数定理（AID），外层目标的真实超梯度满足 \(\nabla f_t(\mathbf{x}, \mathbf{y}_t^*(\mathbf{x})) = \nabla_{\mathbf{x}} f_t(\mathbf{x}, \mathbf{y}_t^*(\mathbf{x})) - \nabla_{\mathbf{x}\mathbf{y}}^2 g_t(\mathbf{x}, \mathbf{y}_t^*(\mathbf{x})) \mathbf{v}_t^*(\mathbf{x})\)，其中线性伴随向量 \(\mathbf{v}_t^*(\mathbf{x}) = [\nabla_{\mathbf{y}\mathbf{y}}^2 g_t(\mathbf{x}, \mathbf{y}_t^*(\mathbf{x}))]^{-1} \nabla_{\mathbf{y}} f_t(\mathbf{x}, \mathbf{y}_t^*(\mathbf{x}))\) 等价于二次凸优化问题 \(\min_{\mathbf{v} \in \mathcal{V}} \Phi_t(\mathbf{x}, \mathbf{y}_t^*(\mathbf{x}), \mathbf{v})\) 的唯一解。由于真实伴随解的范数严格上界为 \(\|\mathbf{v}_t^*(\mathbf{x})\| \leq L_{f,0}/\mu_g\)，算法在凸紧集 \(\mathcal{V} = \{\mathbf{v} \in \mathbb{R}^{d_2} \mid \|\mathbf{v}\| \leq L_{f,0}/\mu_g\}\) 上执行受限步长 \(\beta\) 的投影梯度下降： $\(\mathbf{v}_t^{m+1} \leftarrow \mathcal{P}_{\mathcal{V}}\left(\mathbf{v}_t^m - \beta \nabla_{\mathbf{v}} \Phi_t(\mathbf{x}_t, \mathbf{y}_{t+1}, \mathbf{v}_t^m)\right)\)$ 在 AOBO 中仅需进行 \(M = \lceil -\ln T / \ln \rho \rceil\) 步收缩迭代；而在全单循环变体 FSOBO 中，每一轮外层更新仅配对单步内层更新与单步伴随向量更新（\(N=1, M=1\)），通过利用强凸二次函数的收缩性并引入高阶导数变分项 \(E_{2,T} = E_{\mathbf{y}\mathbf{y},T}^g + E_{\mathbf{y},T}^f\)，成功证明了单循环架构下仅需 \(O(T)\) 次梯度查询即可保证 \(O(1 + V_T + H_{2,T} + E_{2,T})\) 的局部遗憾。
3. 联合滑动平均机制：线性变化环境下的无变分鲁棒下界匹配
传统窗口平均局部遗憾忽略了内层时变函数的信息平滑。WOBO 创新性地同时对外层和内层函数引入指数加权滑动平均：\(\widehat{f}_{t,w}(\mathbf{x},\mathbf{y}) = \frac{1}{W} \sum_{i=0}^{w-1} \eta^i f_{t-i}(\mathbf{x},\mathbf{y})\) 与 \(\widehat{g}_{t,w}(\mathbf{x},\mathbf{y}) = \frac{1}{W} \sum_{i=0}^{w-1} \eta^i g_{t-i}(\mathbf{x},\mathbf{y})\)，定义以 \(\mathbf{y}_{t,w}^*(\mathbf{x}) = \arg\min_{\mathbf{y}} \widehat{g}_{t,w}(\mathbf{x},\mathbf{y})\) 为内层稳态的新型窗口平均局部遗憾 \(\text{Reg}_w(T) = \sum_{t=1}^T \|\mathcal{G}_{\mathcal{X}}(\mathbf{x}_t, \nabla \widehat{f}_{t,w}(\mathbf{x}_t, \mathbf{y}_{t,w}^*(\mathbf{x}_t)), \gamma)\|^2\)。WOBO 针对滑动系统联合更新变量并引入综合残差终止准则： $\(\|\widetilde{\nabla}\widehat{f}_{t,w}\|^2 + \kappa_F \|\nabla_{\mathbf{y}}\widehat{g}_{t,w}\|^2 + 8\kappa_g^2 \|\nabla_{\mathbf{v}}\widehat{\Phi}_{t,w}\|^2 \leq \frac{\delta^2}{W^2}\)$ 该准则能精准检测滑动超梯度模长的上界，使 WOBO 在完全无需任何环境变分先验假设的前提下，直接实现匹配理论下界 \(\Omega(T/W^2)\) 的最优 \(O(T/W^2)\) 窗口局部遗憾；同时其单循环变体 WOBO-SL 亦达到 \(O(T/W)\) 的轻量级遗憾。
损失函数 / 训练策略¶
算法使用具有投影性质的梯度映射（Gradient Mapping）作为外层变量更新器： $\(\mathbf{x}_{t+1} = \mathbf{x}_t - \gamma \mathcal{G}_{\mathcal{X}}(\mathbf{x}_t, \widetilde{\nabla} f_t, \gamma) = \arg\min_{\mathbf{u} \in \mathcal{X}} \left\{ \langle \widetilde{\nabla} f_t, \mathbf{u} \rangle + \frac{1}{2\gamma} \|\mathbf{u} - \mathbf{x}_t\|^2 \right\}\)$ 外层步长严格约束在 \(\gamma \leq 1/(2L_F)\)，内层步长满足 \(\alpha \leq 1/L_{g,1}\)，伴随矩阵求解步长满足 \(\beta \leq 1/L_{g,1}\)。
实验关键数据¶
主实验¶
论文首先在可精确控制函数变分 \(V_T\) 与解漂移 \(H_{2,T}\) 的合成对抗函数集（\(T=1000, \alpha=0.1, \gamma=0.05\)）上对比验证理论局部遗憾界；随后在真实数据流任务（MNIST 动态加噪率超清洗与动态类别不平衡损失调优）上全面测试了累积局部遗憾。
| 实验场景 / 变分模式 | 变分参数配置 | 评估指标 | AOBO (本文) | SOBOW (NeurIPS 23) | OBBO (Bohne 24) |
|---|---|---|---|---|---|
| 合成测试 Pattern (a) (固定 \(H_{2,T}=18\), 变 \(V_T\)) |
\(B=500, n=1\) (\(V_T=2.0\)) | 标准累积局部遗憾 | 300.011 | 954.342 | 400.173 |
| 合成测试 Pattern (a) | \(B=250, n=2\) (\(V_T=4.0\)) | 标准累积局部遗憾 | 500.018 | 1154.342 | 600.170 |
| 合成测试 Pattern (a) | \(B=100, n=5\) (\(V_T=10.0\)) | 标准累积局部遗憾 | 1100.030 | 1754.336 | 1200.165 |
| 合成测试 Pattern (a) | \(B=50, n=10\) (\(V_T=20.0\)) | 标准累积局部遗憾 | 2100.015 | 2754.323 | 2200.156 |
| 合成测试 Pattern (a) | \(B=10, n=50\) (\(V_T=100.0\)) | 标准累积局部遗憾 | 10100.005 | 11064.305 | 10200.104 |
| 合成测试 Pattern (b) (固定 \(V_T=100\), 变 \(H_{2,T}\)) |
\(B=10, n=50\) (\(H_{2,T}=18.0\)) | 标准累积局部遗憾 | 10100.005 | 11064.305 | 10200.104 |
| 合成测试 Pattern (b) | \(B=10, n=25\) (\(H_{2,T}=36.0\)) | 标准累积局部遗憾 | 10100.005 | 11688.409 | 10400.103 |
| 合成测试 Pattern (b) | \(B=10, n=10\) (\(H_{2,T}=90.0\)) | 标准累积局部遗憾 | 10100.005 | 13560.512 | 11000.098 |
| 合成测试 Pattern (b) | \(B=10, n=5\) (\(H_{2,T}=180.0\)) | 标准累积局部遗憾 | 10100.005 | 16591.754 | 12000.090 |
| 合成测试 Pattern (b) | \(B=10, n=1\) (\(H_{2,T}=900.0\)) | 标准累积局部遗憾 | 10100.005 | 99717.328 | 20000.039 |
消融实验¶
针对 WOBO 算法在动态带噪数据超清洗任务（时间步 \(T=3000\)）中的滑动窗口长度 \(w\) 与衰减因子 \(\eta\) 进行敏感性消融分析：
| 实验配置 (参数设置) | 窗口有效累加权重 \(W\) | 理论遗憾阶数 \(O(T/W^2)\) | 累积窗口平均遗憾表现 | 说明 |
|---|---|---|---|---|
| 固定 \(\eta=0.9\), 窗口 \(w=1\) | 1.000 | 基准阶数 \(O(T)\) | 最高 (基线水平) | 无历史窗口加权平均效应 |
| 固定 \(\eta=0.9\), 窗口 \(w=3\) | 2.710 | 下降 ~86.4% | 显著下降 | 历史信息有效抑制高频漂移 |
| 固定 \(\eta=0.9\), 窗口 \(w=5\) | 4.095 | 下降 ~94.0% | 进一步收敛 | 大窗口平滑环境梯度波动 |
| 固定 \(\eta=0.9\), 窗口 \(w=10\) | 6.513 | 下降 ~97.6% | 最低 | 完美匹配 \(O(T/W^2)\) 衰减理论 |
| 固定 \(w=5\), 权重 \(\eta=0.5\) | 1.938 | 较高 | 次优 | 衰减过快，历史利用率低 |
| 固定 \(w=5\), 权重 \(\eta=0.7\) | 2.773 | 中等 | 良好 | 权重均衡过渡 |
| 固定 \(w=5\), 权重 \(\eta=0.9\) | 4.095 | 较低 | 最优 | 充分利用局部滑动平滑增益 |
关键发现¶
- 对内层解漂移完全解耦：合成实验 Pattern (b) 直观证实，随着内层极小点漂移量 \(H_{2,T}\) 从 18.0 激增至 900.0，SOBOW 的遗憾暴增近 9 倍（11064.3 攀升至 99717.3），OBBO 的遗憾翻倍（10200.1 增至 20000.0），而 AOBO 的遗憾严格恒定在 10100.005，数值表现精准服从 \(\text{Reg}(T) \approx 100(1 + V_T)\)。
- 单循环算力与性能极佳平衡：全单循环变体 FSOBO 在数据超清洗与动态类别不平衡任务中，计算耗时仅为多循环 AOBO 与 OBBO 的几分之一，且累积局部遗憾与测试集准确率全面优于既有的在线一阶动量方法 SOGD。
- 窗口平均的双向增益：WOBO 与 WOBO-SL 证明了同时平滑内层目标函数对消除 \(H_{1,T}, H_{2,T}\) 依赖的决定性作用，且增大窗口尺寸能以 \(1/W^2\) 的速率衰减局部遗憾。
亮点与洞察¶
- 自适应阈值打破固定步数魔咒：传统方法常误以为固定内层循环是控制计算量的前提，本文反其道而行之，采用以误差容忍度 \(\delta\) 动态截断的自适应迭代，证明了内层总迭代次数仍严密受控在 \(O(T\log T)\) 内，却奇迹般消除了局部遗憾界中对内层漂移量 \(H_{2,T}\) 的理论依赖。
- 构造性下界奠定领域基准：作者利用坐标正交激活构造与分块时变目标，不仅给出了标准局部遗憾 \(\Omega(1+V_T)\) 的严格下界证明，还首次推导出窗口平均双层遗憾的 \(\Omega(T/W^2)\) 严格下界，完成了上界与下界的完全匹配闭环。
局限与展望¶
- 确定性反馈假设：论文理论体系主要建立在确定性梯度与无偏评估的前提下，针对随机梯度采样下的在线噪声传播，算法仍需扩展方差缩减或动量跟踪机制。
- 内层强凸性约束：内层目标严格局限于强凸函数族，对于弱凸甚至非凸内层目标（如多层神经网络直接作为内层表征）的动态追踪仍是有待攻克的难题。
相关工作与启发¶
- vs OBBO & SOBOW: 二者均依赖固定的内层展开步数或 Neumann 级数近似，其标准和窗口局部遗憾均附带内层解变分项 \(H_{2,T}\)；本文通过自适应动态停止准则与联合窗口平滑，彻底移除了这一依赖并达到紧匹配下界。
- vs SOGD: SOGD 虽提供随机环境下的单循环在线方案，但其遗憾界依赖于更复杂的环境变分累加项；本文提出的 FSOBO 与 WOBO-SL 结构更紧凑，在确定性设置下给出了显著收敛且理论更紧致的局部遗憾保证。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次建立非凸-强凸 OBO 在标准与窗口局部遗憾下的匹配紧下界与自适应解耦算法。
- 实验充分度: ⭐⭐⭐⭐☆ 理论验证（合成对抗分析）严密自洽，并在真实在线数据清洗与类别不平衡任务上完成了充分对比。
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰严密，从引理递进到定理的证明链条逻辑完整。
- 价值: ⭐⭐⭐⭐⭐ 为在线双层学习与动态环境超参数优化提供了极具指导意义的理论界限与实用单循环范式。