技术摘要：关于双层优化中条件数依赖性的研究

问题陈述

本文研究了使用一阶方法寻找 $\epsilon$-驻点（$\epsilon$-stationary point）的双层优化问题的预言复杂度（oracle complexity）。所考虑的具体设定是非凸-强凸（NC-SC）双层优化，定义为：
$$\min_{x \in \mathbb{R}^{d_x}} F(x) = f(x, y^*(x)), \quad \text{其中} \quad y^*(x) = \arg\min_{y \in \mathbb{R}^{d_y}} g(x, y).$$
在此设定中，上层目标函数 $f$ 是非凸的，而下层目标函数 $g$ 对 $y$ 是强凸的。主要的挑战在于收敛速率对下层问题条件数的依赖性，该条件数记为 $\kappa_y = L_1/\mu_y$（其中 $L_1$ 是平滑常数，$\mu_y$ 是强凸常数），以及全局条件数 $\bar{\kappa}_y$。

虽然近期的研究已为确定性平滑问题建立了 $\tilde{O}(\bar{\kappa}_y^4 \epsilon^{-2})$ 或改进后的 $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$ 的上界，但关于条件数依赖性的最优依赖关系仍未知。具体而言，目前尚不清楚双层问题在条件数依赖性方面是否在证明意义上比极小极大（minimax）问题（即 $f = -g$）更难，因为极小极大问题的下界为 $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$。

方法论

作者通过基于**零链（zero-chain）**结构构建“困难实例”来建立新的下界，这是优化下界文献中广泛使用的一种技术。

1. 困难实例构建：
   其核心创新是对用于 NC-SC 极小极大问题的链式困难实例进行的修改。作者引入了一种构造方式，利用上层函数 $f$ 与下层函数 $g$ 之间的不对称性。

   • 双源特征化： 该构造利用两个特定的变量来放大条件数依赖性：
     • 一个耦合变量 $y$（在下层中），用于捕捉计算 $y^*(x)$ 的复杂度。
     • 一个重缩放变量 $z$（从上层移动到下层），用于捕捉超目标函数（hyper-objective）平滑度中的依赖性。
   • 机制： 通过精心设计变量 $x, z$ 和 $y$ 之间的连接，并在 $z$ 而非 $x$ 上添加非凸正则化，作者创造了一种场景，使得有效链长度在 $x$ 层面被缩放了一个与 $\kappa_y$ 相关的因子。具体而言，超目标函数等价于在一个经过 $K^2 x$ 缩放的非凸零链上进行评估，其中 $K = \Omega(\sqrt{\kappa_y})$。

2. 算法类别：
   作者证明其下界适用于以下算法：

   • 确定性一阶算法： 访问梯度 $\nabla f$ 和 $\nabla g$ 的算法。
   • 基于 HVP 的算法： 访问 Hessian-向量乘积（HVP）的算法。作者证明，对于二次下层函数，HVP 预言机在信息获取方面与一阶预言机是等价的，这意味着下界对这两类算法均成立。
   • 随机算法： 使用基于随机零链的独立构造，以处理噪声和方差。

核心贡献与结果

1. 确定性 NC-SC 下界

本文建立了双层问题与极小极大问题在条件数依赖性上的第一个可证明的差距。

• 一阶平滑 ($p=1$)： $\Omega(\kappa_y^{5/2} \epsilon^{-2})$。这改进了极小极大问题的 $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$ 下界。
• 二阶平滑 ($p=2$)： $\Omega(\kappa_y^{31/14} \epsilon^{-12/7})$。
• 任意阶平滑 ($p \ge 3$)： $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$。

2. 凸与强凸设定

作者将结果扩展到超目标函数为凸或强凸的设定：

• 凸-强凸 (C-SC)： 将之前的下界从 $\tilde{\Omega}(\min\{\kappa_y, \epsilon^{-3/2}\}/\sqrt{\epsilon})$ 提升至 $\Omega(\kappa_y^{3/2}/\sqrt{\epsilon})$。
• 强凸-强凸 (SC-SC)： 将之前的 $\tilde{\Omega}(\kappa_y \sqrt{\kappa_x})$ 提升至 $\tilde{\Omega}(\kappa_y^{3/2} \sqrt{\kappa_x})$。

3. 随机 NC-SC 下界

对于具有噪声梯度的随机问题：

• 下界： $\Omega(\kappa_y^4 \epsilon^{-4})$（由方差项主导）。
• 见解： 作者认为，在随机设定中，方差（由重缩放变量放大）是根本的瓶颈，而非偏差（由耦合变量捕捉）。这导致其下界比关注偏差的同期工作显著更紧。

4. 精炼的上界

为了将下界置于背景中，作者通过在内层循环（下层求解器）应用 Nesterov 加速来精炼现有的上界：

• 对于一阶平滑确定性问题，上界被精炼为 $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$；若下层函数为二次函数，则为 $\tilde{O}(\kappa_y^{5/2} \epsilon^{-2})$。
• 这使得下界与二次下层问题的上界之间的差距缩小到了一个很小的多项式对数因子或较小的多项式因子，表明在这些特定设定下接近最优。

重要性与主张

本文声称提供了双层优化与极小极大优化在条件数依赖性方面第一个可证明的分离。

• 根本难度： 结果表明，双层问题在证明意义上比极小极大问题更具挑战性。增加的 $\kappa_y$ 依赖性（例如 $\kappa_y^{5/2}$ 对比 $\sqrt{\kappa_y}$）反映了源于双层结构本身的根本困难，特别是下层解计算与上层平滑度之间的相互作用。
• 方差 vs. 偏差： 在随机设定中，这项工作确定了方差是限制收敛速度的主要因素，为为什么随机双层优化如此困难提供了新的视角。
• 紧致性： 对于二次下层问题，建立的下界被证明是近乎最优的，因为精炼后的上界在小因子范围内与下界相匹配。

作者指出，虽然他们的界对于二次下层函数是紧致的，但为一般非二次函数建立更紧的界仍是一个开放问题。他们也指出，将其随机下界扩展到高阶平滑度的随机算法以及其他设定（如均方平滑度）仍有待研究。