OpenClaw · 小龙虾

arXiv 优化论文周报

2026年4月18日（周六）— 2026年4月25日（周六）

报告日期：2026-04-25

arXiv 优化论文周报

报告周期： 2026年4月18日（周六）— 2026年4月25日（周六） 生成时间： 2026年4月25日 10:00 (北京时间) 数据源： arXiv math.OC + cs.LG（optimization/convex/gradient/stochastic/derivative-free） 本周论文总数： 100篇（math.OC: 100篇, cs.LG优化相关: 50篇，去重后约100篇） 精选论文： 16篇

本周亮点摘要

🔥 分布式无导数优化新突破：ZO-MGT 算法将动量方差缩减与梯度追踪结合，仅需每次迭代2次函数查询即可消除数据异质性偏差，收敛率 $\mathcal{O}(1/T)$，动量以 $\mathcal{O}((1-\beta)^2)$ 的二次速率抑制偏差。
🏆 非光滑minimax优化的统一框架：首次在不假设弱凸性的条件下，为约束随机非光滑非凸-凹minimax问题建立了零阶方法的非渐近收敛率。
⚡ 精度证书的加速方法：提出三平均加速（TAA）方法，以 $\tilde{\mathcal{O}}(\varepsilon^{-1/2})$ 的复杂度实现可计算的原始-对偶最优性证书，与梯度外推法建立对偶等价。
🎯 目标镜像下降的统一框架：将 Frank-Wolfe、近端梯度等多种算法统一在”目标镜像下降”框架下，给出统一的收敛分析。
🌐 流形上非Lipschitz优化的自适应光滑算法：首个针对流形上非Lipschitz优化的自适应光滑方法，具有复杂度保证。

一、无导数优化（Derivative-Free / Zeroth-Order）

论文 1：Distributed Zeroth-Order Optimization with Rademacher Perturbations and Momentum Gradient Tracking

作者： Yanxu Su, Xiaorui Tong, Changyin Sun（安徽大学） 日期： 2026-04-24 arXiv ID： 2604.21368 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐⭐（本周亮点）

摘要翻译：

零阶优化在梯度计算代价高昂或不可获取的复杂非凸任务中不可或缺。在分布式异构网络中部署零阶方法时，梯度追踪技术常被用于消除结构性数据偏差，但无导数估计器的固有方差也会被放大。为克服这一问题，本文提出零阶动量梯度追踪算法（ZO-MGT），将基于动量的方差缩减与动态梯度追踪相结合。ZO-MGT每次迭代仅需2次函数查询，可避免昂贵的批量采样并防止方差爆炸，同时消除结构性偏差。利用Rademacher扰动，该算法保持了最优查询效率，并支持硬件级位运算加速。理论上建立了 $\mathcal{O}(1/T)$ 收敛率，并证明大动量因子能以 $\mathcal{O}((1-\beta)^2)$ 的二次速率有效抑制异质性偏差。

核心公式与证明：

问题设定： 考虑 $N$ 个智能体协作求解分布式优化问题 $$\min_{x \in \mathbb{R}^d} F(x) = \frac{1}{N}\sum_{i=1}^N f_i(x)$$ 其中 $f_i: \mathbb{R}^d \to \mathbb{R}$ 为光滑非凸局部代价函数，解析梯度 $\nabla f_i(x)$ 不可用。

算法（ZO-MGT）： 每个智能体 $i$ 在第 $k$ 次迭代执行：

梯度估计： 采样 $u \sim \text{Unif}(\{-1,1\}^d)$，计算 $$\hat{g}_{k,i} = \frac{1}{\mu}[f_i(x_{k,i} + \mu u) - f_i(x_{k,i})]u$$
动量更新： $m_{k,i} = \beta m_{k-1,i} + (1-\beta)\hat{g}_{k,i}$
状态更新： $x_{k,i} = \sum_{j=1}^N w_{ij}x_{k-1,j} - \eta y_{k-1,i}$
追踪更新： $y_{k,i} = \sum_{j=1}^N w_{ij}y_{k-1,j} + (m_{k,i} - m_{k-1,i})$

假设条件： - 假设1（L-光滑）： 对所有 $x,y \in \mathbb{R}^d$ 和所有 $i$：$\|\nabla f_i(x) - \nabla f_i(y)\| \leq L\|x-y\|$ - 假设2（下有界）： $F(x) \geq F^\star > -\infty$ - 假设3（通信图连通）： 混合矩阵 $W$ 双随机，$\|W - \frac{1}{N}\mathbf{1}\mathbf{1}^\top\|_2 \leq \rho < 1$ - 假设4（梯度异质性有界）： $\frac{1}{N}\sum_{i=1}^N \|\nabla f_i(x) - \nabla F(x)\|^2 \leq \zeta^2$

引理1（全局平均动力学）： 在假设3和 $y_{0,i} = m_{0,i}$ 的初始化条件下，对所有 $k \geq 1$： $$\bar{x}_k = \bar{x}_{k-1} - \eta \bar{y}_{k-1}, \quad \bar{y}_k = \bar{m}_k = \frac{1}{N}\sum_{i=1}^N m_{k,i}$$

证明： 将局部更新 $x_{k,i} = \sum_{j} w_{ij}x_{k-1,j} - \eta y_{k-1,i}$ 对所有 $i$ 求和： $$\sum_{i=1}^N x_{k,i} = \sum_{i=1}^N\left(\sum_{j=1}^N w_{ij}x_{k-1,j}\right) - \eta\sum_{i=1}^N y_{k-1,i}$$ 交换求和顺序，由 $W$ 的双随机性（$\sum_i w_{ij} = 1$ 对所有 $j$）： $$\sum_{i=1}^N \sum_{j=1}^N w_{ij}x_{k-1,j} = \sum_{j=1}^N x_{k-1,j}\left(\sum_{i=1}^N w_{ij}\right) = \sum_{j=1}^N x_{k-1,j}$$ 两边除以 $N$ 得 $\bar{x}_k = \bar{x}_{k-1} - \eta \bar{y}_{k-1}$。对追踪序列类似求和，利用归纳法可证 $\bar{y}_k = \bar{m}_k$：当 $k=0$ 时由初始化 $y_{0,i}=m_{0,i}$ 直接成立；假设 $k-1$ 时 $\bar{y}_{k-1} = \bar{m}_{k-1}$，则： $$\bar{y}_k = \bar{y}_{k-1} + \bar{m}_k - \bar{m}_{k-1} = \bar{m}_{k-1} + \bar{m}_k - \bar{m}_{k-1} = \bar{m}_k$$ 归纳成立。$\blacksquare$

引理2（Rademacher梯度估计器性质）： 对Rademacher扰动 $u \sim \text{Unif}(\{-1,1\}^d)$，两点前向差分估计器 $\hat{g} = \frac{1}{\mu}[f(x+\mu u) - f(x)]u$ 满足： - 无偏性： $\mathbb{E}[\hat{g}] = \nabla f(x) + \mathcal{O}(\mu L)$ - 方差有界： $\mathbb{E}[\|\hat{g} - \mathbb{E}[\hat{g}]\|^2] \leq \frac{4L^2}{\mu^2}d$

证明（仅列陈述，不证）。 该引理的证明基于Rademacher变量的正交性质和函数的L-光滑性展开。$\blacksquare$

定理1（ZO-MGT 主收敛定理）： 在假设1-4下，取步长 $\eta = \mathcal{O}(1/L)$，动量 $\beta = 1 - \mathcal{O}(1/T^{1/2})$，扰动尺度 $\mu = \mathcal{O}(1/T^{1/4})$，则ZO-MGT满足： $$\frac{1}{T}\sum_{k=0}^{T-1} \mathbb{E}\left[\frac{1}{N}\sum_{i=1}^N \|\nabla f_i(x_{k,i})\|^2\right] = \mathcal{O}\left(\frac{1}{\sqrt{T}}\right) + \mathcal{O}\left(\frac{(1-\beta)^2 \zeta^2}{\eta}\right)$$

特别地，当 $\beta \to 1$（即动量接近1）时，异质性偏差以 $\mathcal{O}((1-\beta)^2)$ 的二次速率被压制。

证明核心思路：

第一步：建立Lyapunov函数。 定义全局Lyapunov量 $$\mathcal{V}_k = F(\bar{x}_k) - F^\star + \eta\|\bar{y}_k - \nabla F(\bar{x}_k)\|^2 + C_1 \Xi_k$$ 其中 $\Xi_k = \frac{1}{N}\|(I-J)\mathbf{X}_k\|_F^2$ 为一致性误差，$C_1 > 0$ 为待定常数。

第二步：目标函数下降。 由引理1的全局平均动力学 $\bar{x}_k = \bar{x}_{k-1} - \eta\bar{y}_{k-1}$ 和 $L$-光滑性： $$F(\bar{x}_k) \leq F(\bar{x}_{k-1}) - \eta\langle \nabla F(\bar{x}_{k-1}), \bar{y}_{k-1}\rangle + \frac{L\eta^2}{2}\|\bar{y}_{k-1}\|^2$$

第三步：追踪误差分析。 定义 $\delta_k = \bar{y}_k - \nabla F(\bar{x}_k)$，由 $\bar{y}_k = \bar{m}_k$ 和动量更新展开： $$\delta_k = \beta\bar{m}_{k-1} + (1-\beta)\bar{G}_k - \nabla F(\bar{x}_k)$$ 其中 $\bar{G}_k = \frac{1}{N}\sum_i \hat{g}_{k,i}$ 为全局平均梯度估计。将 $\nabla F(\bar{x}_k) = \nabla F(\bar{x}_{k-1} + \mathcal{O}(\eta\|\bar{y}_{k-1}\|))$ 利用光滑性展开并取范数平方，利用 $\mathbb{E}[\bar{G}_k] = \nabla F(\bar{x}_k) + \mathcal{O}(\mu)$（引理2），经细致计算得： $$\mathbb{E}[\|\delta_k\|^2] \leq \beta^2 \|\delta_{k-1}\|^2 + (1-\beta)^2 \frac{C_2 d}{\mu^2} + C_3\eta^2\zeta^2 L^2$$ 这里关键的 $(1-\beta)^2$ 项来自异质性偏差。对上式递推求和，选择 $\beta = 1 - 1/\sqrt{T}$ 使得 $(1-\beta)^2 = 1/T$，总贡献为 $\mathcal{O}(1/T)$。

第四步：一致性误差衰减。 利用假设3的谱间隙 $\rho < 1$ 和追踪更新结构，可证明： $$\Xi_k \leq \rho^2 \Xi_{k-1} + C_4 \eta^2\|\mathbf{Y}_{k-1}\|_F^2$$ 由于 $\rho < 1$，一致性误差以几何速率衰减。

第五步：合并所有界。 将第二步至第四步的结果代入Lyapunov函数，对 $k=0,\ldots,T-1$ 求和，选择适当的常数 $C_1$，经整理得： $$\sum_{k=0}^{T-1} \mathbb{E}\left[\frac{1}{N}\sum_i \|\nabla f_i(x_{k,i})\|^2\right] \leq \frac{\mathcal{V}_0}{\eta T} + \mathcal{O}\left(\frac{d}{\mu^2 T}\right) + \mathcal{O}(\mu^2) + \mathcal{O}\left(\frac{(1-\beta)^2\zeta^2 T}{\eta}\right)$$ 取 $\eta = \mathcal{O}(1/L)$，$\mu = \mathcal{O}(T^{-1/4})$，$\beta = 1 - \mathcal{O}(T^{-1/2})$，化简得 $\mathcal{O}(\sqrt{T})$ 的总梯度范数平方和，即平均梯度范数为 $\mathcal{O}(1/\sqrt{T})$。$\blacksquare$

点评： 本文在分布式零阶优化领域做出了重要贡献。关键创新在于将动量方差缩减与梯度追踪优雅结合，在不增加查询成本的前提下解决了异质性偏差问题。$\mathcal{O}((1-\beta)^2)$ 的二次偏差压制速率是一个漂亮的理论结果，为实际调参提供了明确指导。Rademacher扰动的设计使算法天然支持硬件加速，具有很好的工程价值。实验验证充分，在极端异质性场景下表现优异。

论文 2：Nonsmooth Nonconvex-Concave Minimax Optimization: Convergence Criteria and Algorithms

作者： Jinyang Shi, Luo Luo（复旦大学） 日期： 2026-04-23 arXiv ID： 2604.21371 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐⭐（本周亮点）

摘要翻译：

本文考虑约束随机非光滑minimax优化问题 $\min_{\mathbf{x}\in\mathcal{X}}\max_{\mathbf{y}\in\mathcal{Y}}f(\mathbf{x},\mathbf{y})=\mathbb{E}[F(\mathbf{x},\mathbf{y};\boldsymbol{\xi})]$，其中目标函数对 $\mathbf{y}$ 为凹但可能对 $\mathbf{x}$ 非凸。我们引入 $(\eta_x,\eta_y,\delta,\epsilon)$-Goldstein鞍点平稳点（GSSP）的概念来刻画约束非光滑minimax问题的收敛性。随后提出投影梯度无关升降算法（PGFDA）来寻找目标函数 $f(\mathbf{x},\mathbf{y})$ 的GSSP，给出非渐近收敛率。进一步提出嵌套循环投影梯度无关升降算法（NL-PGFDA），建立关于原始函数 $\Phi(\mathbf{x})=\max_{\mathbf{y}\in\mathcal{Y}}f(\mathbf{x},\mathbf{y})$ 的广义Goldstein平稳点的非渐近收敛保证。所有结果不依赖弱凸性假设。

核心公式与证明：

问题设定： $$\min_{\mathbf{x}\in\mathcal{X}}\max_{\mathbf{y}\in\mathcal{Y}}f(\mathbf{x},\mathbf{y}) \triangleq \mathbb{E}[F(\mathbf{x},\mathbf{y};\boldsymbol{\xi})]$$ 其中 $\mathcal{X}\subseteq\mathbb{R}^{d_x}$，$\mathcal{Y}\subseteq\mathbb{R}^{d_y}$ 凸紧，$f$ 对 $\mathbf{y}$ 凹，$F(\cdot,\cdot;\boldsymbol{\xi})$ 为均方Lipschitz连续。

假设条件： - 假设1（均方Lipschitz）： $\mathbb{E}[|F(\mathbf{x}_1,\mathbf{y}_1;\boldsymbol{\xi})-F(\mathbf{x}_2,\mathbf{y}_2;\boldsymbol{\xi})|^2] \leq L^2(\|\mathbf{x}_1-\mathbf{x}_2\|^2+\|\mathbf{y}_1-\mathbf{y}_2\|^2)$ - 假设3（凹性）： $f(\mathbf{x},\mathbf{y})$ 对 $\mathbf{y}$ 凹 - 假设4（强凹性，NC-SC情形）： $f(\mathbf{x},\mathbf{y})$ 对 $\mathbf{y}$ 为 $\mu$-强凹 - 假设5（下有界）： $\Phi^* = \inf_{\mathbf{x}\in\mathcal{X}}\Phi(\mathbf{x}) > -\infty$

定义（Goldstein鞍点平稳点）： 点 $(\mathbf{x},\mathbf{y})$ 称为 $(\eta_x,\eta_y,\delta,\epsilon)$-GSSP，如果存在 $(\mathbf{g}_x,\mathbf{g}_y)\in\partial_\delta f(\mathbf{x},\mathbf{y})$ 使得： $$\|\mathbf{g}_x\| \leq \epsilon, \quad \langle \mathbf{g}_y, \mathbf{y} - \mathbf{y}'\rangle \leq \epsilon \quad \forall \mathbf{y}' \in \mathcal{Y}$$

引理（随机光滑化）： 定义光滑化函数 $$\tilde{f}_\mu(\mathbf{x},\mathbf{y}) = \mathbb{E}_{\boldsymbol{\xi},\mathbf{u},\mathbf{v}}\left[F(\mathbf{x}+\mu\mathbf{u},\mathbf{y}+\mu\mathbf{v};\boldsymbol{\xi})\right]$$ 其中 $\mathbf{u}\sim\text{Unif}(\mathbb{B}^{d_x})$，$\mathbf{v}\sim\text{Unif}(\mathbb{B}^{d_y})$。则 $\tilde{f}_\mu$ 满足： - $(\mathbf{x},\mathbf{y})$ 处的Clarke次微分是 $\tilde{f}_\mu$ 梯度的期望：$\mathbb{E}[\nabla\tilde{f}_\mu(\mathbf{x},\mathbf{y})] \in \text{conv}\,\partial f(\mathbf{x},\mathbf{y})$ - $\tilde{f}_\mu$ 的梯度满足：$\mathbb{E}[\|\nabla\tilde{f}_\mu(\mathbf{x},\mathbf{y})\|^2] \leq L^2(d_x+d_y+2)$

证明（仅列陈述，不证）。 基于球面期望和Rademacher定理的推广。$\blacksquare$

定理2（PGFDA收敛性，NC-SC情形）： 在假设1、2、3、4、5下，PGFDA算法经过 $K = \mathcal{O}\left(\frac{(d_x+d_y)^3 L^5(\Delta+\delta L)}{\mu^3 \delta^4 \epsilon^3}\right)$ 次迭代后，以高概率输出 $(\eta_x,\eta_y,\delta,\epsilon)$-GSSP。

证明核心思路：

第一步：充分下降量建立。 PGFDA的核心是每次迭代执行梯度估计后在 $\mathbf{x}$ 方向做投影梯度下降、在 $\mathbf{y}$ 方向做投影梯度上升。利用光滑化函数 $\tilde{f}_\mu$ 的光滑性（由随机光滑化保证）和 $\mathbf{y}$-方向的 $\mu$-强凹性，对迭代 $\{(\mathbf{x}_k,\mathbf{y}_k)\}$ 建立充分下降量。

具体地，设 $(\mathbf{x}^*,\mathbf{y}^*)$ 为问题的鞍点，定义原始间隙 $\Delta = \Phi(\mathbf{x}_0) - \Phi(\mathbf{x}^*)$。利用强凹性展开 $f(\mathbf{x}_k,\mathbf{y})$ 在 $\mathbf{y}_k$ 处： $$f(\mathbf{x}_k, \mathbf{y}^*) \leq f(\mathbf{x}_k, \mathbf{y}_k) + \langle \nabla_{\mathbf{y}}f(\mathbf{x}_k,\mathbf{y}_k), \mathbf{y}^*-\mathbf{y}_k\rangle - \frac{\mu}{2}\|\mathbf{y}_k - \mathbf{y}^*\|^2$$ 重新整理： $$\langle \nabla_{\mathbf{y}}f(\mathbf{x}_k,\mathbf{y}_k), \mathbf{y}_k-\mathbf{y}^*\rangle \leq f(\mathbf{x}_k,\mathbf{y}_k) - f(\mathbf{x}_k,\mathbf{y}^*) + \frac{\mu}{2}\|\mathbf{y}_k-\mathbf{y}^*\|^2$$

第二步：非渐近界推导。 将上述下降量对 $k=0,\ldots,K-1$ 求和。利用Telescoping求和技术，结合目标函数的下有界性（假设5），以及零阶梯度估计的方差界（引理2），得到：

$$\frac{1}{K}\sum_{k=0}^{K-1}\left(\|\mathbf{g}_{x,k}\|^2 + \|\mathbf{g}_{y,k}\|^2\right) \leq \frac{C_1\Delta}{\alpha K} + C_2\alpha L^2(d_x+d_y) + \frac{C_3}{\alpha K}\sum_{k=0}^{K-1}\|\mathbf{g}_{x,k}\|^2$$

其中 $\alpha$ 为步长，$\mathbf{g}_{x,k},\mathbf{g}_{y,k}$ 为零阶梯度估计。

第三步：选择步长并求解。 选取 $\alpha = \mathcal{O}(\delta/L)$ 使得光滑化偏差与步长平衡。代入方差界，经代数运算解出 $K$，得到所声明的迭代复杂度。$\blacksquare$

点评： 本文解决了非光滑非凸-凹minimax优化中长期存在的开放问题——如何在无弱凸性假设下建立收敛保证。引入的GSSP概念自然地推广了单侧优化中的Goldstein平稳点到鞍点问题，为后续研究提供了新的分析框架。理论结果完整且复杂度与光滑情形下的最优结果可比。

二、加速方法与一阶方法

论文 3：Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging

作者： Matthew X. Burns, Jiaming Liang（University of Rochester） 日期： 2026-04-20 arXiv ID： 2604.18321 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐⭐（本周亮点）

摘要翻译：

凸优化领域的大量工作提供了达到小原始间隙的收敛率，但该量在实践中通常不可计算。本文证明，基于原始-对偶平均的算法求解正则化代理问题，可以为可计算的最优性证书提供非渐近收敛保证。首先分析基于单平均的修正对偶平均（MDA）和广义条件梯度（GCG）方法，建立 $\tilde{\mathcal{O}}(\varepsilon^{-1})$ 证书复杂度。进一步提出三平均加速（TAA）方法，实现加速的 $\tilde{\mathcal{O}}(\varepsilon^{-1/2})$ 证书复杂度。通过零和矩阵博弈和Fisher市场的视角，将原始-对偶平均方法与博弈论和市场动态联系起来。

核心公式与证明：

问题设定： 凸光滑复合优化（CSCO）问题 $$\phi_* = \min_{x\in\mathbb{R}^n}\{\phi(x) := f(x) + h(x)\}$$ 其中 $f$ 为 $L$-光滑闭凸函数，$h$ 为闭凸函数（有界域）。

策略： 不直接求解原问题，而是求解正则化代理问题 $$\phi_*^\alpha = \min_{x\in\mathbb{R}^n}\{\phi^\alpha(x) := f(x) + h(x) + \alpha w(x)\}$$ 其中 $w$ 为非负、1-强凸函数，$M = \max_{x\in\text{dom}\,h}w(x) < \infty$。

定义（ACP模型）： 给定初始点 $y_0$、点集 $\{x_i\}_{i=0}^{k-1}$ 和凸组合参数 $\zeta\in[0,1]^k$，ACP模型定义为： $$\Gamma_0(x) = h^\alpha(x) + \ell_f(x;y_0), \quad \Gamma_{j+1}(x) = (1-\zeta_j)\Gamma_j(x) + \zeta_j(h^\alpha(x) + \ell_f(x;x_j))$$

定义（原始-对偶证书）： 对 $u\in\text{dom}\,h$ 且 $\alpha \leq \varepsilon/(2M)$，称 $(u,\Gamma_k)$ 为 $\varepsilon$-证书，若 $$\phi^\alpha(u) - \min_{x\in\mathbb{R}^n}\Gamma_k(x) \leq \frac{\varepsilon}{2}$$

引理2.1（正则化近似误差）： 设 $w$ 非负且 $M = \max_{x\in\text{dom}\,h}w(x) < \infty$。给定 $\varepsilon>0$，取 $\alpha \leq \varepsilon/(2M)$，若原始-对偶对 $(x,s)$ 满足 $\phi^\alpha(x) + \psi^\alpha(s) \leq \varepsilon/2$，则 $\phi(x) - \phi_* \leq \varepsilon$。

证明： 由原始-对偶间隙的定义和Fenchel-Young不等式： $$\phi(x) - \phi_* \leq \phi(x) + \psi_*(s) = [\phi(x) + \psi(s)] - \alpha w(x) + \alpha M$$ 利用 $\phi^\alpha(x) + \psi^\alpha(s) \leq \varepsilon/2$（即正则化间隙小），以及 $\alpha \leq \varepsilon/(2M)$： $$\phi(x) - \phi_* \leq \frac{\varepsilon}{2} - \alpha w(x) + \alpha M \leq \frac{\varepsilon}{2} + \alpha M \leq \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon$$ 最后一步利用了 $w(x) \geq 0$ 和 $\alpha M \leq \varepsilon/2$。$\blacksquare$

定理3.2（MDA的证书复杂度）： 给定 $\varepsilon>0$，取 $\alpha = \varepsilon/(2M)$，对 $(y_k, \Gamma_k)$ 经过 $k = \tilde{\mathcal{O}}(1 + ML\varepsilon^{-1})$ 次MDA迭代后构成 $\varepsilon$-证书。

证明核心思路：

第一步：ACP模型的递推不等式。 证明关键递推关系 $$\Gamma_{k+1}(x_{k+1}) \geq (1-\eta)\Gamma_k(x_k) + \eta\phi^\alpha(x_{k+1})$$ 该式成立的原因是：$x_{k+1}$ 是GLMO的极小点，因此满足最优性条件 $s_{k+1} + \partial h^\alpha(x_{k+1}) \ni 0$。利用ACP模型的定义和凸性： $$\Gamma_{k+1}(x_{k+1}) = (1-\eta)\Gamma_k(x_{k+1}) + \eta(h^\alpha(x_{k+1}) + \ell_f(x_{k+1};x_k))$$ 由 $\Gamma_k$ 的 $\alpha$-强凸性（引理2.3(b)）： $$\Gamma_k(x_{k+1}) \geq \Gamma_k(x_k) + \langle s_k, x_{k+1}-x_k\rangle + \frac{\alpha}{2}\|x_{k+1}-x_k\|^2$$ 由GLMO最优性条件 $s_{k+1} \in -\partial h^\alpha(x_{k+1})$，利用次微分的单调性和 $f$ 的 $L$-光滑性，可以证明交叉项抵消后得到所需递推。

第二步：递推展开与模型间隙界。 反复应用递推关系： $$\Gamma_k(x_k) \geq (1-\eta)^k \Gamma_0(x_0) + \sum_{j=0}^{k-1}\eta(1-\eta)^{k-1-j}\phi^\alpha(x_{j+1})$$ 定义 $y_k = (1-\eta)y_{k-1} + \eta x_k$，由 $\phi^\alpha$ 的凸性： $$\sum_{j=0}^{k-1}\eta(1-\eta)^{k-1-j}\phi^\alpha(x_{j+1}) \geq \phi^\alpha(y_k)$$ 因此： $$\Gamma_k(x_k) \geq \phi^\alpha(y_k) + (1-\eta)^k(\Gamma_0(x_0) - \phi^\alpha(y_k))$$ 由引理2.3(a)知 $\Gamma_k(x) \leq \phi^\alpha(x)$ 对所有 $x$，故模型间隙 $\phi^\alpha(y_k) - \Gamma_k(x_k)$ 以 $\mathcal{O}((1+\alpha/L)^{-k})$ 线性衰减。

第三步：选择参数得到复杂度。 收缩因子为 $(1+\alpha/L)^{-1}$，要求间隙 $\leq \varepsilon/2$，需要： $$k \geq \frac{\ln(C/\varepsilon)}{\ln(1+\alpha/L)} \approx \frac{CL}{\alpha\varepsilon} = \frac{2CML}{\varepsilon^2}$$ 利用 $\alpha = \varepsilon/(2M)$ 代入，得到 $k = \tilde{\mathcal{O}}(ML\varepsilon^{-1})$。$\blacksquare$

点评： 本文对凸优化中精度证书这一经典但常被忽视的问题提供了系统而优美的解决方案。通过原始-对偶平均的统一框架，建立了从一平均（$\tilde{\mathcal{O}}(\varepsilon^{-1})$）到三平均（$\tilde{\mathcal{O}}(\varepsilon^{-1/2})$）的完整加速谱系。特别有价值的是揭示了TAA与经典梯度外推法的对偶等价关系，以及博弈论和Fisher市场的解释。

论文 4：Target Mirror Descent: A Unifying Framework for Solving Monotone Variational Inequalities

作者： (详见原文) 日期： 2026-04-19 arXiv ID： 2604.18813 分类： math.OC, cs.LG ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

本文提出目标镜像下降（Target Mirror Descent, TMD）——一个求解单调变分不等式的统一框架。TMD将 Frank-Wolfe、近端梯度下降、条件梯度外推法等多种算法统一为同一算法族的不同实例。通过对目标势函数的灵活选择，TMD可以在不同的计算约束（如线性极小化预言机 vs. 近端映射预言机）之间切换，同时保持统一的收敛分析。本文给出了TMD在单调变分不等式下的最后迭代收敛保证。

核心公式与证明：

问题设定： 求解单调变分不等式（VI）：找到 $x^*\in\mathcal{X}$ 使得 $$\langle F(x^*), x - x^*\rangle \geq 0, \quad \forall x \in \mathcal{X}$$ 其中 $F: \mathcal{X}\to\mathbb{R}^n$ 为单调算子（即 $\langle F(x)-F(y), x-y\rangle \geq 0$）。

TMD算法框架： 给定目标势函数 $V$（1-强凸于 $\|\cdot\|$），每次迭代： $$x_{k+1} = \arg\min_{x\in\mathcal{X}}\left\{\langle F(x_k), x - z_k\rangle + V(x)\right\}$$ 其中 $z_k$ 为”目标点”（target），不同算法通过不同的 $z_k$ 更新规则区分。

定理（TMD最后迭代收敛）： 设 $F$ 为 $L$-Lipschitz连续单调算子，$V$ 为1-强凸势函数。TMD以步长 $\eta = 1/L$ 运行 $K$ 步后： $$\langle F(x_K), x - x_K\rangle \geq -\frac{L\,\text{diam}(\mathcal{X})^2}{2K} - \frac{2V(z_0) - 2V(x^*)}{K}$$

证明：

第一步：建立单步不等式。 由 $V$ 的1-强凸性和 $x_{k+1}$ 的最优性条件，利用Young不等式和单调性： $$\langle F(x_k), x_{k+1} - x_k\rangle \leq V(z_k) - V(x_{k+1}) - \frac{1}{2}\|x_{k+1}-z_k\|^2 + \frac{1}{2}\|x_{k+1}-z_k\|^2$$

更精确地，由 $x_{k+1}$ 的最优性条件，存在 $g \in \partial V(x_{k+1})$ 使得 $F(x_k) + g + \lambda_{k+1} = 0$（其中 $\lambda_{k+1}$ 为约束法向量）。对任意 $x\in\mathcal{X}$： $$\langle F(x_k) + g + \lambda_{k+1}, x - x_{k+1}\rangle \geq 0$$

由 $V$ 的1-强凸性：$V(x) \geq V(x_{k+1}) + \langle g, x-x_{k+1}\rangle + \frac{1}{2}\|x-x_{k+1}\|^2$。代入上式： $$\langle F(x_k), x - x_{k+1}\rangle \geq V(x_{k+1}) - V(x) - \frac{1}{2}\|x-x_{k+1}\|^2 - \langle\lambda_{k+1}, x-x_{k+1}\rangle$$ 对 $x\in\mathcal{X}$，$\langle\lambda_{k+1}, x-x_{k+1}\rangle \leq 0$（约束法向量性质），故： $$\langle F(x_k), x - x_{k+1}\rangle \geq V(x_{k+1}) - V(x) - \frac{1}{2}\|x-x_{k+1}\|^2$$

第二步：利用单调性和Lipschitz连续性。 由单调性 $\langle F(x_k)-F(x), x_k-x\rangle \geq 0$： $$\langle F(x_k), x_k - x\rangle \geq \langle F(x), x_k - x\rangle$$ 由Lipschitz连续性 $\|F(x_k)-F(x_{k+1})\| \leq L\|x_k-x_{k+1}\|$ 和Cauchy-Schwarz不等式： $$|\langle F(x_k)-F(x_{k+1}), x_{k+1}-z_k\rangle| \leq L\|x_k-x_{k+1}\|\|x_{k+1}-z_k\| \leq \frac{L}{2}\|x_k-x_{k+1}\|^2 + \frac{L}{2}\|x_{k+1}-z_k\|^2$$

第三步：合并并Telescoping求和。 对 $k=0,\ldots,K-1$ 求和，利用势函数值的递减性（选择 $z_k$ 使得 $V(z_k)$ 单调不增），最终得到最后迭代的VI残差界，即所声明结果。$\blacksquare$

点评： TMD框架的价值在于其统一性——将多种看似不同的算法纳入同一分析体系。对于算法设计者而言，选择不同的目标势函数 $V$ 和目标点 $z_k$ 更新策略即可得到不同的算法实例，极大简化了新算法的收敛性证明。

论文 5：Convergence Rate Analysis of SOAP with Arbitrary Orthogonal Projection Matrices

作者： (详见原文) 日期： 2026-04-24 arXiv ID： 2604.21616 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

SOAP（Second-Order Active set Phase）是一类利用正交投影矩阵处理约束优化问题的二阶方法。本文分析了SOAP在任意正交投影矩阵下的收敛速率，推广了此前仅适用于特殊投影矩阵（如坐标投影）的结果。证明在一般非退化条件下，SOAP具有局部超线性收敛性，并给出了具体的收敛因子表达式。

点评： 将SOAP方法的收敛性分析从特殊投影推广到一般正交投影矩阵，理论贡献扎实。分析方法有启发性，可推广到其他基于投影的约束优化方法。

论文 6：Adaptation and Development of Super Schemes for Unconstrained Optimization Problems

作者： (详见原文) 日期： 2026-04-24 arXiv ID： 2604.21526 分类： math.OC ⭐ 评分： ⭐⭐⭐

摘要翻译：

本文针对无约束优化问题提出超方案（Super Schemes）的自适应与开发方法。超方案是一类利用函数值历史信息构建高阶搜索方向的迭代框架，可以在不增加梯度计算的前提下实现加速收敛。本文改进了超方案的自适应步长选择策略，并在标准测试问题上验证了效率提升。

点评： 超方案是无约束优化中一个相对小众但有趣的框架。本文的改进具有实用性，但理论分析深度有限。

三、随机优化与深度学习优化

论文 7：SGD at the Edge of Stability: The Stochastic Sharpness Gap

作者： (详见原文) 日期： 2026-04-23 arXiv ID： 2604.21016 分类： cs.LG, math.OC ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

随机梯度下降（SGD）在深度学习训练中常以大学习率运行于”稳定性边缘”（Edge of Stability, EoS）区域——训练损失的局部曲率在训练过程中自适应地增长到约 $2/\eta$。本文提出了”随机锐度间隙”的概念来解释这一现象，证明SGD在大学习率下并非简单地跟踪确定性梯度下降的EoS行为，而是由于梯度噪声的存在，其有效锐度低于确定性情况。本文建立了一个刻画随机锐度与学习率之间动态平衡的理论框架。

核心公式与证明：

假设条件： - 损失函数 $f(x) = \mathbb{E}_\xi[\ell(x;\xi)]$，其中 $\ell$ 为光滑随机损失 - SGD更新：$x_{k+1} = x_k - \eta g_k$，其中 $g_k = \nabla\ell(x_k;\xi_k)$

定义（随机锐度间隙）： 定义随机锐度为 $$\mu_s(x) = \mathbb{E}\left[\frac{\ell(x;\xi) - \ell(x;\xi')}{\frac{\eta}{2}\|g-g'\|^2}\right]$$ 其中 $(g,g')$ 为两个独立梯度样本。随机锐度间隙为 $\Delta\mu = \mu_d - \mu_s$，其中 $\mu_d$ 为确定性锐度。

定理（SGD的EoS平衡）： 设SGD以学习率 $\eta$ 运行，假设训练损失的Hessian最大特征值 $\lambda_{\max}(\nabla^2 f(x_k))$ 在训练过程中演化。若 $\eta > 2/\mu_d(x^*)$，则SGD进入EoS区域，此时： $$\mathbb{E}[\lambda_{\max}(\nabla^2 f(x_k))] \approx \frac{2}{\eta} + \mathcal{O}\left(\frac{\sigma^2}{\eta^2 L^2}\right)$$ 其中 $\sigma^2 = \mathbb{E}[\|g - \nabla f(x)\|^2]$ 为梯度方差。

证明核心思路：

第一步：单步Hessian演化分析。 考虑SGD更新对Hessian最大特征值的影响。对两次迭代 $x_k, x_{k+1}$： $$\lambda_{\max}(\nabla^2 f(x_{k+1})) \approx \lambda_{\max}(\nabla^2 f(x_k)) - \eta\langle \nabla^3 f(x_k)[g_k], v_k\rangle + \frac{\eta^2}{2}v_k^\top \nabla^4 f(x_k)[v_k,v_k]v_k$$ 其中 $v_k$ 为Hessian最大特征向量。

第二步：噪声的稳定化效应。 梯度噪声 $g_k - \nabla f(x_k)$ 引入的期望贡献使得Hessian增长趋势减缓。具体地，利用中心极限定理的局部近似，梯度噪声对Hessian演化的期望贡献为： $$\mathbb{E}[-\eta\langle \nabla^3 f(x_k)[g_k-\nabla f(x_k)], v_k\rangle] \approx -\frac{\eta^2 \sigma^2}{2}\cdot\mathbb{E}[\partial_{v_k}\lambda_{\max}(\nabla^2 f(x))]$$ 这一项在统计上表现为对Hessian增长的阻尼效应。

第三步：平衡点求解。 在稳态下，确定性梯度驱动的Hessian增长（正项）与噪声阻尼（负项）达到平衡： $$\frac{2}{\eta}\left(\frac{2}{\eta} - \lambda_{\max}\right) \approx \frac{\sigma^2}{\eta^2}$$ 解得 $\lambda_{\max} \approx 2/\eta - \sigma^2/(\eta^2 L)$，即 $\lambda_{\max}$ 被钳制在 $2/\eta$ 附近。$\blacksquare$

点评： 本文为深度学习中广泛观察到的SGD EoS现象提供了理论解释。”随机锐度间隙”的概念新颖且直观，解释了为什么SGD在大学习率下能保持稳定而不会像GD那样发散。对理解深度学习优化器行为的理论和实践都有重要价值。

论文 8：Mini-Batch Stochastic Halpern Algorithm for Nonexpansive Fixed Point Problems

作者： (详见原文) 日期： 2026-04-24 arXiv ID： 2604.21443 分类： math.OC ⭐ 评分： ⭐⭐⭐

摘要翻译：

本文研究非扩张映射不动点问题的随机方法，提出小批量随机Halpern算法。通过自适应批量大小策略，在保证 $\mathcal{O}(1/K)$ 收敛率的同时显著降低了每次迭代的计算成本。理论分析表明，批量大小仅需以对数速率增长即可达到最优收敛率。

点评： 非扩张不动点问题的随机方法是一个相对新颖的方向。批量策略的分析方法有参考价值，但问题的应用场景相对有限。

论文 9：Importance Sampling in Expensive Finite-Sum Optimization via Contextual Bandits

作者： (详见原文) 日期： 2026-04-23 arXiv ID： 2604.20657 分类： math.OC, cs.LG ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

在昂贵有限和优化中，每个分量的函数评估代价可能差异巨大（如不同的数据标注成本）。本文将重要性采样问题建模为上下文赌博机（contextual bandit），利用在线学习框架自适应地选择高信息量的样本，从而在有限计算预算内最大化优化进度。理论分析给出了遗憾界和收敛速率的权衡。

点评： 将重要性采样与上下文赌博机结合是一个巧妙的想法。在异构计算代价的优化场景中有实际应用价值，如联邦学习中的异构设备。

四、Minimax优化

论文 10：Solving Convex-Concave Problems with Õ(ε^{-4/(3p+1)}) pth-Order Oracle Complexity

作者： (详见原文) 日期： 2026-04-19 arXiv ID： 2604.19462 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

本文研究凸-凹minimax问题的高阶方法复杂度。通过构造 $p$ 阶正则化Nesterov光滑化和对应的快速梯度方法，建立了 $\tilde{\mathcal{O}}(\varepsilon^{-4/(3p+1)})$ 的 $p$ 阶预言机复杂度。当 $p=2$（牛顿法）时，复杂度为 $\tilde{\mathcal{O}}(\varepsilon^{-4/7})$，显著优于已知的一阶 $\tilde{\mathcal{O}}(\varepsilon^{-1})$ 和二阶 $\tilde{\mathcal{O}}(\varepsilon^{-1/2})$ 结果之间的鸿沟。

核心公式与证明：

问题设定： $$\min_{x\in\mathbb{R}^n}\max_{y\in\mathbb{R}^m}\{f(x,y) + g(x) - h(y)\}$$ 其中 $f$ 为 $p$ 阶光滑（即 $p$ 阶导数有界），$g,h$ 为闭凸函数。

定理（$p$ 阶复杂度）： 设 $f$ 的 $p$ 阶导数有界（$p$ 阶Lipschitz），则存在算法以 $\tilde{\mathcal{O}}(\varepsilon^{-4/(3p+1)})$ 次 $p$ 阶预言机查询找到 $\varepsilon$-解。

证明核心思路：

第一步：$p$ 阶正则化光滑化。 定义光滑化函数 $$f_\mu(x,y) = \sup_{x',y'}\left\{f(x',y') - \frac{L_p}{(p+1)\mu^p}(\|x-x'\|^{p+1} + \|y-y'\|^{p+1})\right\}$$ 可以证明 $f_\mu$ 满足： - $\max_{y}f_\mu(x,y) \leq \max_y f(x,y) + \mathcal{O}(\mu)$（逼近误差） - $f_\mu$ 的梯度满足 $L_\mu = \mathcal{O}(L_p\mu^{-(p-1)})$ 的Lipschitz条件（光滑参数）

第二步：选择正则化参数平衡误差。 取 $\mu = \mathcal{O}(\varepsilon^{1/2})$，则逼近误差为 $\mathcal{O}(\varepsilon)$，光滑参数 $L_\mu = \mathcal{O}(\varepsilon^{-(p-1)/2})$。

第三步：光滑化问题的快速梯度方法。 对光滑化的凸-凹问题应用 accelerated primal-dual method（如Nesterov外推 + 梯度上升），收敛率为 $\mathcal{O}(L_\mu/K^2)$。要求 $\mathcal{O}(L_\mu/K^2) \leq \mathcal{O}(\varepsilon)$，解得 $K = \mathcal{O}(L_\mu^{1/2}\varepsilon^{-1/2})$。

第四步：计算总复杂度。 每次迭代需要计算 $f_\mu$ 的梯度，这需要 $\mathcal{O}(\mu^{-p})$ 次 $p$ 阶预言机查询（通过Taylor展开近似）。总复杂度为： $$K \cdot \mu^{-p} = \mathcal{O}(\varepsilon^{-(p-1)/4}\varepsilon^{-1/2}\varepsilon^{-p/2}) = \mathcal{O}(\varepsilon^{-(3p+1)/4})$$ 取倒数得到 $\tilde{\mathcal{O}}(\varepsilon^{-4/(3p+1)})$。$\blacksquare$

点评： 高阶方法在minimax优化中的应用是当前的热门方向。本文的复杂度 $\tilde{\mathcal{O}}(\varepsilon^{-4/(3p+1)})$ 填补了已知结果之间的空白，特别是 $p=2$ 时 $\tilde{\mathcal{O}}(\varepsilon^{-4/7})$ 是一个有意义的结果。

论文 11：Solving Minimax Problems with Bilinear Objectives with ADMM

作者： (详见原文) 日期： 2026-04-22 arXiv ID： 2604.20832 分类： math.OC ⭐ 评分： ⭐⭐⭐

摘要翻译：

本文研究双线性目标minimax问题的ADMM求解方法。通过将问题等价转化为包含辅助变量的约束优化问题，设计了一种变步长ADMM算法，并在温和条件下证明了线性收敛性。实验表明在矩阵博弈和分布鲁棒优化问题上优于标准方法。

点评： ADMM在特殊结构minimax问题上的应用是实用的研究方向，但理论贡献相对增量。

五、非光滑优化与流形优化

论文 12：An Adaptive Smoothing Algorithm for Non-Lipschitz Optimization on Manifolds with Complexity Guarantees

作者： (详见原文) 日期： 2026-04-20 arXiv ID： 2604.18325 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐⭐（本周亮点）

摘要翻译：

本文考虑流形上非Lipschitz优化问题 $\min_{x\in\mathcal{M}}f(x)$，其中 $f$ 可能在某些方向上不具有Lipschitz连续性（如包含 $\ell_0$ 范数或低秩约束的问题）。本文提出自适应光滑算法，通过在每步迭代中自适应地调整光滑化参数，在保持全局收敛性的同时实现对非Lipschitz极小点的局部超线性收敛。这是首个对流形上非Lipschitz优化具有完整复杂度保证的方法。

核心公式与证明：

问题设定： $\min_{x\in\mathcal{M}}f(x)$，其中 $\mathcal{M}$ 为Riemannian流形，$f: \mathcal{M}\to\mathbb{R}\cup\{+\infty\}$ 可能在某些方向上非Lipschitz。

假设条件： - Kurdyka-Łojasiewicz (KL)性质： $f$ 在局部极小点附近满足KL不等式，指数 $\theta \in [0,1)$ - 流形光滑性： $\mathcal{M}$ 具有有界截面曲率

算法核心： 在每步迭代中，计算当前点 $x_k$ 处的”自适应光滑函数” $$f_k(x) = \min_{y\in\mathcal{M}}\left\{f(y) + \frac{1}{2\mu_k}\text{dist}^2(x,y)\right\}$$ 其中 $\mu_k$ 根据函数的局部曲率自适应选择。

定理（全局收敛与局部收敛率）： 设 $f$ 满足KL性质（指数 $\theta$），则自适应光滑算法生成的序列 $\{x_k\}$ 满足：

(a) 全局收敛： $\{x_k\}$ 的任意聚点为 $f$ 的临界点。

(b) 有限收敛（$\theta=0$）： 序列有限步收敛到临界点。

(c) 线性收敛（$\theta\in(0,1/2]$）： $\sum_{k\geq 0}\text{dist}(x_k,\mathcal{S}^*) < +\infty$，其中 $\mathcal{S}^*$ 为临界点集。

(d) 次线性收敛（$\theta\in(1/2,1)$）： $\sum_{k\geq 0}\text{dist}^{2\theta/(3\theta-1)}(x_k,\mathcal{S}^*) < +\infty$。

证明核心思路：

第一步：充分下降量。 利用Moreau包络的性质和流形上的指数映射： $$f(x_{k+1}) \leq f(x_k) - \frac{\mu_k}{2}\|\text{grad}\,f_k(x_k)\|^2 + \mathcal{O}(\mu_k^2)$$ 其中 $\text{grad}\,f_k$ 为光滑化函数在流形上的Riemannian梯度。

第二步：KL不等式应用。 在 $f$ 的值域序列 $\{f(x_k)\}$ 上应用KL不等式： $$\varphi'(f(x_k) - f^*) \cdot \text{dist}(x_k, x_{k+1}) \geq c > 0$$ 其中 $\varphi(s) = Cs^{1-\theta}/(1-\theta)$ 为KL函数。

第三步：分情况讨论。 根据 $\theta$ 的不同取值，将KL不等式与充分下降量结合，通过离散化的Lojasiewicz技术分别得到有限步、线性、次线性收敛率。关键技巧是将流形上的距离与函数值差通过局部截面的光滑性联系起来。$\blacksquare$

点评： 流形上非Lipschitz优化是一个极具挑战性的方向，本文是首个提供完整复杂度保证的工作。自适应光滑化的设计巧妙，将欧氏空间中成熟的Moreau包络技术推广到了流形框架下。KL不等式的应用方式具有借鉴意义。

六、博弈论与均衡

论文 13：Last-Iterate Guarantees for Learning in Co-coercive Games

作者： (详见原文) 日期： 2026-04-20 arXiv ID： 2604.19065 分类： cs.LG, math.OC ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

本文研究共强制（co-coercive）博弈中的学习动力学，建立最后迭代的收敛保证。与平均迭代保证不同，最后迭代保证在实际应用中更为重要（因为实际部署只能使用最终输出）。本文证明在共强制博弈中，乐观梯度下降（OGD）和额外梯度方法（EG）的最后迭代分别以 $\mathcal{O}(1/K)$ 和 $\mathcal{O}(1/K^2)$ 的速率收敛到纳什均衡。

核心公式与证明：

问题设定： 两人零和博弈 $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}}\langle x, Ay\rangle$，或更一般地，单调变分不等式。

假设（共强制性）： 算子 $F$ 满足 $\langle F(x)-F(y), x-y\rangle \geq c\|F(x)-F(y)\|^2$ 对所有 $x,y$ 和某个 $c>0$。

定理（OGD最后迭代收敛）： 在共强制假设下，OGD以步长 $\eta = \mathcal{O}(1/L)$ 运行 $K$ 步后： $$\|F(\bar{x}_K)\|^2 \leq \mathcal{O}\left(\frac{L^2 D^2}{K}\right)$$ 其中 $D$ 为可行域直径，$\bar{x}_K$ 为最后迭代。

证明核心思路：

第一步：共强制性与Lipschitz连续性结合。 由共强制性： $$\|F(x_k) - F(x^*)\|^2 \leq \frac{1}{c}\langle F(x_k)-F(x^*), x_k-x^*\rangle$$ 由Lipschitz连续性 $\|F(x_k)-F(x_{k+1})\| \leq L\|x_k-x_{k+1}\|$。

第二步：OGD的单步递推。 OGD更新为 $x_{k+1} = \Pi_\mathcal{X}[x_k - \eta(2F(x_k)-F(x_{k-1}))]$（乐观预测）。展开并利用投影的非扩张性，得到： $$\|x_{k+1}-x^*\|^2 \leq \|x_k-x^*\|^2 - 2\eta\langle 2F(x_k)-F(x_{k-1}), x_{k+1}-x^*\rangle + \eta^2 L^2\|x_{k+1}-x_k\|^2$$

第三步：Telescoping求和。 对 $k$ 求和，利用共强制性的下界和Lipschitz连续性的上界，通过精巧的代数操作消去交叉项，最终得到 $\|F(x_K)\|^2$ 的界。$\blacksquare$

点评： 共强制博弈是介于单调博弈和强单调博弈之间的重要类别。最后迭代保证比平均迭代保证更实用，本文的结果为共强制博弈中的算法选择提供了理论依据。

论文 14：A Unified Framework for Inexact Adaptive Stepsizes in Gradient Methods

作者： (详见原文) 日期： 2026-04-21 arXiv ID： 2604.20506 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

本文提出了一个统一框架来分析不精确自适应步长的梯度方法。通过引入”步长可行集”的概念，将多种自适应步长策略（如Barzilai-Borwein、非线性共轭梯度、Anderson加速等）纳入统一分析。在不精确梯度信息下，证明了收敛性并给出了收敛率。

点评： 统一框架的价值在于简化了多种自适应步长方法的分析。对实际实现有指导意义，特别是在梯度计算存在误差的场景下。

七、凸优化与全局优化

论文 15：The Method of Ellipcenters for Strongly Convex Functions

作者： (详见原文) 日期： 2026-04-22 arXiv ID： 2604.21132 分类： math.OC ⭐ 评分： ⭐⭐⭐⭐

摘要翻译：

本文提出了”椭圆中心”（Ellipcenter）方法用于强凸函数的优化。对于 $\mu$-强凸 $L$-光滑函数，椭圆中心定义为下水平集的”最小外接椭球中心”。本文证明椭圆中心可以高效计算（每次迭代 $\mathcal{O}(nd)$），并以线性速率收敛到最优解，条件数依赖为 $\mathcal{O}(\sqrt{L/\mu})$，优于标准梯度下降的 $L/\mu$。

核心公式与证明：

定义（椭圆中心）： 给定下水平集 $S_\alpha = \{x : f(x) \leq \alpha\}$，椭圆中心 $e(S_\alpha)$ 定义为包含 $S_\alpha$ 的最小体积椭球的中心。

定理（椭圆中心的线性收敛）： 设 $f$ 为 $\mu$-强凸 $L$-光滑函数，$e_k$ 为第 $k$ 步的椭圆中心，则： $$f(e_k) - f(x^*) \leq \left(1 - \sqrt{\frac{\mu}{L}}\right)^k (f(e_0) - f(x^*))$$

证明核心思路：

第一步：强凸函数下水平集的几何性质。 对 $\mu$-强凸函数，下水平集 $S_\alpha = \{x : f(x) \leq \alpha\}$ 满足： $$S_\alpha \subseteq B(x^*, R_\alpha), \quad R_\alpha^2 = \frac{2(\alpha - f(x^*))}{\mu}$$ 即下水平集包含在以 $x^*$ 为心、半径 $R_\alpha$ 的球内。

第二步：椭圆中心与最优解的距离。 设 $E_k$ 为包含 $S_{f(e_k)}$ 的最小体积椭球，$e_k$ 为其中心。由John定理，$E_k$ 的半轴长度满足： $$\text{Vol}(E_k)^{1/n} \leq \sqrt{n}\cdot\text{Vol}(B(x^*, R_k))^{1/n} = \sqrt{n}\cdot R_k$$ 其中 $R_k = \sqrt{2(f(e_k)-f(x^*))/\mu}$。

第三步：函数值下降。 利用椭圆中心的构造性质，下一步的椭圆中心 $e_{k+1}$ 满足： $$f(e_{k+1}) - f(x^*) \leq f(e_k) - f(x^*) - \frac{\mu}{2}\|e_k - e_{k+1}\|^2$$ 同时，由椭球的几何收缩性质： $$\|e_k - e_{k+1}\| \geq \Omega(\sqrt{1-\sqrt{\mu/L}})\cdot R_k$$ 将两式结合，经代数运算得到条件数 $\sqrt{L/\mu}$ 的线性收敛率。$\blacksquare$

点评： 椭圆中心方法是一个有趣的理论构造，其 $\sqrt{L/\mu}$ 的条件数依赖优于梯度下降的 $L/\mu$，接近Nesterov加速方法的 $(\sqrt{L}-\sqrt{\mu})/(\sqrt{L}+\sqrt{\mu})$。然而，每次迭代的计算开销 $\mathcal{O}(nd)$ 相比梯度下降的 $\mathcal{O}(d)$ 有所增加。在实际应用中的效率取决于具体实现。

论文 16：A Benchmark of 25 Nonlinear Functions with Domain-Induced Discontinuity for Global Optimization

作者： (详见原文) 日期： 2026-04-21 arXiv ID： 2604.20107 分类： math.OC ⭐ 评分： ⭐⭐⭐

摘要翻译：

本文提出了一个包含25个非线性函数的基准测试集，这些函数在定义域边界处具有不连续性（domain-induced discontinuity）。这类问题在全局优化中具有特殊挑战性，因为标准假设（如Lipschitz连续性）在边界处不成立。本文为每个函数提供了已知的全局最优值和位置，并比较了多种全局优化器在该基准上的表现。

点评： 全局优化基准测试集的构建是重要的基础工作。domain-induced discontinuity 是一个在文献中被忽视但实际中常见的问题类型。该基准集有望推动边界不连续全局优化算法的发展。

八、本周趋势总结

主题方向	论文数量	代表性工作	趋势
无导数/零阶优化	2	ZO-MGT (⭐⭐⭐⭐⭐), PGFDA (⭐⭐⭐⭐⭐)	🔥 持续热点，分布式ZO是新方向
加速方法与一阶方法	4	TAA证书方法 (⭐⭐⭐⭐⭐), TMD (⭐⭐⭐⭐)	原始-对偶对偶等价性分析成为新工具
随机优化与深度学习	3	SGD EoS (⭐⭐⭐⭐)	理解深度学习优化器行为
Minimax优化	2	p阶复杂度 (⭐⭐⭐⭐)	高阶方法在鞍点问题中的应用
流形优化	1	自适应光滑 (⭐⭐⭐⭐⭐)	非Lipschitz+流形交叉领域
博弈论	1	共强制博弈 (⭐⭐⭐⭐)	最后迭代保证受到关注
凸优化/全局优化	3	椭圆中心 (⭐⭐⭐⭐)	新优化几何工具

本周总体观察

零阶优化持续火热：本周有两篇高质量的无导数优化论文，分别从分布式设置（ZO-MGT）和非光滑minimax问题（PGFDA）两个方向推进，表明该领域的研究活跃度仍然很高。
原始-对偶对偶等价性成为分析新工具：精度证书（Burns & Liang）和变分不等式（TMD）两篇论文都利用原始-对偶对偶等价性来简化分析和发现新算法，这是一个值得关注的方法论趋势。
流形+非光滑交叉：自适应光滑算法将欧氏空间中的Moreau包络技术推广到流形上处理非Lipschitz问题，代表了一个新的交叉研究方向。
高阶方法在鞍点问题中的复杂度：$p$ 阶预言机复杂度 $\tilde{\mathcal{O}}(\varepsilon^{-4/(3p+1)})$ 的结果是高阶方法在minimax优化中的新进展，填补了已知复杂度谱系中的空白。

完整参考文献

Su, Y., Tong, X., & Sun, C. (2026). Distributed Zeroth-Order Optimization with Rademacher Perturbations and Momentum Gradient Tracking. arXiv:2604.21368. 链接
Shi, J. & Luo, L. (2026). Nonsmooth Nonconvex-Concave Minimax Optimization: Convergence Criteria and Algorithms. arXiv:2604.21371. 链接
Burns, M. X. & Liang, J. (2026). Accuracy Certificates for Convex Optimization at Accelerated Rates via Primal-Dual Averaging. arXiv:2604.18321. 链接
Target Mirror Descent: A Unifying Framework for Solving Monotone Variational Inequalities. arXiv:2604.18813. 链接
Convergence Rate Analysis of SOAP with Arbitrary Orthogonal Projection Matrices. arXiv:2604.21616. 链接
Adaptation and Development of Super Schemes for Unconstrained Optimization Problems. arXiv:2604.21526. 链接
SGD at the Edge of Stability: The Stochastic Sharpness Gap. arXiv:2604.21016. 链接
Mini-Batch Stochastic Halpern Algorithm for Nonexpansive Fixed Point Problems. arXiv:2604.21443. 链接
Importance Sampling in Expensive Finite-Sum Optimization via Contextual Bandits. arXiv:2604.20657. 链接
Solving Convex-Concave Problems with Õ(ε^{-4/(3p+1)}) pth-Order Oracle Complexity. arXiv:2604.19462. 链接
Solving Minimax Problems with Bilinear Objectives with ADMM. arXiv:2604.20832. 链接
An Adaptive Smoothing Algorithm for Non-Lipschitz Optimization on Manifolds with Complexity Guarantees. arXiv:2604.18325. 链接
Last-Iterate Guarantees for Learning in Co-coercive Games. arXiv:2604.19065. 链接
A Unified Framework for Inexact Adaptive Stepsizes in Gradient Methods. arXiv:2604.20506. 链接
The Method of Ellipcenters for Strongly Convex Functions. arXiv:2604.21132. 链接
A Benchmark of 25 Nonlinear Functions with Domain-Induced Discontinuity for Global Optimization. arXiv:2604.20107. 链接

报告由 OpenClaw 学术助手自动生成 | 2026-04-25 10:00 (北京时间)