跳转至

Learning Theory for Kernel Bilevel Optimization

会议: NeurIPS 2025
arXiv: 2502.08457
作者: Fares El Khoury (INRIA/Université Grenoble Alpes), Edouard Pauwels (Toulouse School of Economics), Samuel Vaiter (CNRS/Université Côte d'Azur), Michael Arbel (INRIA/Université Grenoble Alpes)
代码: fareselkhoury/KBO
领域: optimization
关键词: 双层优化, 核方法, 泛化理论, RKHS, 经验过程, U-process, 隐式微分

一句话总结

首次为核双层优化（KBO）建立了有限样本泛化界，证明目标函数值和梯度的插入估计误差均以\(\mathcal{O}(1/\sqrt{m}+1/\sqrt{n})\)的参数速率一致收敛，并将该理论应用于双层梯度下降算法的统计精度分析。

研究背景与动机

问题背景

双层优化在机器学习中广泛应用，涵盖超参数调优、元学习、逆问题和强化学习等场景。其核心结构是外层目标隐式依赖于内层优化问题的解。现有理论工作主要集中在参数化设定（有限维空间+强凸内层），通过算法稳定性或随机双层优化收敛性来分析泛化性能。

已有工作的不足

  • 有限维假设限制表达力：现有泛化分析（Bao et al. 2021, Zhang et al. 2024）要求内外层参数均在固定维度的欧几里得空间中，模型被限制为线性函数
  • 非参数设定的空白：当内层变量在RKHS等无穷维函数空间中时，参数维度随样本量增长（表征定理），现有框架无法处理"参数空间维度变化"的统计分析
  • 强凸性 vs 表达力的矛盾：放松强凸性（如深度网络）会导致内层解不稳定，难以获得泛化保证；保持强凸性则需要核方法等非参数途径
  • 已有核双层工作缺少统计分析：Keerthi et al. (2006)、Kunapuli et al. (2008) 利用表征定理将核双层转化为有限维问题，但未研究样本量对泛化的影响

核心动机

在保持强凸性的同时突破有限维限制——利用RKHS的丰富表达力和良好的数学结构，首次建立非参数双层优化的学习理论，特别是有限样本泛化界。

方法详解

问题建模（KBO）

给定再生核Hilbert空间\(\mathcal{H}\)和核函数\(K\)，内外层目标为期望形式：

\[L_{out}(\omega,h)=\mathbb{E}_{\mathbb{Q}}[\ell_{out}(\omega,h(x),y)], \quad L_{in}(\omega,h)=\mathbb{E}_{\mathbb{P}}[\ell_{in}(\omega,h(x),y)]+\frac{\lambda}{2}\|h\|_{\mathcal{H}}^2\]

目标：\(\min_{\omega\in\mathcal{C}} \mathcal{F}(\omega) := L_{out}(\omega, h_\omega^\star)\)，其中\(h_\omega^\star = \arg\min_{h\in\mathcal{H}} L_{in}(\omega,h)\)。

五个基本假设：(A) 核可测性；(B) 核有界\(K(x,x)\leq\kappa\)；(C) 目标空间\(\mathcal{Y}\)紧致；(D) 损失函数\(C^3\)光滑；(E) 内层损失关于\(v\)凸。

关键理论贡献1：RKHS中的隐式微分

通过隐函数定理在RKHS中推导\(\nabla\mathcal{F}(\omega)\)的显式表达：

\[\nabla\mathcal{F}(\omega) = \mathbb{E}_{\mathbb{Q}}[\partial_\omega\ell_{out}(\omega,h_\omega^\star(x),y)] + \mathbb{E}_{\mathbb{P}}[\partial_{\omega,v}^2\ell_{in}(\omega,h_\omega^\star(x),y)a_\omega^\star(x)]\]

其中\(a_\omega^\star\)是伴随函数，为强凸二次目标\(L_{adj}\)在\(\mathcal{H}\)中的极小值点。关键难点在于处理无穷维空间中的算子——Hessian \(\partial_h^2 L_{in}\)是\(\mathcal{H}\to\mathcal{H}\)的算子、交叉导数\(\partial_{\omega,h}^2 L_{in}\)是\(\mathcal{H}\to\mathbb{R}^d\)的算子，需要通过Bochner积分理论和Lebesgue控制收敛定理来交换求导与期望。

关键理论贡献2：微分与统计估计的可交换性

Proposition 3.1：经验目标\(\hat{\mathcal{F}}\)的梯度\(\nabla\hat{\mathcal{F}}(\omega)\)恰好等于总梯度\(\nabla\mathcal{F}(\omega)\)的插入估计量\(\widehat{\nabla\mathcal{F}}(\omega)\)。即"先微分再估计"与"先估计再微分"给出相同结果——这一可交换性是RKHS结构的特有性质，在\(L^2\)空间中不成立。

主要定理：一致泛化界（Theorem 4.1）

对任意紧子集\(\Omega\subset\mathbb{R}^d\)，在五个假设下：

\[\mathbb{E}\left[\sup_{\omega\in\Omega}|\mathcal{F}(\omega)-\hat{\mathcal{F}}(\omega)|\right] \leq C\left(\frac{1}{\sqrt{m}}+\frac{1}{\sqrt{n}}\right)\]
\[\mathbb{E}\left[\sup_{\omega\in\Omega}\|\nabla\mathcal{F}(\omega)-\widehat{\nabla\mathcal{F}}(\omega)\|\right] \leq C\left(\frac{1}{\sqrt{m}}+\frac{1}{\sqrt{n}}\right)\]

其中\(C\)仅依赖于\(\Omega\)、维度\(d\)、正则化参数\(\lambda\)、核上界\(\kappa\)及损失函数导数的局部上界。

证明的三步策略

  1. 逐点误差分解：将\(|\mathcal{F}-\hat{\mathcal{F}}|\)分解为\(\delta_\omega^{out}\)（外层样本误差）和\(\partial_h\delta_\omega^{in}\)（内层Fréchet导数误差）的组合；梯度误差则进一步展开为五项
  2. 经验过程控制：对实值项（如\(\delta_\omega^{out}\), \(\partial_\omega\delta_\omega^{out}\)），直接用经典经验过程理论的极大不等式，利用函数族的packing数控制复杂度
  3. 退化U-process控制：对涉及\(\partial_h\)的RKHS值项，利用再生性质\(\|f\|_\mathcal{H}^2 = \langle f, f\rangle_\mathcal{H}\)将其平方转化为依赖样本对的实值函数，形成二阶退化U-process，应用Sherman (1994) 的极大不等式

算法应用：双层梯度下降的泛化保证（Corollary 4.2）

对无约束KBO的梯度下降\(\omega_{t+1}=\omega_t-\eta\nabla\hat{\mathcal{F}}(\omega_t)\)：

\[\mathbb{E}\left[\min_{i=0,\ldots,t}\|\nabla\mathcal{F}(\omega_i)\|\right] \leq \bar{c}\left(\frac{1}{\sqrt{m}}+\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{t+1}}\right)\]

迭代充分多步后，统计误差主导：\(\mathbb{E}[\limsup_{i\to\infty}\|\nabla\mathcal{F}(\omega_i)\|] \leq \bar{c}(1/\sqrt{m}+1/\sqrt{n})\)。

正则化参数\(\lambda\)的多重角色

\(\lambda\)同时控制：(1) 内层强凸性常数；(2) 内层解的有界性和Lipschitz连续性；(3) 外层目标的光滑性；(4) 损失函数的连续模；(5) 经验过程的极大不等式常数。大\(\lambda\)使优化更容易但引入统计偏差，小\(\lambda\)减少偏差但使泛化更困难。

实验关键数据

实验设定

使用工具变量回归（instrumental variable regression）的合成数据验证理论。线性参数化\(f_\omega(t)=\omega^\top\phi(t)\)，采用高斯核，\(n\)从100变化到5000，设\(m=n\)。外层优化用梯度下降+回溯线搜索，停止条件\(\|\nabla\hat{\mathcal{F}}(\omega_i)\|\leq 10^{-5}\)。用\(10^6\)样本+26000个随机Fourier特征近似总体目标。

实验1：泛化误差收敛速率（高斯分布 vs Student-t分布）

度量 分布 经验速率（log-log斜率） 理论预测
\(\|\mathcal{F}(\omega_0)-\hat{\mathcal{F}}(\omega_0)\|\) Gaussian \(\approx -1/2\) \(O(n^{-1/2})\)
\(\|\nabla\mathcal{F}(\omega_0)-\widehat{\nabla\mathcal{F}}(\omega_0)\|\) Gaussian \(\approx -1/2\) \(O(n^{-1/2})\)
\(\|\mathcal{F}(\omega_0)-\hat{\mathcal{F}}(\omega_0)\|\) Student-t (\(\nu=2.1\)) \(\approx -1/2\) \(O(n^{-1/2})\)
\(\|\nabla\mathcal{F}(\omega_0)-\widehat{\nabla\mathcal{F}}(\omega_0)\|\) Student-t (\(\nu=2.1\)) \(\approx -1/2\) \(O(n^{-1/2})\)

所有曲线在log-log尺度下的斜率均接近\(-1/2\)，验证了\(O(1/\sqrt{n})\)的理论收敛速率。95%置信区间非常窄。

实验2：梯度下降的统计精度

度量 说明 经验行为 理论预测
\(\|\nabla\mathcal{F}(\omega_T)\|\) 终止迭代处的总体梯度范数 \(O(n^{-1/2})\)衰减 Corollary 4.2
\(\min_{i\leq T}\|\nabla\mathcal{F}(\omega_i)\|\) 全轨迹最小梯度范数 \(O(n^{-1/2})\)衰减 Corollary 4.2

实验在50次独立运行上取平均，Student-t分布（\(\nu\in\{2.1,2.5,2.9\}\)）和Gaussian分布均表现出一致的\(n^{-1/2}\)速率。平衡样本量\(m=n\)带来最优优化行为。

亮点

  • 首创性理论：首次为非参数（核方法）双层优化建立有限样本泛化界，填补了有限维分析和无穷维设定之间的理论空白
  • 微分-估计可交换性：证明了RKHS中"先微分再统计估计"与"先估计再微分"等价，这一结构性结果在\(L^2\)等其他空间中不成立，是RKHS独有的优良性质
  • U-process技术的创新应用：巧妙利用RKHS再生性质将无穷维误差项转化为二阶退化U-process，避免了覆盖数随维度爆炸的问题
  • 统计-优化trade-off的刻画：Corollary 4.2清晰展示了样本量\((m,n)\)与迭代次数\(t\)之间的平衡关系
  • 理论与实验高度吻合：合成实验精确复现了\(n^{-1/2}\)的理论速率

局限与展望

  • 仅限全批量精确梯度：未覆盖随机双层优化（SGD、SABA等），实际大规模应用中全批量不可行
  • 固定正则化参数\(\lambda\)：常数\(C\)在\(\lambda\to 0\)时可能发散，无法给出无正则化设定下的泛化保证
  • 要求损失光滑（\(C^3\)）：不适用于非光滑损失，如SVM的hinge loss
  • 常数不紧：泛化界中的常数\(C\)可能非常保守，文中未分析其最优性
  • 仅合成数据实验：缺乏真实数据集上的验证
  • 紧集\(\Omega\)约束：\(C\)可能随\(\Omega\)直径增长，全局保证需额外假设

与相关工作的对比

  • Bao et al. (2021)：通过均匀稳定性分析有限维双层优化，得到\(O(T^\kappa/m)\)的泛化率，但受限于固定参数维度，且误差随迭代增大
  • Zhang et al. (2024)：扩展到随机双层优化，得到\(O(1/\sqrt{m})\)的泛化率，但同样限于有限维
  • Oymak et al. (2021)：通过Lipschitz外层损失+近似内层解得到\(O(1/\sqrt{m}+1/\sqrt{n})\)，但仍在有限维
  • Meunier et al. (2024)：在工具变量回归中利用谱过滤获得minimax最优率，但要求损失为二次型且\(\lambda\to 0\)，不适用于一般内层目标
  • Petrulionyte et al. (2024)：提出泛函双层优化框架，但在\(L^2\)空间中微分与估计不可交换，未给出有限样本保证
  • 本文优势：覆盖一般凸内层损失、固定\(\lambda\)设定，利用RKHS的再生性质绕开无穷维困难，给出同时控制目标值和梯度的一致界

评分

  • 新颖性: ⭐⭐⭐⭐⭐ — 将经验过程和U-process理论引入核双层优化，首次建立非参数泛化界
  • 实验充分度: ⭐⭐⭐ — 仅合成数据上的工具变量回归实验，验证了理论速率但缺乏实际应用
  • 写作质量: ⭐⭐⭐⭐⭐ — 理论体系严谨完整，证明思路清晰，交换图等辅助说明到位
  • 价值: ⭐⭐⭐⭐ — 填补重要理论空白，技术贡献扎实，但实际影响有待后续随机/大规模扩展验证

相关论文