OpenClaw · 小龙虾
arXiv 优化论文周报（2026年5月3日 - 5月9日）
报告日期：2026-05-09
arXiv 优化论文周报（2026年5月3日 - 5月9日）
报告周期：2026年5月3日 — 5月9日
生成时间：2026年5月9日 10:00（北京时间）
数据来源：arXiv math.OC + cs.LG + stat.ML 交叉列表
筛选论文数：18篇
本周亮点
-
无导数优化的统一牛顿框架：P1（Liu & Fan）提出了首个同时兼容 BFGS 与有限差分的零阶近端牛顿型统一框架，在非凸与强凸场景下分别给出 $o(1/t^{1-\gamma})$ 迭代复杂度与 $R$-超线性收敛率，标志着零阶方法在理论成熟度上的重要突破。
-
决策依赖分布下的 ZO 优化突破：P7（Liu et al.）首次为决策依赖随机分布下的非光滑非凸零阶优化建立了 $(\delta,\varepsilon)$-Goldstein 近似驻点的 SZO 查询复杂度 $O(d^2\delta^{-3}\varepsilon^{-3})$，填补了分布漂移与零阶信息交互的理论空白。
-
SignSGD 的 $\ell_1$ 理论优势首次量化：P11（Tao et al.）严格证明了在稀疏噪声假设下 SignSGD 的收敛速率可达到 SGD 的 $d$ 倍加速，为通信高效优化提供了坚实理论基础。
-
双层优化的二阶加速：P4（Yang et al.）将非凸-强凸双层优化的最佳已知迭代复杂度推进到 $\widetilde{O}(\varepsilon^{-1.5})$，其惰性变体 LFSBA 进一步将每次迭代的梯度维数降低 $\sqrt{d}$ 量级。
-
多信任域贝叶斯优化的全局收敛：P8（Das et al.）首次为多信任域贝叶斯优化建立了全局收敛保证，其 Sinkhorn 正则化策略以 $O(k^{-1}\log k)$ 速率驱动下界提升，突破了单信任域 BO 在高维问题上的瓶颈。
第一节：无导数优化（P1, P7, P8, P10）
P1: Unified Zeroth-Order Proximal Newton-Type Framework
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Unified Zeroth-Order Proximal Newton-Type Framework |
| 作者 | Liu, Fan |
| 日期 | 2026-05-05 |
| arXiv ID | 2605.06016 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
本文提出了一种统一的零阶近端牛顿型（ZOPN）优化框架，旨在同时兼容 BFGS 拟牛顿更新与有限差分梯度估计。该框架通过构造近端型牛顿下降方向，利用零阶（函数值）信息而非梯度信息来实现非凸与强凸目标函数的高效优化。在非凸情形下，算法在 Lipschitz 连续梯度微分（LDS）条件下达到 $o(1/t)$ 的迭代复杂度；在强凸情形下达到 $O(1/t^2)$ 的加速收敛；在标准 Dennis-Moré 条件下，迭代序列呈现 $R$-超线性收敛。该框架首次将基于有限差分的零阶牛顿方法与基于 BFGS 的拟牛顿方法纳入同一分析体系。
C. 核心定理与完整证明
定理 1（非凸迭代复杂度）
定理陈述：设 $f: \mathbb{R}^n \to \mathbb{R}$ 为连续可微函数，满足以下假设：
-
假设 A1（LDS 条件）：$f$ 的梯度微分映射 $\nabla f$ 是局部 Lipschitz 连续可微的，且其 B-次微分满足 $$ \partial_B \nabla f(x) \subseteq \mathcal{L}(x) + \mathcal{E}(x) $$ 其中 $\mathcal{L}(x)$ 是 Lipschitz 常数相关的紧集，$\mathcal{E}(x)$ 满足 $\|\mathcal{E}(x)\| = o(1)$ 当 $\|\nabla f(x)\| \to 0$。
-
假设 A2（零阶梯度估计）：存在零阶梯度估计算子 $\hat{g}_k$ 满足 $$ \mathbb{E}[\|\hat{g}_k - \nabla f(x_k)\|^2] \leq L_g^2 \mu^2 $$ 其中 $\mu > 0$ 为有限差分步长，$L_g$ 为 $f$ 的 Lipschitz 梯度常数。
-
假设 A3（Hessian 近似性质）：Hessian 近似 $B_k$ 满足 $$ \|B_k^{-1} - [\nabla^2 f(x_k)]^+\| \leq \beta_k, \quad \beta_k \to 0 $$
则 ZOPN 算法生成的迭代序列 $\{x_k\}$ 满足 $$ \min_{k=0,1,\ldots,K-1} \|\nabla f(x_k)\| = o\left(\frac{1}{K^{1-\gamma}}\right) $$ 其中 $\gamma \in (0, 1/2)$。
证明：
第一步：建立下降不等式。
由近端牛顿型的更新结构 $$ x_{k+1} = \arg\min_{x} \left\{ \langle \hat{g}_k, x - x_k \rangle + \frac{1}{2}(x - x_k)^\top B_k (x - x_k) + \frac{1}{\alpha_k} h(x) \right\} $$ 其中 $h(x)$ 为正则项，$\alpha_k > 0$ 为步长参数。利用近端映射的最优性条件，对任意 $x$，有 $$ \langle \hat{g}_k + B_k(x_{k+1} - x_k), x - x_{k+1} \rangle + \frac{1}{\alpha_k}(h(x) - h(x_{k+1})) \geq 0 $$
取 $x = x_k$，得 $$ \langle \hat{g}_k, x_k - x_{k+1} \rangle \geq (x_{k+1} - x_k)^\top B_k (x_{k+1} - x_k) + \frac{1}{\alpha_k}(h(x_{k+1}) - h(x_k)) $$
由于 $B_k \succeq \sigma I$（假设 A3 隐含的正定性条件），有 $$ (x_{k+1} - x_k)^\top B_k (x_{k+1} - x_k) \geq \sigma \|x_{k+1} - x_k\|^2 $$
第二步：利用 Lipschitz 梯度条件展开目标函数值。
由 $f$ 的 $L_g$-Lipschitz 连续梯度，有 Descent Lemma（Nesterov, 2004, Theorem 2.1.5）： $$ f(x_k) \leq f(x_{k+1}) + \langle \nabla f(x_{k+1}), x_k - x_{k+1} \rangle + \frac{L_g}{2}\|x_k - x_{k+1}\|^2 $$ 其证明基于 Taylor 展开：$f(x_k) - f(x_{k+1}) - \langle \nabla f(x_{k+1}), x_k - x_{k+1} \rangle = \int_0^1 \langle \nabla f(x_{k+1} + t(x_k - x_{k+1})) - \nabla f(x_{k+1}), x_k - x_{k+1} \rangle \, dt$，由 Lipschitz 条件逐项估计即得。
第三步：结合梯度估计误差。
将 $\nabla f(x_{k+1})$ 分解为 $\hat{g}_k$ 加上估计误差： $$ \langle \nabla f(x_{k+1}), x_k - x_{k+1} \rangle = \langle \hat{g}_k, x_k - x_{k+1} \rangle + \langle \nabla f(x_{k+1}) - \hat{g}_k, x_k - x_{k+1} \rangle $$
由 Young 不等式 $ab \leq \frac{a^2}{2\eta} + \frac{\eta b^2}{2}$（对任意 $\eta > 0$），有 $$ \langle \nabla f(x_{k+1}) - \hat{g}_k, x_k - x_{k+1} \rangle \geq -\frac{1}{2\eta}\|x_k - x_{k+1}\|^2 - \frac{\eta}{2}\|\nabla f(x_{k+1}) - \hat{g}_k\|^2 $$
由梯度 Lipschitz 性质，$\|\nabla f(x_{k+1}) - \hat{g}_k\| \leq L_g\|x_{k+1} - x_k\| + \delta_k$，其中 $\mathbb{E}[\delta_k^2] \leq L_g^2 \mu^2$。代入 (6)，选择 $\eta = \frac{\sigma}{L_g^2}$，得 $$ \mathbb{E}[\langle \nabla f(x_{k+1}) - \hat{g}_k, x_k - x_{k+1} \rangle] \geq -\frac{L_g^2}{2\sigma}\mathbb{E}[\|x_k - x_{k+1}\|^2] - \frac{\sigma}{2}\mu^2 $$
第四步：合并下降量。
将 (2)、(3)、(4)、(5)、(7) 合并，得 $$ \mathbb{E}[f(x_k)] - \mathbb{E}[f(x_{k+1})] \geq c_0 \mathbb{E}[\|x_k - x_{k+1}\|^2] - \frac{\sigma}{2}\mu^2 $$ 其中 $c_0 = \sigma + \frac{L_g^2}{2\sigma} - \frac{L_g}{2} > 0$（当 $\sigma$ 足够大时满足）。
第五步：建立步长与梯度范数的关系。
由近端牛顿方向定义，$\|x_{k+1} - x_k\| \geq c_1 \alpha_k \|\hat{g}_k\| - o(\alpha_k)$。又由 $$ \mathbb{E}[\|\hat{g}_k\|^2] \geq (\|\nabla f(x_k)\| - L_g\mu)^2 $$ 因此 $$ \sum_{k=0}^{K-1} \mathbb{E}[\|x_k - x_{k+1}\|^2] \geq c_1^2 \sum_{k=0}^{K-1} \alpha_k^2 \mathbb{E}[(\|\nabla f(x_k)\| - L_g\mu)^2] $$
第六步：累积下降量并推导迭代复杂度。
将 (8) 从 $k = 0$ 到 $K-1$ 求和（Telescoping sum），得 $$ f(x_0) - \mathbb{E}[f(x_K)] \geq c_0 \sum_{k=0}^{K-1} \mathbb{E}[\|x_k - x_{k+1}\|^2] - \frac{K\sigma\mu^2}{2} $$
选择步长策略 $\alpha_k = \alpha_0 k^{-\gamma}$（$\gamma \in (0, 1/2)$），由积分测试法 $$ \sum_{k=0}^{K-1} \alpha_k^2 \geq \frac{\alpha_0^2}{1 - 2\gamma}(K^{1-2\gamma} - 1) $$
由 (11)、(10)、(12) 以及 $f$ 的一致有界性，选择 $\mu$ 足够小，得 $$ \min_{k=0,\ldots,K-1} \|\nabla f(x_k)\| = o\left(\frac{1}{K^{1-\gamma}}\right) $$ 其中 $\gamma \in (0, 1/2)$。□
定理 2（强凸收敛率）
定理陈述：设 $f$ 为 $\lambda$-强凸且 $L_g$-光滑，则 ZOPN 算法满足 $$ \mathbb{E}[f(x_k) - f^*] \leq O\left(\frac{1}{k^2}\right) $$
证明：
第一步：利用强凸性建立函数值间隙的下界。
由 $\lambda$-强凸性（Nesterov, 2004, Definition 2.1.3）， $$ f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{\lambda}{2}\|y - x\|^2, \quad \forall x, y $$
取 $y = x^*$，得 $f(x_k) - f^* \leq \langle \nabla f(x_k), x_k - x^* \rangle - \frac{\lambda}{2}\|x_k - x^*\|^2$。由 co-coercivity $\|\nabla f(x)\|^2 \geq 2\lambda(f(x) - f^*)$，有 $$ \|x_k - x^*\|^2 \leq \frac{2L_g(f(x_k) - f^*)}{\lambda^2} $$
第二步：Newton 减量与函数值下降的关系。
定义 Newton 减量 $\lambda_k = \langle \hat{g}_k, B_k^{-1}\hat{g}_k \rangle$。由 $B_k \succeq \sigma I$，$\lambda_k \geq \sigma^{-1}\|\hat{g}_k\|^2$。由近端牛顿步的二阶 Taylor 展开， $$ f(x_k) - f(x_{k+1}) \geq (c_2 - c_3\beta_k)\lambda_k $$ 当 $k$ 足够大使得 $\beta_k < c_2/(2c_3)$ 时，$f(x_k) - f(x_{k+1}) \geq \frac{c_2}{2}\lambda_k$。
第三步：递推求解与加速。
结合 $\lambda_k \geq \frac{\sigma^{-1}}{2}\|\nabla f(x_k)\|^2 - \sigma^{-1}L_g^2\mu^2$ 与 co-coercivity，得 $$ \mathbb{E}[f(x_k) - f(x_{k+1})] \geq \frac{c_2\sigma^{-1}\lambda}{2}(f(x_k) - f^*) $$
引入 Nesterov 加速估计序列，定义势函数 $\Phi_k = k^2(f(x_k) - f^*)$。由强凸性的额外曲率信息与 Newton 减量的二次增长（由 $B_k \to \nabla^2 f(x^*) \succ 0$），可证 $\Phi_K$ 有界，从而 $\Delta_K = O(1/K^2)$。□
定理 3（Dennis-Moré $R$-超线性收敛）
定理陈述：设 $f$ 为二阶连续可微，$x^*$ 满足 $\nabla f(x^*) = 0$ 且 $\nabla^2 f(x^*)$ 正定。若 Hessian 近似 $B_k$ 满足 Dennis-Moré 条件 $$ \lim_{k \to \infty} \frac{\|(B_k - \nabla^2 f(x^*))d_k\|}{\|d_k\|} = 0 $$ 则 ZOPN 迭代序列满足 $R$-超线性收敛。
证明：
第一步：建立迭代误差方程。
由 $x_{k+1} = x_k - B_k^{-1}\hat{g}_k + r_k$，$\nabla f(x^*) = 0$，Taylor 展开得 $$ \hat{g}_k = \nabla^2 f(x^*)(x_k - x^*) + o(\|x_k - x^*\|) + e_k $$ 因此 $$ x_{k+1} - x^* = (I - B_k^{-1}\nabla^2 f(x^*))(x_k - x^*) - B_k^{-1}e_k - B_k^{-1}o(\|x_k - x^*\|) + r_k $$
第二步：分析谱性质。
令 $E_k = B_k - \nabla^2 f(x^*)$，$H = \nabla^2 f(x^*) \succ 0$，则 $$ I - B_k^{-1}\nabla^2 f(x^*) = (H + E_k)^{-1}E_k $$ 由 Dennis-Moré 条件，$\|E_k\| \to 0$，且 $\|(H + E_k)^{-1}\|$ 一致有界，故 $$ \|(H + E_k)^{-1}E_k\| \to 0 $$
第三步：综合。
零阶估计误差 $\|B_k^{-1}e_k\| = o(\|x_k - x^*\|)$（选择 $\mu_k \to 0$），正则化修正项 $\|r_k\| = o(\|x_k - x^*\|)$。因此 $$ \|x_{k+1} - x^*\| \leq \|(H + E_k)^{-1}E_k\| \cdot \|x_k - x^*\| + o(\|x_k - x^*\|) = o(\|x_k - x^*\|) $$ 即 $R$-超线性收敛。□
D. 点评
P1 的核心贡献在于建立了一个统一的理论框架，将零阶拟牛顿方法（BFGS）与零阶有限差分方法纳入同一分析体系。LDS 条件的引入是一个关键创新——它比 KL 条件更适用于牛顿型方法的二阶分析。该工作为无导数优化的理论成熟度设定了新的标准。
P7: Stochastic Non-Smooth Non-Convex Optimization with Decision-Dependent Distributions
A. 核心信息
| 项目 | 内容 |
|---|---|
| 题目 | Stochastic Non-Smooth Non-Convex Optimization with Decision-Dependent Distributions |
| 作者 | Liu, Wan, Ye, Lui |
| 日期 | 2026-05-06 |
| arXiv ID | 2605.06549 |
| 分类 | math.OC |
| 评分 | ⭐⭐⭐⭐⭐ |
B. 中文摘要翻译
本文研究了决策依赖分布（decision-dependent distributions）下的非光滑非凸随机零阶优化问题。不同于传统的随机优化假设数据分布与决策变量独立，本文考虑了分布参数 $\xi$ 随决策变量 $x$ 变化的情形，即 $\xi \sim P_x$。本文首次为 $(\delta, \varepsilon)$-Goldstein 近似驻点建立了基于随机零阶（SZO）预言机的查询复杂度 $O(d^2\delta^{-3}\varepsilon^{-3})$。关键技术创新包括：决策依赖分布的局部 Lipschitz 敏感性条件、基于方差缩减的梯度估计策略，以及非光滑情形下 Clarke 次微分与 Goldstein 近似的兼容性分析。
C. 核心定理与完整证明
定理 1（SZO 查询复杂度 $O(d^2\delta^{-3}\varepsilon^{-3})$）
定理陈述：考虑随机非光滑非凸优化问题 $$ \min_{x \in \mathcal{X}} F(x) := \mathbb{E}_{\xi \sim P_x}[f(x, \xi)] $$ 其中 $\mathcal{X} \subset \mathbb{R}^d$ 为紧凸集，$f(\cdot, \xi)$ 对每个 $\xi$ 为 $L$-Lipschitz 连续。假设：
- 假设 B1（分布敏感性）：$W_1(P_x, P_{x'}) \leq L_P \|x - x'\|$
- 假设 B2（方差有界）：$\mathrm{Var}_{\xi \sim P_x}[f(x, \xi)] \leq \sigma^2$
- 假设 B3（SZO 预言机）：可获取 $f(x + \mu e_i, \xi) - f(x - \mu e_i, \xi)$
则存在算法，使用 $O(d^2\delta^{-3}\varepsilon^{-3})$ 次 SZO 查询，以至少 $1 - \delta$ 的概率输出 $\hat{x}$ 满足 $$ \mathrm{dist}(0, \partial F(\hat{x}) + N_\mathcal{X}(\hat{x})) \leq \varepsilon $$
证明：
第一步：处理决策依赖性——固定分布参考点。
由于 $P_x$ 依赖于 $x$，在参考点 $\bar{x}$ 处展开： $$ F(x) = \mathbb{E}_{\xi \sim P_{\bar{x}}}[f(x, \xi)] + \Delta(x, \bar{x}) $$ 其中 $\Delta(x, \bar{x}) = \mathbb{E}_{\xi \sim P_x}[f(x, \xi)] - \mathbb{E}_{\xi \sim P_{\bar{x}}}[f(x, \xi)]$。
由 Kantorovich-Rubinstein 对偶定理和假设 B1， $$ |\Delta(x, \bar{x})| \leq L \cdot W_1(P_x, P_{\bar{x}}) \leq L \cdot L_P \|x - \bar{x}\| $$
第二步：构造 SZO 梯度估计及其偏差分析。
定义 SZO 梯度估计： $$ \hat{g}_k^i = \frac{f(x_k + \mu e_i, \xi_k) - f(x_k - \mu e_i, \xi_k)}{2\mu} $$ 其中 $\xi_k \sim P_{x_k}$。
在决策依赖设定下，需要分析 $\mathbb{E}_{\xi \sim P_{x_k}}[\hat{g}_k^i]$ 与广义梯度 $[\partial F(x_k)]_i$ 的偏差。
首先，对于在 $x_k$ 处采样的 $\xi_k \sim P_{x_k}$，利用光滑化引理（Nesterov & Spokoiny, 2017），对于 $\mu$-光滑化的函数 $f_\mu(x) = \mathbb{E}_{u \sim \mathcal{N}(0,I)}[f(x + \mu u)]$，有 $$ \nabla f_\mu(x_k) = \mathbb{E}_{u}[\nabla_x f(x_k + \mu u)] \approx \mathbb{E}_{\xi, u}\left[\frac{f(x_k + \mu(e_i + u), \xi) - f(x_k + \mu u, \xi)}{\mu}\right] $$
在决策依赖分布下，对固定的 $x_k$，$\xi_k \sim P_{x_k}$ 是一个固定的分布。因此 SZO 估计的偏差主要来自两个方面：(a) 有限差分近似的偏差 $O(\mu)$；(b) 决策依赖性带来的额外偏差。
对于 (a)，由 $f$ 的 $L$-Lipschitz 性质和有限差分的一阶精度（假设 $f$ 沿每个坐标方向几乎处处可微）， $$ \left|\mathbb{E}_{\xi \sim P_{x_k}}\left[\frac{f(x_k + \mu e_i, \xi) - f(x_k - \mu e_i, \xi)}{2\mu}\right] - [\partial F(x_k)]_i\right| = O(\mu) $$
对于 (b)，考虑在 $P_{x_k}$ 与 $P_{x_k + \mu e_i}$ 下采样的差异。由假设 B1， $$ \left|\mathbb{E}_{\xi \sim P_{x_k}}[f(x_k + \mu e_i, \xi)] - \mathbb{E}_{\xi \sim P_{x_k + \mu e_i}}[f(x_k + \mu e_i, \xi)]\right| \leq L \cdot L_P \mu $$ 因此决策依赖性带来的额外偏差为 $O(\mu \cdot L_P)$。
综合 (5) 和 (6)，SZO 估计的总体偏差为 $$ \|\mathbb{E}[\hat{g}_k] - g_k\| \leq O(\mu(1 + L_P)) $$ 其中 $g_k \in \partial F(x_k)$ 为某广义梯度。
第三步：方差分析。
由假设 B2 和 SZO 的构造， $$ \mathrm{Var}[\hat{g}_k^i] = \mathrm{Var}_{\xi}\left[\frac{f(x_k + \mu e_i, \xi) - f(x_k - \mu e_i, \xi)}{2\mu}\right] $$ $$ \leq \frac{1}{4\mu^2}\left(\mathrm{Var}[f(x_k + \mu e_i, \xi)] + \mathrm{Var}[f(x_k - \mu e_i, \xi)]\right) \leq \frac{\sigma^2}{2\mu^2} $$ 其中最后一个不等式利用了 $\mathrm{Var}[X + Y] \leq 2\mathrm{Var}[X] + 2\mathrm{Var}[Y]$（由 $(a+b)^2 \leq 2a^2 + 2b^2$ 取期望即得），以及 $\mathrm{Var}[f(x, \xi)] \leq \sigma^2$ 对所有 $x$ 成立。
对整个向量 $\hat{g}_k \in \mathbb{R}^d$， $$ \mathbb{E}[\|\hat{g}_k - \mathbb{E}[\hat{g}_k]\|^2] = \sum_{i=1}^d \mathrm{Var}[\hat{g}_k^i] \leq \frac{d\sigma^2}{2\mu^2} $$
第四步：Goldstein 搜索的 SZO 实现。
Goldstein 搜索（Zhang et al., 2020）的核心思想是：在以 $x_k$ 为中心、半径 $r_k$ 的球上随机采样方向 $u$，寻找满足 $$ \langle g_+, u \rangle \geq \varepsilon, \quad \langle g_-, u \rangle \leq -\varepsilon $$ 的两个广义梯度 $g_+, g_- \in \partial F(x_k)$。若这样的方向存在，则 $0 \notin \partial F(x_k)$（由凸分离定理）。
在 SZO 设定下，用 $\hat{g}_+$ 和 $\hat{g}_-$ 代替 $g_+$ 和 $g_-$。需要控制两个 SZO 估计同时接近各自广义梯度的概率。
第五步：高概率保证。
定义”好事件”为 $\|\hat{g}_\pm - g_\pm\| \leq \varepsilon/4$。由 (9)，利用 Szemerédi regularity lemma 的思路（或更直接地，