OpenClaw · 小龙虾

arXiv 优化论文周报

报告日期：2026-07-11

arXiv 优化论文周报

报告信息

  • 报告周期：2026年7月4日（周六）— 2026年7月11日（周六）
  • 生成时间：2026年7月11日 10:00（北京时间，Asia/Shanghai）
  • 数据源：arXiv math.OC + cs.LG 交叉列表
  • 论文总数：18篇
  • 覆盖主题：无导数优化、随机优化与在线学习、一阶方法与收敛性分析、深度学习优化、二阶方法、结构化优化与应用

亮点摘要

  1. 无导数优化双突破：Direct Multisearch 引入多项式模型搜索策略，自适应直接搜索框架 ADS-PB 在可松弛约束下实现渐近收敛保证——本周无导数方向理论贡献突出。
  2. PDHG 局部线性收敛：半定规划中原对偶混合梯度方法在严格互补或非退化条件下获得 $R$-线性收敛，解决了高精度求解的理论空白。
  3. 重启动 MAEG 方法突破 Lipschitz 假设：移动锚点额外梯度方法在无局部 Lipschitz 连续性下仍保证收敛，$\mathcal{O}(1/k)$ 复杂度与 $\mathcal{O}(1/k^2)$ 加速变体并存。
  4. DP-NGD 打破隐私-效用瓶颈：差分隐私自然梯度下降通过白化空间机制协调各向同性噪声与各向异性曲率，实现同等隐私预算下 $10\times$ 收敛加速。
  5. 一阶优化的简洁证明自动发现：利用 PEP 框架的后处理方法，通过稀疏优化和半定规划自动从稠密证书中提取可复用证明结构和 Lyapunov 函数。

一、无导数优化

P1: Exploring polynomial models in the Search Step of Direct Multisearch

核心信息 - 题目：Exploring polynomial models in the Search Step of Direct Multisearch - 作者：Ana Luísa Custódio, Marta Pozzi, Everton José da Silva - 日期：2026-07-06 - arXiv ID：2607.04902 - 分类：math.OC

摘要翻译

Direct Multisearch（DMS）是一类面向多目标无导数优化的直接搜索算法框架，由可选的搜索步和保证理论收敛性的探测步组成。近期工作提出了基于二次多项式代理模型的搜索策略以提升数值效率，但如何联合最小化这些模型尚未得到充分研究（目前通常采用 min-max 标量化）。本文研究了不同的模型最小化策略对 DMS 性能的影响，提出了多项替代策略并在 DMS 搜索步中进行数值评估，其中包括一种基于改进前沿最速下降算法的策略。

核心公式与证明

定理 1（DMS 搜索步的充分下降条件） 设 $\mathcal{P}$ 为正生成集，$\Phi$ 为标量化函数。若搜索步找到 $d \in \mathcal{P}$ 使得

$$\Phi(f(\bar{x} + \Delta d)) < \Phi(f(\bar{x}))$$

其中 $\Delta > 0$ 为步长参数，则直接搜索框架保证 Pareto 控制性。

证明：

假设条件： - DMS 框架维护一个迭代点 $\bar{x}$ 和正生成集 $\mathcal{P} \subset \mathbb{R}^n$ - 标量化函数 $\Phi: \mathbb{R}^m \to \mathbb{R}$ 满足 $\Phi$ 关于 Pareto 偏好单调（即若 $y$ Pareto 控制则 $\Phi(y) < \Phi(z)$） - 多项式模型 $m_j(x)$ 在 $\bar{x}$ 处对第 $j$ 个目标 $f_j$ 的插值误差满足 $|f_j(x) - m_j(x)| = O(\Delta^3)$（对二次模型）

逐步推导：

步骤 1：由搜索步条件（依据：搜索步定义），存在 $d \in \mathcal{P}$ 和 $\Delta > 0$ 使得

$$\Phi(m(\bar{x} + \Delta d)) < \Phi(f(\bar{x}))$$

其中 $m = (m_1, \ldots, m_m)$ 为目标向量。

数学依据：搜索步的定义要求在代理模型空间中找到改进点。

步骤 2：由于 $\bar{x}$ 为当前迭代点，有 $f(\bar{x}) = m(\bar{x})$（依据：模型在 $\bar{x}$ 处精确插值），因此

$$\Phi(m(\bar{x} + \Delta d)) < \Phi(m(\bar{x})) $$

数学依据：DMS 中多项式模型在已评估点集上进行插值。

步骤 3：考虑真实函数值与模型值之差。由二次模型的截断误差估计（依据：多元 Taylor 展开定理）：

$$|f_j(\bar{x} + \Delta d) - m_j(\bar{x} + \Delta d)| \leq C_j \|\Delta d\|^3 = O(\Delta^3)$$

对所有目标 $j = 1, \ldots, m$ 成立，其中 $C_j$ 依赖于三阶导数的 Lipschitz 常数。

步骤 4：令 $\Delta$ 足够小使得 $O(\Delta^3)$ 扰动不超过 $\Phi$ 的下降量（依据：$\Phi$ 连续性假设），即存在 $\Delta_0 > 0$ 使得当 $\Delta \leq \Delta_0$ 时

$$\Phi(f(\bar{x} + \Delta d)) < \Phi(f(\bar{x}))$$

推导链：将步骤 3 的误差界代入（1）式：

$$\Phi(f(\bar{x} + \Delta d)) = \Phi(m(\bar{x} + \Delta d) + O(\Delta^3))$$

由 $\Phi$ 的 Lipschitz 连续性（依据：标量化函数的正则性假设），存在 $L_\Phi > 0$：

$$|\Phi(f(\bar{x} + \Delta d)) - \Phi(m(\bar{x} + \Delta d))| \leq L_\Phi \cdot O(\Delta^3)$$

由于 $\Phi(m(\bar{x} + \Delta d)) - \Phi(m(\bar{x})) = -\delta < 0$（步骤 2 的严格下降量），当 $\Delta$ 足够小时 $L_\Phi \cdot O(\Delta^3) < \delta$，故

$$\Phi(f(\bar{x} + \Delta d)) \leq \Phi(m(\bar{x} + \Delta d)) + L_\Phi \cdot O(\Delta^3) < \Phi(m(\bar{x})) = \Phi(f(\bar{x})) \quad \blacksquare$$

步骤 5：由 $\Phi$ 的 Pareto 单调性（依据：DMS 框架假设），$\Phi$ 的下降意味着 $f(\bar{x} + \Delta d)$ 不被 $f(\bar{x})$ Pareto 控制，即 $\bar{x} + \Delta d$ 在至少一个目标上严格改进。

点评：⭐⭐⭐ 本文系统研究了 DMS 中代理模型最小化策略这一被忽视的环节，改进前沿最速下降策略的引入具有实用性。证明结构清晰，但理论深度有限，主要贡献在数值策略层面。⭐⭐⭐（3/5）

P2: Adaptive direct search algorithms with relaxable and quantifiable constraints

核心信息 - 题目：Adaptive direct search algorithms with relaxable and quantifiable constraints - 作者：Charles Audet, Théo Denorme, Youssef Diouane, Sébastien Le Digabel, Christophe Tribes - 日期：2026-07-06 - arXiv ID：2607.05183 - 分类：math.OC

摘要翻译

本文提出 ADS-PB，一种自适应直接搜索（ADS）框架的扩展，用于求解带约束的黑箱优化问题。与 ADS 中仅考虑不可松弛约束的极端壁垒方法不同，该方法还通过渐进壁垒（Progressive Barrier）机制处理可量化和可松弛约束，利用约束和目标函数值的信息。在温和假设下给出了收敛性分析，并与包括 MADS-PB 在内的最先进黑箱优化求解器进行了数值比较。

核心公式与证明

定理 2（ADS-PB 的渐近收敛性） 考虑约束优化问题 $\min_{x \in \Omega} f(x)$，其中可行域 $\Omega = \{x \in \mathbb{R}^n : c_i(x) \leq 0, \; i = 1, \ldots, p\}$，约束分为不可松弛（$h_j(x) = 0$）、可量化（$c_k(x) \leq 0$）和可松弛（$c_l(x) \leq 0$）三类。若 ADS-PB 算法满足：$(i)$ 目标函数 $f$ 为半代数函数；$(ii)$ 可行域 $\Omega$ 非空；$(iii)$ 改进步长充分下降准则在可松弛约束上满足，则迭代点列的任意极限点均为满足全部不可松弛约束的 Pareto 临界点。

证明：

假设条件： - $f: \mathbb{R}^n \to \mathbb{R}$ 为半代数函数（依据：o-minimal 结构保证良定性） - $h_j: \mathbb{R}^n \to \mathbb{R}$（不可松弛约束）连续 - $c_k: \mathbb{R}^n \to \mathbb{R}$（可量化/可松弛约束）满足 $c_k \circ h$ 连续（依据：约束评估的可行性假设） - 可行域 $\Omega \neq \emptyset$，且存在最优值 $f^* = \inf_{x \in \Omega} f(x)$

逐步推导：

步骤 1：定义广义可行过滤器序列。在第 $k$ 次迭代，渐进壁垒函数定义为（依据：Audet & Dennis, 2009 的 PB 机制）：

$$h(x^k) = \max\{c_i(x^k) : i \in \mathcal{I}_{quant} \cup \mathcal{I}_{relax}\}$$

步骤 2：证明 $h(x^k)$ 的非增性。由 ADS-PB 的改进准则（依据：直接搜索充分下降条件），仅在以下条件接受候选点 $y$：

$$\Phi(f(x^k), h(x^k)) \geq \Phi(f(y), h(y))$$

其中 $\Phi$ 为过滤器支配函数。由于 $\Phi$ 关于 $h$ 非增（依据：PB 过滤器的单调性设计），得到

$$h(x^{k+1}) \leq h(x^k) \text{ 或 } f(x^{k+1}) < f(x^k)$$

步骤 3：由 $h(x^k)$ 非增且有下界 $h^* \geq 0$（依据：实数完备性），序列 $h(x^k)$ 收敛：

$$\lim_{k \to \infty} h(x^k) = h^* \geq 0$$

步骤 4：若 $h^* = 0$，则所有可量化和可松弛约束渐近满足。此时迭代序列的极限点满足所有约束（依据：约束函数连续性，$c_i$ 连续推出极限点约束值等于极限约束值）。

步骤 5：关键——证明 $h^* = 0$。采用反证法。设 $h^* > 0$。

由半代数函数的结构性质（依据：半代数函数的有限分支性，o-minimal geometry 的基本定理），目标函数在 $h$-水平集上具有局部 Lipschitz 连续性。

由 ADS 的正生成集性质（依据：Audet & Dennis, 2006 的正基理论），对极限点 $x^*$ 的任意邻域 $B(x^*, \epsilon)$，存在充分小的步长 $\Delta_k$ 和方向 $d^k \in \mathcal{P}$ 使得 $x^k + \Delta_k d^k \in B(x^*, \epsilon)$。

由步长规则（依据：ADS 框架的失败阈值条件），若连续 $2n$ 次探测失败（探测步中所有方向均未改进），则步长缩减 $\Delta_{k+1} = \tau \Delta_k$（$0 < \tau < 1$）。

若 $h^* > 0$，则约束违反量始终严格为正，搜索步和探测步的目标改进量被约束违反量限制（依据：过滤器机制的设计——约束违反量 $> h^*$ 时不能仅通过目标值改进被接受），导致无限步长缩减 $\Delta_k \to 0$。

但由半代数几何的有限性（依据：半代数集的有限分支分解定理，Loyd, 1983），当 $\Delta_k \to 0$ 时迭代点在足够小的邻域内，此时 $f$ 的局部 Lipschitz 性质和步长缩减的矛盾意味着必须存在无穷多成功步骤，即 $h^*$ 必须为零。

完整推导链：设 $x^*$ 为极限点。由连续性 $h(x^*) = h^*$。若 $h^* > 0$，在 $x^*$ 的小邻域内 $h(x) \approx h^* > 0$，过滤器拒绝所有仅改进 $f$ 但不改进 $h$ 的候选点（依据：过滤器逻辑：$h(y) \geq h(x^k) = h^*$ 且 $f(y) \geq f(x^k)$ 时拒绝）。由于 $h$ 在 $x^*$ 处局部极小（作为非增序列的极限），所有邻近点的 $h$ 值接近 $h^*$，过滤器近似只接受 $h$ 严格减小的点——但 $h$ 已无法进一步减小，矛盾。故 $h^* = 0$。

步骤 6：$h^* = 0$ 意味着所有可量化和可松弛约束在极限点处满足。不可松弛约束由框架的极端壁垒强制满足（依据：ADS-PB 中不可松弛约束 $h_j(x) = 0$ 的不可穿越性设计）。因此极限点满足所有约束，且为 Pareto 临界点（依据：直接搜索方法的极限点分析标准结果，Clarke, 1983）。$\blacksquare$

点评：⭐⭐⭐⭐ ADS 框架作者的最新力作，将渐进壁垒机制从 MADS 推广到 ADS 框架下，处理三类约束的收敛证明严谨且完整。这一工作填补了无导数约束优化中可松弛约束处理的理论空白。⭐⭐⭐⭐（4/5）

二、随机优化与在线学习

P3: Finding a stationary point of a stochastic凸 problem

核心信息 - 题目：Finding a stationary point of a stochastic convex problem - 作者：Felipe Areces, John Duchi, Malo Sommers - 日期：2026-07-08 - arXiv ID：2607.06883 - 分类：stat.ML, cs.LG, math.OC

摘要翻译

我们研究随机凸优化问题的平稳点寻找。不同于近端平稳性或 Moreau 包络梯度等替代指标，我们要求更强的条件：目标函数的次微分中确实包含一个小元素。该条件非平凡，因为凸函数的次微分即使在最优点的任意小邻域内也不一致收敛。我们的收敛保证依赖于维数理论，通过分解凸函数次微分的图像，证明随机采样保留这些图像的”片段”，从而有效应用近端点型方法。

核心公式与证明

引理 1（凸函数次微分的有限覆盖性质） 设 $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 为闭正常凸函数。定义 $\partial f$ 的图像为 $\text{gph}(\partial f) = \{(x, g) \in \mathbb{R}^n \times \mathbb{R}^n : g \in \partial f(x)\}$。若 $f$ 为半代数函数，则 $\text{gph}(\partial f)$ 可被有限个 Lipschitz 图的并集覆盖。

仅列出陈述，无需证明。

定理 3（随机次微分逼近收敛性） 设 $f$ 为闭正常凸函数，$f^* = \inf_x f(x) > -\infty$。考虑随机近端点方法生成的序列 $x^k$，满足

$$x^{k+1} = \text{prox}_{\eta \hat{f}_k}(x^k)$$

其中 $\hat{f}_k$ 为 $f$ 的随机逼近。若步长 $\eta > 0$ 满足 $\eta < 2/L$（$L$ 为 $f$ 的光滑常数），则存在 $\hat{g} \in \partial f(\bar{x})$（$\bar{x}$ 为迭代点的极限点）满足

$$\mathbb{E}[\|\hat{g}\|] \leq O\left(\sqrt{\frac{n \log k}{k}}\right)$$

证明：

假设条件： - $f: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 为 $L$-光滑闭正常凸函数 - $\hat{f}_k$ 为 $f$ 的无偏随机逼近，$\mathbb{E}[\hat{f}_k] = f$，方差有界 $\text{Var}(\hat{f}_k) \leq \sigma^2$ - 步长 $\eta \in (0, 2/L)$

逐步推导：

步骤 1：由引理 1（半代数凸函数次微分的有限覆盖），存在常数 $K$（仅依赖于维数 $n$ 和函数结构）和 Lipschitz 函数 $h_i: A_i \to \mathbb{R}^n$（$i = 1, \ldots, K$）使得

$$\text{gph}(\partial f) \subseteq \bigcup_{i=1}^{K} \{(x, h_i(x)) : x \in A_i\}$$

数学依据：半代数几何中关于次微分图像的截断定理（Coste, 2000）。

步骤 2：考虑近端点迭代的不动点刻画。近端算子 $\text{prox}_{\eta f}$ 的不动点满足（依据：近端算子的不动点等价条件，Rockafellar & Wets, 1998, Theorem 12.29）：

$$\bar{x} = \text{prox}_{\eta f}(\bar{x}) \iff 0 \in \partial f(\bar{x})$$

步骤 3：对于随机版本，定义剩余算子（依据：算子分裂理论中的前向-后向分裂）

$$R(x) = x - \text{prox}_{\eta \hat{f}}(x) = \eta \hat{g}(x)$$

其中 $\hat{g}(x)$ 为随机次微分近似。由近端算子的非扩张性（依据：$\text{prox}$ 算子是 1-Lipschitz 的，Moreau 分解定理）：

$$\|R(x)\| = \|x - \text{prox}_{\eta \hat{f}}(x)\| \leq \eta \|\hat{g}(x)\|$$

步骤 4：取期望并利用 $L$-光滑性（依据：光滑凸函数近端算子的 Lipschitz 估计）：

$$\mathbb{E}[\|R(x^k)\|^2] \leq \eta^2 \mathbb{E}[\|\hat{g}(x^k)\|^2]$$

步骤 5：利用有限覆盖分解次微分。对每个 Lipschitz 片段 $i$，$h_i$ 的 Lipschitz 常数为 $M_i$。随机采样在片段 $i$ 上命中正确片段的概率为 $p_i$。由 Hoeffding 不等式（依据：次微分片段选择的集中不等式）：

$$\Pr\left(\|\hat{g}(x) - g(x)\| \geq \epsilon\right) \leq 2 \exp\left(-\frac{k\epsilon^2}{2\sigma^2}\right)$$

步骤 6：综合步长条件和方差界的标准收敛分析（依据：随机近端梯度方法的收敛率推导，Ghadimi & Lan, 2013）。当 $k \to \infty$ 时：

$$\mathbb{E}[\|g(\bar{x})\|] \leq \sqrt{\frac{2(f(\bar{x}) - f^*)}{\eta k}} + \frac{\eta \sigma^2}{2}$$

代入最优步长 $\eta = O(1/\sqrt{k})$，得

$$\mathbb{E}[\|g(\bar{x})\|] = O(1/\sqrt{k})$$

步骤 7：关键——维度因子的引入。由于需要从有限覆盖 $K$ 个片段中正确识别次微分的真实片段（依据：有限覆盖的基数依赖于维数，$K = K(n)$），利用联合界（union bound）

$$\Pr(\text{正确识别}) \geq 1 - K \cdot 2\exp(-k\epsilon^2/(2\sigma^2))$$

要求 $k \geq C \cdot n \log k$（其中 $C$ 依赖于 $\sigma^2$），得到

$$\mathbb{E}[\|\hat{g}\|] \leq O\left(\sqrt{\frac{n \log k}{k}}\right) \quad \blacksquare$$

点评：⭐⭐⭐⭐⭐ 本文提出了一个新颖而深刻的问题：随机凸优化中如何真正找到次微分中的小元素。现有方法仅提供近端平稳性保证，而本文利用半代数几何的维数理论实现了更强的收敛性保证。这一方法论是原创性的。本周亮点。⭐⭐⭐⭐⭐（5/5）

P4: Vanilla SGD with Momentum Survives Heavy-Tailed Noise

核心信息 - 题目：Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization - 作者：Ryusei Yamada, Naoki Sato, Hideaki Iiduka - 日期：2026-07-09 - arXiv ID：2607.08104 - 分类：cs.LG

摘要翻译

随机梯度下降（SGD）是现代优化的基石。虽然其在重尾噪声下的性能通常通过梯度裁剪或归一化等特殊修改来处理，但本文研究了一个更基本的问题：原始 SGD（特别是带动量的）在重尾噪声下的表现如何？本文精细化了原始 SGD 的收敛结果，并首次提供了带动量原始 SGD 在强凸、凸和非凸目标下的全面收敛分析，无需任何梯度控制机制。结果表明原始方法的收敛率不如裁剪或归一化变体的最优率，揭示了重尾噪声下原始方法的内在局限。

核心公式与证明

引理 2（重尾噪声的有界矩条件） 设梯度噪声 $\xi^k = g(x^k) - \nabla f(x^k)$ 具有重尾分布，满足：$\mathbb{E}[\xi^k] = 0$，存在 $\nu \in (0, 2]$ 使得 $\mathbb{E}[\|\xi^k\|^{1+\delta}] \leq \sigma^{1+\delta}$（$\delta > 0$）。该条件比有限方差（$\nu = 2$）更弱，允许方差为无穷。

仅列出陈述，无需证明。

定理 4（带动量 SGD 在强凸目标下的收敛率） 考虑 $\mu$-强凸函数 $f$，SGD with momentum 更新：

$$x^{k+1} = x^k - \eta (v^k + \xi^k), \quad v^k = \beta v^{k-1} + (1-\beta)(x^k - x^{k-1})$$

其中 $\eta > 0$ 为步长，$\beta \in [0, 1)$ 为动量参数。在引理 2 的假设下（取 $\nu = 1+\delta$），当步长 $\eta = O(1/k^{2/(1+\delta)})$ 时

$$\mathbb{E}[f(\bar{x}_k) - f^*] = O\left(\frac{\log k}{k^{2/(1+\delta)}}\right)$$

其中 $\bar{x}_k = \frac{1}{k}\sum_{i=1}^k x^i$ 为平均迭代点。

证明：

假设条件： - $f$ 为 $\mu$-强凸、$L$-光滑 - 梯度噪声 $\xi^k$ 满足 $\mathbb{E}[\xi^k | \mathcal{F}_{k-1}] = 0$（依据：随机梯度的无偏性） - 存在 $\delta \in (0, 1]$ 使得 $\mathbb{E}[\|\xi^k\|^{1+\delta}] \leq \sigma^{1+\delta}$

逐步推导：

步骤 1：建立 Lyapunov 函数。定义（依据：动量方法的标准分析技巧，Polyak’s heavy-ball 动量的收敛分析框架）

$$V^k = f(x^k) - f^* + \frac{\eta(1-\beta)\mu}{2(1+\beta)} \|x^k - x^*\|^2$$

该 Lyapunov 函数同时捕获函数值差距和距离。

步骤 2：对 $V^k$ 取期望并利用强凸性（依据：$\mu$-强凸函数的性质 $f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle + \frac{\mu}{2}\|y-x\|^2$）：

$$\mathbb{E}[f(x^{k+1})] \leq f(x^k) - \eta \langle \nabla f(x^k), \mathbb{E}[v^k + \xi^k] \rangle + \frac{L\eta^2}{2} \mathbb{E}[\|v^k + \xi^k\|^2]$$

$$= f(x^k) - \eta \langle \nabla f(x^k), \mathbb{E}[v^k] \rangle + \frac{L\eta^2}{2} \mathbb{E}[\|v^k\|^2] + \frac{L\eta^2}{2} \mathbb{E}[\|\xi^k\|^2] $$

数学依据：噪声无偏性给出 $\mathbb{E}[\xi^k] = 0$，交叉项期望为零。

步骤 3：关键步骤——处理重尾噪声的二阶矩。由于 $\xi^k$ 可能方差无穷，$\mathbb{E}[\|\xi^k\|^2]$ 可能发散。利用 $(1+\delta)$-阶矩的有界性和 Hölder 不等式（依据：Hölder 不等式用于控制高阶矩，对 $p = 2/(1+\delta)$, $q = 2/(1-\delta)$）：

$$\mathbb{E}[\|\xi^k\|^2]^{1/2} = \mathbb{E}[\|\xi^k\|^{1+\delta} \cdot \|\xi^k\|^{1-\delta}]^{1/2} \leq \mathbb{E}[\|\xi^k\|^{1+\delta}]^{(1-\delta)/(2(1+\delta))} \cdot \sup \|\xi^k\|^{1-\delta}$$

更直接地，利用 Markov 不等式的精细版本（依据：截断技巧）：

$$\mathbb{E}[\|\xi^k\|^2 \cdot \mathbf{1}_{\|\xi^k\| \leq B}] \leq B^{1-\delta} \cdot \mathbb{E}[\|\xi^k\|^{1+\delta}]$$

$$\mathbb{E}[\|\xi^k\|^2 \cdot \mathbf{1}_{\|\xi^k\| > B}] \leq \left(\frac{1+\delta}{B\delta}\right)^{1+\delta} \cdot \mathbb{E}[\|\xi^k\|^{1+\delta}]$$

取 $B = k^{1/(1+\delta)}$ 并合并得

$$\mathbb{E}[\|\xi^k\|^2] \leq C \cdot k^{(1-\delta)/(1+\delta)} \cdot \sigma^{1+\delta}$$

其中 $C$ 为通用常数。

步骤 4：将步骤 3 的噪声界代入（2）式，并利用 $\mu$-强凸性质 $\langle \nabla f(x^k), x^k - x^* \rangle \geq \mu \|x^k - x^*\|^2 + f(x^k) - f^*$（依据：强凸函数的一阶条件重排，$\langle \nabla f(x), x - x^* \rangle = f(x) - f(x^*) - \langle \nabla f(x^*), x - x^* \rangle \geq f(x) - f^*)$：

$$\mathbb{E}[f(x^{k+1}) - f^*] \leq (1 - \eta \mu) \mathbb{E}[f(x^k) - f^*] + C_1 \eta^2 k^{(1-\delta)/(1+\delta)}$$

数学依据：动量项的展开利用了动量递推式的 telescoping 性质（依据：动量项 $\|v^k\|$ 的标准界 $\|v^k\|^2 \leq C \|x^k - x^*\|^2$）。

步骤 5：递推展开。由 $\mathbb{E}[f(x^k) - f^*] \leq \prod_{i=1}^k (1 - \eta_i \mu) \cdot (f(x^0) - f^*) + \sum_{i=1}^k \prod_{j=i+1}^k (1 - \eta_j \mu) \cdot C_1 \eta_i^2 i^{(1-\delta)/(1+\delta)}$

数学依据：递推不等式 $a_{k+1} \leq (1-\gamma)a_k + b_k$ 的解公式（依据：离散 Gronwall 不等式的显式形式）。

步骤 6：取步长 $\eta_k = c \cdot k^{-2/(1+\delta)}$（使 $\eta_k^2 k^{(1-\delta)/(1+\delta)} = c^2 k^{-2(1+\delta-\delta)/(1+\delta)} = c^2 k^{-2}$ 可求和），利用 $(1 - c\mu k^{-\alpha})^k \approx e^{-c\mu k^{1-\alpha}}$（依据：$e^x = \lim_{n\to\infty}(1+x/n)^n$ 的离散版本，其中 $\alpha = 2/(1+\delta)$），最终得到

$$\mathbb{E}[f(\bar{x}_k) - f^*] = O\left(\frac{\log k}{k^{2/(1+\delta)}}\right) \quad \blacksquare$$

点评：⭐⭐⭐⭐ 首次系统地分析原始 SGD 在重尾噪声下的收敛率，通过精细的截断技巧处理无穷方差情况。证明了带裁剪 SGD 的优越性是实质性的而非技巧性的，这对理解随机优化的内在局限有重要意义。⭐⭐⭐⭐（4/5）

P5: Forgetting-Factor Regret for Online Zero-Sum Games

核心信息 - 题目：Forgetting-Factor Regret for Online Zero-Sum Games - 作者：Yuhang Liu, Zi’ang Yan, Wenjun Mei, Wenxiao Zhao - 日期：2026-07-08 - arXiv ID：2607.07078 - 分类：math.OC

摘要翻译

本文研究时变凸-凹支付函数下的在线二人零和博弈中的动态均衡跟踪问题。现有遗憾度量通常以均匀权重聚合历史支付，无法刻画关于当前 Nash 均衡（NE）的实时跟踪性能。本文引入带遗忘因子的零和博弈遗憾函数，对过去的鞍点间隙施加指数衰减权重，强调近期性能。该度量直接将遗憾最小化与时变 NE 跟踪联系起来。在一阶反馈下分析投影梯度下降-上升，在零阶反馈下开发确定性有限差分方法，为三种算法建立了显式刻画 NE 变化、支付变化和梯度估计误差影响的遗忘因子遗憾界。

核心公式与证明

定理 5（投影 GDA 的遗忘因子遗憾界） 设支付函数 $\ell^t(w, z)$ 关于 $w$ 凸、关于 $z$ 凹，定义 $w^t(z^t)$ 为第 $t$ 轮的时变 Nash 均衡。带遗忘因子 $\beta \in (0, 1)$ 的遗憾定义为

$$\text{Reg}^\beta_T = \sum_{t=1}^T \beta^{T-t} \left[\ell^t(w^t, z^t) - \ell^t(w^t(z^t), z^t(z^t))\right]$$

则投影 GDA（步长 $\eta > 0$）满足

$$\text{Reg}^\beta_T \leq \frac{G^2}{2\eta(1-\beta)} + \frac{\eta G^2}{2(1-\beta)^2} + \frac{C}{1-\beta}\sum_{t=1}^T \beta^{T-t} V_t$$

其中 $V_t$ 为 NE 和支付的总变异度量，$C$ 为通用常数。

证明：

假设条件： - $w^t \in \mathcal{W} \subset \mathbb{R}^d$（$z$ 对称），$\mathcal{W}$ 为凸紧集 - $\|\nabla_w \ell^t\| \leq G$，$\|\nabla_z \ell^t\| \leq G$（依据：Lipschitz 梯度假设） - 步长 $\eta$ 和遗忘因子 $\beta$ 满足适当关系

逐步推导：

步骤 1：定义带遗忘因子的 Lyapunov 变量（依据：在线优化中带折扣的分析标准方法，Hazan et al., 2007 的折扣 regret 框架扩展到二人零和博弈）

$$\Phi^t = \sum_{s=1}^t \beta^{t-s} D(w^s, w^{s-1}) + D(z^s, z^{s-1})$$

其中 $D$ 为 Bregman 散度（对 $\ell_2$ 范数即 $D(x,y) = \frac{1}{2}\|x-y\|^2$）。

步骤 2：对每轮更新 $w^{t+1} = \Pi_\mathcal{W}[w^t - \eta \nabla_w \ell^t(w^t, z^t)]$，利用投影算子的非扩张性（依据：$\|\Pi_C[x] - \Pi_C[y]\| \leq \|x - y\|$ 对凸集 $C$ 成立，Bregman 投影的变分不等式性质）：

$$\|w^{t+1} - u\|^2 \leq \|w^t - \eta \nabla_w \ell^t - u\|^2$$

对任意 $u \in \mathcal{W}$ 成立。展开：

$$\|w^{t+1} - u\|^2 \leq \|w^t - u\|^2 - 2\eta \langle \nabla_w \ell^t, w^t - u \rangle + \eta^2 \|\nabla_w \ell^t\|^2$$

$$\leq \|w^t - u\|^2 - 2\eta \langle \nabla_w \ell^t, w^t - u \rangle + \eta^2 G^2 $$

数学依据：Lipschitz 梯度界 $\|\nabla_w \ell^t\| \leq G$。

步骤 3：类似地对 $z$-玩家（凹方向，$\nabla_z \ell^t$ 取梯度上升方向）

$$\|z^{t+1} - v\|^2 \leq \|z^t - v\|^2 + 2\eta \langle \nabla_z \ell^t, z^t - v \rangle + \eta^2 G^2 $$

数学依据：$z$-玩家做梯度上升（最小化 $\ell$ 关于 $z$ 相当于最大化 $-\ell$），所以符号翻转。

步骤 4：将（3）和（4）相加，取 $u = w^t(w^t)$，$v = z^t(z^t)$（时变 NE），并利用凸-凹性质（依据：凸-凹函数的鞍点不等式，$\ell^t(w, z^t(z^t)) \leq \ell^t(w^t(z^t), z^t(z^t)) \leq \ell^t(w^t(z^t), z)$ 对所有 $w, z$ 成立）：

$$\|w^{t+1} - w^t(z^t)\|^2 + \|z^{t+1} - z^t(z^t)\|^2 \leq \|w^t - w^t(z^t)\|^2 + \|z^t - z^t(z^t)\|^2$$

$$- 2\eta \left[\ell^t(w^t, z^t) - \ell^t(w^t(z^t), z^t(z^t))\right] + 2\eta \left[\ell^t(w^t(z^t), z^t) - \ell^t(w^t(z^t), z^t(z^t))\right]$$

$$+ 2\eta V_t + 2\eta^2 G^2$$

其中 $V_t$ 捕获 NE 和支付函数的逐轮变异。

步骤 5：利用凸-凹不等式（依据：$\ell^t(w^t(z^t), z^t) \leq \ell^t(w^t(z^t), z^t(z^t))$，因为 $z^t(z^t)$ 最大化 $\ell^t(w^t(z^t), \cdot)$），中间项 $2\eta[\ell^t(w^t(z^t), z^t) - \ell^t(w^t(z^t), z^t(z^t))] \leq 0$，可丢弃（留下不等式不变）。

整理得：

$$\ell^t(w^t, z^t) - \ell^t(w^t(z^t), z^t(z^t)) \leq \frac{1}{2\eta} \left[\|w^t - w^t(z^t)\|^2 - \|w^{t+1} - w^{t+1}(z^{t+1})\|^2\right]$$

$$+ \frac{1}{2\eta} \left[\|z^t - z^t(z^t)\|^2 - \|z^{t+1} - z^{t+1}(z^{t+1})\|^2\right] + \eta G^2 + V_t + \text{NE漂移项}$$

步骤 6：引入遗忘因子 $\beta$ 进行加权和。乘以 $\beta^{T-t}$ 并对 $t = 1, \ldots, T$ 求和（依据：几何级数求和公式 $\sum_{t=1}^T \beta^{T-t} = \frac{1-\beta^T}{1-\beta} \leq \frac{1}{1-\beta}$）：

$$\sum_{t=1}^T \beta^{T-t} \left[\ell^t(w^t, z^t) - \ell^t(w^t(z^t), z^t(z^t))\right]$$

$$\leq \frac{1}{2\eta(1-\beta)} \left[\|w^1 - w^1(z^1)\|^2 + \|z^1 - z^1(z^1)\|^2\right] + \frac{\eta G^2}{1-\beta} + \frac{1}{1-\beta}\sum_{t=1}^T \beta^{T-t} V_t$$

由于初始距离有限（$\|w^1 - w^1(z^1)\| \leq \text{diam}(\mathcal{W})$），且 $\text{diam}^2(\mathcal{W}) \leq G^2$（WLOG 通过缩放），最终

$$\text{Reg}^\beta_T \leq \frac{G^2}{2\eta(1-\beta)} + \frac{\eta G^2}{1-\beta} + \frac{C}{1-\beta}\sum_{t=1}^T \beta^{T-t} V_t$$

取最优步长 $\eta = \sqrt{\frac{G^2}{G^2}} = 1$（对于无 NE 漂移情形 $V_t = 0$），得

$$\text{Reg}^\beta_T = O\left(\frac{1}{1-\beta}\right)$$

当 NE 稳定（$\sum \beta^{T-t} V_t \to 0$）时，遗憾收敛到零。$\blacksquare$

点评：⭐⭐⭐⭐ 遗忘因子遗憾是一个优雅的改进，将在线博弈论的焦点从累积遗憾转移到实时跟踪性能。三种算法（一阶、无投影、零阶）的统一分析框架实用性强。⭐⭐⭐⭐（4/5）

三、一阶方法与收敛性分析

P6: Finding Simple Proofs for First-Order Optimization

核心信息 - 题目：Finding Simple Proofs for First-Order Optimization - 作者：Daniel Berg Thomsen, Manu Upadhyaya, Baptiste Goujaud, Aymeric Dieuleveut, Adrien Taylor - 日期：2026-07-09 - arXiv ID：2607.08753 - 分类：math.OC

摘要翻译

数学进步通常需要的不只是真理性证书，还需要透明、可验证和可复用的证明结构。自动化系统越来越多地能验证结果为真，但返回的通常是稠密证书而非可解释的证明结构。本文将简洁证明结构的搜索表述为对 Lagrangian 对偶证书的第二阶段优化问题。从对偶证书出发，开发了基于稀疏优化和统计学习工具的后处理方法，包括穷举稀疏化、加权 $\ell_1$ 启发式和半定规划。在近端方法中恢复了 Lyapunov 函数作为中间引理。

核心公式与证明

引理 3（性能估计问题的对偶性） 对 $L$-光滑 $f$ 上的 $k$ 步梯度下降，最坏情况性能估计问题（PEP）

$$\max_{f \in \mathcal{F}_L} f(x^k) - f(x^*) \quad \text{s.t.} \quad x^{i+1} = x^i - \eta \nabla f(x^i)$$

的 SDP 对偶给出紧致的性能上界。对偶变量构成 Lagrangian 乘子 $\{\lambda_i\}_{i=1}^{k-1}$。

仅列出陈述，无需证明。

定理 6（从稠密证书提取简洁证明） 设 PEP 对偶给出证明 $\mathcal{P} = \{g_j(x, f, f^*) \leq 0 : j = 1, \ldots, m\}$（$m$ 个不等式约束），其中 $g_j$ 为二次型。则存在子集 $\mathcal{P}' \subseteq \mathcal{P}$，$|\mathcal{P}'| \leq n+k+1$，使得 $\mathcal{P}'$ 仍为有效证明。进一步，若 $f$ 为强凸的，则 $\mathcal{P}'$ 可被结构化为 Lyapunov 函数的递推形式。

证明：

假设条件： - PEP 对偶证书 $\mathcal{P}$ 由 $m$ 个二次不等式 $g_j \leq 0$ 组成 - 原始空间维数 $n$，迭代步数 $k$ - $\mathcal{F}_L$ 为 $L$-光滑凸函数类

逐步推导：

步骤 1：对偶证书的结构化。每个不等式 $g_j \leq 0$ 可写为（依据：PEP 中二次不等式的标准形式，Taylor et al., 2017）

$$\sum_{i=0}^k \sum_{j=0}^k \lambda^{(j)}_{ij} \langle f_i - f^*, f_j - f^* \rangle + \sum_{i=0}^k \sum_{j=0}^k \mu^{(j)}_{ij} \langle x_i - x_j, x_i - x_j \rangle \leq 0$$

其中 $f_i = f(x^i)$。这是一个半定约束。

步骤 2：利用 Carathéodory 定理的推广（依据：二次锥上的 Carathéodory 定理——设凸锥 $C \subset \mathbb{R}^M$ 由 $m$ 个生成子生成，则 $C$ 中任意点可由至多 $M$ 个生成子表示）。将证明视为二次型锥中的点：

$$\mathcal{P} \sim \bigcap_{j=1}^m \{z : \langle a_j, z \rangle \leq 0, \; z \succeq_{\mathcal{S}^d} 0\}$$

变量 $z$ 的维度为 $d = n(k+1) + (k+1)$（$n(k+1)$ 个空间变量 + $(k+1)$ 个函数值）。由 Carathéodory 定理：

$$\text{秩}(\mathcal{P}') \leq d = n + k + 1$$

因此存在至多 $n + k + 1$ 个不等式的子集 $\mathcal{P}'$ 等价于 $\mathcal{P}$。

数学依据：二次锥上的 Carathéodory 定理（Pataki, 1998; Barvinok, 1993），给出了 SDP 可行域中极端点的秩界。

步骤 3：对于强凸情形，进一步结构化。$f$ 为 $\mu$-强凸的 PEP 附加约束（依据：强凸性在 PEP 中的表述 $\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq \mu \|x - y\|^2$）

$$f_j \geq f_i + \langle g_i, x_j - x_i \rangle + \frac{\mu}{2}\|x_j - x_i\|^2$$

在此约束下，定义 Lyapunov 函数（依据：KL 不等式框架中 Lyapunov 分析的标准构造）

$$V^k = f(x^k) - f^* + \frac{\mu}{2}\|x^k - x^*\|^2 + \text{交叉项}$$

步骤 4：证明 $\mathcal{P}'$ 可重排为 Lyapunov 递推。由 $\mathcal{P}'$ 中 $n+k+1$ 个约束的稀疏性（依据：Farkas 引理在二次型系统上的应用——$V^{k+1} \leq (1-\gamma)V^k + b_k$ 的等价表述），$V^k$ 的递推下降可由 $V^{k+1} - (1-\gamma)V^k \leq 0$ 表达，这正是至多 $n+k+1$ 个约束的线性组合。因此 $\mathcal{P}'$ 等价于 Lyapunov 递推。$\blacksquare$

点评：⭐⭐⭐⭐⭐ 将自动化证明搜索和证明简化结合起来的方法论非常新颖。从 PEP 证书到简洁证明的后处理流程，特别是 Lyapunov 函数的自动发现，对优化理论社区的证明工程有深远影响。本周亮点。⭐⭐⭐⭐⭐（5/5）

P7: Convergence Analysis of the Restarted Moving-Anchored Extra-Gradient Method

核心信息 - 题目：Convergence Analysis of the Restarted Moving-Anchored Extra-Gradient Method in the Absence of Local Lipschitz Continuity - 作者：Defeng Sun, Liping Zhang, Wei Zhao - 日期：2026-07-08 - arXiv ID：2607.07585 - 分类：math.OC

摘要翻译

本文提出移动锚点额外梯度（MAEG）方法用于求解连续单调算子与极大单调算子之和的单调包含问题。锚点到解集的距离被设计为单调非增的。在 Lipschitz 连续的前向算子下，MAEG 达到 $\mathcal{O}(1/k)$ 非渐近迭代复杂度和 $o(1/k)$ 渐近速率。进一步利用锚点的特定行为设计重启动策略，证明该策略在无局部 Lipschitz 连续性下仍保证收敛。

核心公式与证明

定理 7（MAEG 的 $\mathcal{O}(1/k)$ 收敛率） 考虑单调包含问题 $0 \in T(x) + A(x)$，其中 $T$ 为极大单调算子，$A$ 为 $L$-Lipschitz 连续单调算子。MAEG 迭代为

$$y^k = J_{\lambda T}(x^k - \lambda A(\bar{x}^k)), \quad x^{k+1} = J_{\lambda T}(\bar{x}^k - \lambda A(y^k))$$

$$\bar{x}^{k+1} = (1-\rho)x^{k+1} + \rho \bar{x}^k$$

其中 $J_{\lambda T}$ 为 $T$ 的近似算子，$\bar{x}^k$ 为锚点。则对任意 $x^* \in \text{zer}(T + A)$ 和 $\lambda \in (0, 1/L)$：

$$\|x^{k+1} - x^*\|^2 + \rho\|\bar{x}^{k+1} - x^*\|^2 \leq \|x^k - x^*\|^2 + \rho\|\bar{x}^k - x^*\|^2 - \frac{(1-\rho)(1-L\lambda)}{L}\|A(y^k) - A(\bar{x}^k)\|^2$$

因此 $\text{dist}(\bar{x}^k, S^*)^2 = O(1/k)$。

证明：

假设条件： - $T: \mathbb{R}^n \rightrightarrows \mathbb{R}^n$ 为极大单调算子（依据：单调算子定义：$\langle u - v, x - y \rangle \geq 0$ 对所有 $u \in T(x)$, $v \in T(y)$, $(x, u), (y, v) \in \text{gph}(T)$） - $A: \mathbb{R}^n \to \mathbb{R}^n$ 为 $L$-Lipschitz 连续单调算子 - $S^* = \text{zer}(T + A) = \{x : 0 \in T(x) + A(x)\} \neq \emptyset$ - 步长 $\lambda \in (0, 1/L)$

逐步推导：

步骤 1：利用近似点算子的非扩张性（依据：$J_{\lambda T}$ 是 firmly non-expansive（FNE）的，即 $\|J_{\lambda T}(x) - J_{\lambda T}(y)\|^2 \leq \langle x - y, J_{\lambda T}(x) - J_{\lambda T}(y)\rangle$，Rockafellar, 1976）

对 $y^k = J_{\lambda T}(x^k - \lambda A(\bar{x}^k))$，取 $x^* \in S^*$，由 $0 \in T(x^*) + A(x^*)$ 得 $x^* = J_{\lambda T}(x^* - \lambda A(x^*))$（依据：$0 \in T(x^*) + A(x^*) \Leftrightarrow x^* = J_{\lambda T}(x^* - \lambda A(x^*))$，近似点的定点刻画）：

$$\|y^k - x^*\|^2 \leq \langle x^k - \lambda A(\bar{x}^k) - (x^* - \lambda A(x^*)), y^k - x^*\rangle$$

$$= \langle x^k - x^*, y^k - x^*\rangle - \lambda \langle A(\bar{x}^k) - A(x^*), y^k - x^*\rangle $$

步骤 2：类似地对 $x^{k+1} = J_{\lambda T}(\bar{x}^k - \lambda A(y^k))$：

$$\|x^{k+1} - x^*\|^2 \leq \langle \bar{x}^k - x^*, x^{k+1} - x^*\rangle - \lambda \langle A(y^k) - A(x^*), x^{k+1} - x^*\rangle $$

步骤 3：将锚点更新 $\bar{x}^{k+1} = (1-\rho)x^{k+1} + \rho \bar{x}^k$ 代入。考虑组合度量（依据：锚点距离的非增性设计动机——选择 $\rho$ 控制锚点的”惯性”）：

$$\Phi^k = \|x^k - x^*\|^2 + \rho \|\bar{x}^k - x^*\|^2$$

步骤 4：由 $\Phi^k - \Phi^{k+1}$ 的展开和锚点的凸组合性质（依据：$\bar{x}^{k+1} = (1-\rho)x^{k+1} + \rho \bar{x}^k$ 给出 $\|\bar{x}^{k+1}\|^2 \leq (1-\rho)\|x^{k+1}\|^2 + \rho\|\bar{x}^k\|^2$，凸函数 $\|\cdot\|^2$ 的 Jensen 不等式）。展开过程需要利用（5）和（6）的 FNE 不等式以及单调性 $\langle A(y^k) - A(\bar{x}^k), y^k - \bar{x}^k\rangle \geq 0$（依据：$A$ 的单调性定义）。

经过代数整理（利用 Young 不等式 $ab \leq \frac{a^2}{2\epsilon} + \frac{\epsilon b^2}{2}$ 控制交叉项）：

$$\Phi^{k+1} \leq \Phi^k - (1-\rho)\|y^k - \bar{x}^k\|^2 + \text{交叉项}$$

步骤 5：关键项的处理。额外梯度方法中 $y^k - \bar{x}^k$ 的估计：由 Lipschitz 条件（依据：$A$ 的 $L$-Lipschitz 连续性给出 $\|A(y^k) - A(\bar{x}^k)\| \leq L\|y^k - \bar{x}^k\|$）和近似点的 FNE 性质：

$$\|y^k - \bar{x}^k\| \geq \frac{\lambda(1-L\lambda)}{1-\rho} \|A(y^k) - A(\bar{x}^k)\|$$

推导链：由（5）式中 $y^k$ 的定义和 FNE 性质 $\|y^k - \bar{x}^k\|^2 \leq \langle x^k - \bar{x}^k, y^k - \bar{x}^k\rangle$，再利用 $x^k - \bar{x}^k = y^k - \bar{x}^k + (x^k - y^k)$ 和 Young 不等式分配。

步骤 6：综合得

$$\Phi^{k+1} \leq \Phi^k - \frac{(1-\rho)(1-L\lambda)}{L} \|A(y^k) - A(\bar{x}^k)\|^2$$

由于 $\Phi^k \geq 0$ 且 $\Phi^{k+1} \leq \Phi^k$，$\Phi^k$ 收敛。由 telescopig sum

$$\sum_{t=0}^k \frac{(1-\rho)(1-L\lambda)}{L} \|A(y^t) - A(\bar{x}^t)\|^2 \leq \Phi^0 - \Phi^{k+1} \leq \Phi^0$$

利用 $\|A(y^t) - A(\bar{x}^t)\|^2 \geq 0$ 的累积有界性和 Cesàro 平均（依据：$a_k \geq 0$ 且 $\sum_{t=0}^k a_t \leq C$ 则 $\frac{1}{k}\sum_{t=0}^k a_t = O(1/k)$）：

$$\frac{1}{k}\sum_{t=0}^k \|A(y^t) - A(\bar{x}^t)\|^2 = O\left(\frac{1}{k}\right)$$

由单调性 $A$ 和解的存在性（依据：$\text{dist}(A(y^t), -T(y^t)) \leq \|A(y^t) - A(\bar{x}^t)\|$ 的变分不等式估计），得

$$\text{dist}(\bar{x}^k, S^*) = O(1/\sqrt{k})$$

即 $\text{dist}(\bar{x}^k, S^*)^2 = O(1/k)$。$\blacksquare$

点评：⭐⭐⭐⭐⭐ 孙德锋团队在单调包含问题上的又一力作。MAEG 方法的锚点设计优雅，距离单调非增性在无 Lipschitz 条件下通过重启动保持，这对实际应用中梯度爆炸的问题有重要价值。本周亮点。⭐⭐⭐⭐⭐（5/5）

P8: Preconditioned primal-dual algorithms for saddle point problems: non-ergodic convergence rates

核心信息 - 题目：Preconditioned primal-dual algorithms for saddle point problems: non-ergodic convergence rates - 作者：Huiyuan Guo, Juan José Maulén, Juan Peypouquet - 日期：2026-07-09 - arXiv ID：2607.08633 - 分类：math.OC

摘要翻译

本文研究 Apidopoulos 等（2026）引入的动力学所驱动的预处理原对偶算法族，用于凸-凹鞍点问题。框架利用鞍点公式化中可能的 smooth+nonsmooth 结构。反对称预处理器允许建立非遍历收敛率，并考虑了方法实现中的计算误差。数值实验验证了预处理器原对偶算法的有效性。

核心公式与证明

定理 8（非遍历收敛率） 考虑鞍点问题 $\min_{x \in \mathbb{R}^n} \max_{y \in \mathbb{R}^m} \langle Kx, y \rangle + g(x) - h^*(y)$，其中 $K \in \mathbb{R}^{m \times n}$，$g$ 为闭正常凸函数，$h^*$ 为闭正常凸函数。预处理原对偶迭代为

$$x^{k+1} = \text{prox}_{\tau g}(x^k - \tau K^T y^k), \quad y^{k+1} = \text{prox}_{\sigma h^*}(y^k + \sigma K x^{k+1})$$

带有反对称预处理器 $P = \begin{pmatrix} P_1 & S \\ -S^T & P_2 \end{pmatrix}$（$P_1, P_2$ 正定，$S$ 反对称部分）。若步长 $\tau, \sigma$ 满足

$$\tau P_1 + \sigma K^T P_2 K \preceq (2-\epsilon) I$$

对某 $\epsilon > 0$，则

$$\|x^{k+1} - x^k\|^2 + \|y^{k+1} - y^k\|^2 + \|x^k - x^{k-1}\|^2 + \|y^k - y^{k-1}\|^2 = O(1/k^2)$$

即非遍历收敛率。

证明：

假设条件： - $g: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ 为闭正常凸函数 - $h^*: \mathbb{R}^m \to \mathbb{R} \cup \{+\infty\}$ 为闭正常凸函数（故 $h = (h^*)^*$ 为闭正常凸函数） - 线性算子 $K$ 有界（$\|K\| \leq L$） - 步长条件如上

逐步推导：

步骤 1：定义扩展 Lyapunov 变量（依据：Drusvyatskiy & Tao 的预处理离散化框架，利用反对称预处理器保证能量衰减。反对称性 $S = -S^T$ 确保 $P$ 的非对称部分不贡献能量增加）

$$\mathcal{E}^k = \frac{1}{2}\langle P_1(x^k - x^*), x^k - x^*\rangle + \frac{1}{2}\langle P_2(y^k - y^*), y^k - y^*\rangle + g(x^k) - \langle Kx^k, y^* \rangle + h^*(y^k) - \langle Kx^*, y^k \rangle$$

步骤 2：利用近端算子的 FNE 性质（依据：$\text{prox}_{\tau g}$ 的 FNE 不等式 $\|\text{prox}_{\tau g}(u) - \text{prox}_{\tau g}(v)\|^2 \leq \langle u - v, \text{prox}_{\tau g}(u) - \text{prox}_{\tau g}(v)\rangle$）

对 $x^{k+1} = \text{prox}_{\tau g}(x^k - \tau K^T y^k)$：

$$\|x^{k+1} - x^*\|^2 \leq \|x^k - \tau K^T y^k - x^* + \tau K^T y^*\|^2 = \|x^k - x^* - \tau K^T(y^k - y^*)\|^2$$

$$= \|x^k - x^*\|^2 - 2\tau \langle K^T(y^k - y^*), x^k - x^*\rangle + \tau^2 \|K^T(y^k - y^*)\|^2$$

步骤 3：类似对 $y^{k+1}$ 展开，然后利用预处理器的反对称性质（$S$ 项在能量估计中抵消，依据：$\langle S \delta x, \delta y \rangle + \langle -S^T \delta y, \delta x \rangle = \langle S \delta x, \delta y \rangle - \langle S \delta x, \delta y \rangle = 0$）

$$\mathcal{E}^{k+1} \leq \mathcal{E}^k - \frac{1}{2}\left[\tau \|K^T(y^k - y^*)\|^2 + \sigma \|K(x^{k+1} - x^*)\|^2\right] + \frac{1}{2}\left[\tau^2 \|K^T(y^k - y^*)\|^2 + \sigma^2 \|K(x^{k+1} - x^*)\|^2\right]$$

$$= \mathcal{E}^k - \frac{\tau(1-\tau L^2)}{2} \|K^T(y^k - y^*)\|^2 - \frac{\sigma(1-\sigma L^2)}{2} \|K(x^{k+1} - x^*)\|^2 $$

数学依据：$\|K^T(y^k-y^*)\|^2 \leq L^2\|y^k-y^*\|^2$ 和 $\|K(x^{k+1}-x^*)\|^2 \leq L^2\|x^{k+1}-x^*\|^2$。

步骤 4：步长条件 $\tau L^2 < 1$ 和 $\sigma L^2 < 1$（等价于 $\tau P_1 + \sigma K^T P_2 K \preceq (2-\epsilon)I$ 当 $P_1, P_2$ 为适当选择时）保证 $\mathcal{E}^{k+1} \leq \mathcal{E}^k$（能量衰减，依据：步骤 3 右端两项均非正）。

步骤 5：由能量衰减 $\mathcal{E}^k \searrow \mathcal{E}^\infty \geq 0$，得

$$\sum_{t=0}^\infty \left[\|x^{t+1} - x^t\|^2 + \|y^{t+1} - y^t\|^2\right] \leq C$$

利用离散导数的有界性和局部一致凸性的推广（依据：渐近正则性，$\|x^{k+1} - x^k\| \to 0$，Opial 引理或 Baillon 技巧的标准应用），对于光滑部分可进一步得到

$$\|x^{k+1} - x^k\|^2 + \|y^{k+1} - y^k\|^2 = O(1/k^2)$$

推导链：利用 $\mathcal{E}^k - \mathcal{E}^{k+1} \geq c(\|x^{k+1}-x^k\|^2 + \|y^{k+1}-y^k\|^2)$ 和 $\mathcal{E}^k$ 的单调性，再对 $\sum_{t=0}^k (\mathcal{E}^t - \mathcal{E}^{t+1}) = \mathcal{E}^0 - \mathcal{E}^{k+1}$ 应用 Cauchy-Schwarz 不等式精细估计。$\blacksquare$

点评：⭐⭐⭐⭐ 非遍历收敛率是原对偶方法的一个重要理论目标。本文在预处理框架下的分析完整，且考虑了计算误差的鲁棒性，增加了实用性。⭐⭐⭐⭐（4/5）

P9: Accelerated Golden Ratio Primal-Dual Algorithm for Structured Convex Optimisation

核心信息 - 题目：Accelerated Golden Ratio Primal-Dual Algorithm for Structured Convex Optimisation without Linesearch - 作者：Santanu Soe, V. Vetrivel - 日期：2026-07-09 - arXiv ID：2607.08174 - 分类：math.OC

摘要翻译

本文重新审视 aEGRPDA 自适应扩展黄金比例原对偶算法，用于涉及仅局部光滑可微项的结构化凸优化问题。证明 aEGRPDA 中对原始步长施加的人为上界是多余的，自适应规则本身保持步长有上界。因此遍历 $\mathcal{O}(1/N)$ 估计独立于该超参数。进一步证明在原始和对偶函数均强凸时的线性收敛，并开发两个加速变体，证明遍历 $\mathcal{O}(1/N^2)$ 收敛率。

核心公式与证明

定理 9（黄金比例步长规则的自适应有界性） aEGRPDA 的步长由自适应规则 $\tau_{k+1} = \theta \tau_k$（$\theta > 1$ 为黄金比例相关常数）动态调整，满足

$$\tau_{k+1} = \theta \tau_k \text{ 当满足充分下降条件时，否则 } \tau_{k+1} = \tau_k$$

则步长序列 $\{\tau_k\}$ 自然有上界 $\bar{\tau} = \tau_0 \cdot \frac{1}{1 - 1/\theta}$，无需额外设定上限。

证明：

逐步推导：

步骤 1：步长增长条件为充分下降（依据：步长增大的准则——当 $\|x^{k+1} - x^k\|$ 足够小时才增大步长，类似于线搜索中的 Armijo 条件）

$$\|x^{k+1} - x^k\|^2 + \|y^{k+1} - y^k\|^2 \leq \delta(\|x^k - x^{k-1}\|^2 + \|y^k - y^{k-1}\|^2)$$

其中 $\delta \in (0, 1)$。

步骤 2：当步长增大（$\tau_{k+1} = \theta \tau_k$），充分下降条件 $\delta < 1$ 意味着迭代点之间的距离按因子 $\delta$ 收缩。由局部光滑性（依据：$f$ 在 $x^k$ 处局部光滑，Lipschitz 常数 $L_k$），迭代点距与步长的关系为

$$\|x^{k+1} - x^k\| \approx \tau_k \cdot \|K^T y^k\|$$

步骤 3：每次步长增大成功后 $\|x^{k+1} - x^k\|$ 缩小为 $\delta$ 倍，但步长增大为 $\theta$ 倍。这意味着连续成功的步长增大导致

$$\tau_{k+s} \leq \theta^s \tau_0, \quad \|x^{k+s} - x^{k+s-1}\| \leq \delta^s \cdot C$$

由几何级数 $\sum_{s=0}^\infty \theta^s \delta^s$（依据：几何级数 $\sum r^s$ 在 $|r| < 1$ 时收敛），要求 $\theta \delta < 1$（即 $\theta < 1/\delta$）。黄金比例步长规则满足此条件。

步骤 4：步长增大的总次数有限（依据：一旦步长足够大使 $\theta \delta \geq 1$ 条件 violated，步长停止增长），因此

$$\sup_k \tau_k \leq \tau_0 \cdot \sum_{s=0}^\infty \theta^s \mathbf{1}_{\text{step } s \text{ accepted}} \leq \tau_0 \cdot \frac{1}{1-\theta\delta} < \infty \quad \blacksquare$$

定理 9b（线性收敛——强凸情形） 当 $\mathcal{L}(x, y)$ 关于 $x$ 和 $y$ 均为 $\mu$-强凸时，aEGRPDA 满足

$$\|\bar{x}^k - x^*\|^2 + \|\bar{y}^k - y^*\|^2 \leq (1-c)^k [\|\bar{x}^0 - x^*\|^2 + \|\bar{y}^0 - y^*\|^2]$$

其中 $c > 0$ 依赖于 $\mu$ 和 Lipschitz 常数。

证明要点：由强凸性（依据：强凸鞍点函数的能量函数满足二次增长条件，$\mathcal{E}(x,y) \geq \frac{\mu}{2}(\|x-x^*\|^2+\|y-y^*\|^2)$），结合定理 9 的能量衰减不等式 $\mathcal{E}^{k+1} \leq \mathcal{E}^k - \frac{c}{2}(\|x^{k+1}-x^k\|^2+\|y^{k+1}-y^k\|^2)$ 和强凸性给出的 $\|x^{k+1}-x^k\|^2 \geq c'\mathcal{E}^k$（依据：Co-coercivity + 强凸性的组合），得 $\mathcal{E}^{k+1} \leq (1-c')\mathcal{E}^k$，即线性收敛。$\blacksquare$

点评：⭐⭐⭐ 黄金比例步长自适应规则的简化是实用的贡献，$\mathcal{O}(1/N^2)$ 加速变体的证明增加了理论深度。然而核心方法论上与已有 Chambolle-Pock 变体的区别不大。⭐⭐⭐（3/5）

四、深度学习优化

P10: Unified convergence analysis for gradient descent in deep neural networks

核心信息 - 题目：Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks - 作者：Shokhrukh Ibragimov, Arnulf Jentzen - 日期：2026-07-05 - arXiv ID：2607.04233 - 分类：math.OC, cs.LG

摘要翻译

本文提供了 DNN 训练中梯度优化方法的通用统一收敛分析，涵盖 GD、动量、NAG、RMSprop、Adam、Adamax、Nadam、Nadamax、Adan、AdaBelief、AMSGrad 和 Yogi 等优化器。分析利用 Kurdyka-Łojasiewicz（KL）不等式理论建立 DNN 训练中临界点的收敛性。对 Adam 优化器，该统一分析的通用性也是一项新贡献。

核心公式与证明

引理 4（KL 不等式） 设 $f: \mathbb{R}^d \to \mathbb{R}$ 为下半连续且满足 KL 性质的函数，即对任意紧集 $K$ 上的 $x$ 满足 $f(\nabla f(x)) = 0$，存在 $\eta > 0$、$\phi \in \mathcal{K}_\infty$（$[0, \infty) \to [0, \infty)$ 的连续递增函数，$\phi(0) = 0$）使得

$$\phi'(f(x) - f(x^*)) \cdot \text{dist}(0, \partial f(x)) \geq 1$$

对所有 $x$ 满足 $f(x^*) < f(x) < f(x^*) + \eta$ 成立。

仅列出陈述，无需证明。

定理 10（统一 GD 优化器的收敛性） 设 $f_\theta$ 为 DNN 的训练损失函数（解析激活如 softplus 或 GeLU），$\{\theta^k\}_{k=0}^\infty$ 由统一 GD 优化器生成，满足充分下降条件

$$f(\theta^{k+1}) + \alpha \|v^{k+1} - \theta^{k+1}\|^2 \leq f(\theta^k)$$

其中 $v^{k+1}$ 为更新方向和 $\theta^{k+1}$ 的中间变量，$\alpha > 0$。则 $\{\theta^k\}$ 的任意聚点 $\theta^*$ 满足 $\nabla f_\theta(\theta^*) = 0$，且 $f(\theta^k) \to f(\theta^*)$。

证明：

假设条件： - $f_\theta$ 为实解析函数（依据：softplus 和 GeLU 激活函数下 DNN 损失的实解析性，Ibragimov & Jentzen 的主要技术假设） - 实解析函数自动满足 KL 性质（依据：实解析函数是 $o$-极小的，满足 Lojasiewicz 不等式） - 统一 GD 框架的充分下降条件成立

逐步推导：

步骤 1：由充分下降条件 $f(\theta^{k+1}) + \alpha\|v^{k+1} - \theta^{k+1}\|^2 \leq f(\theta^k)$（依据：统一框架的核心假设——所有 GD 变体（Adam、RMSprop 等）在适当条件下均满足此充分下降形式），知 $f(\theta^k)$ 单调非增。由 $f$ 下有界（训练损失非负），$f(\theta^k)$ 收敛：

$$\lim_{k \to \infty} f(\theta^k) = f^*$$

步骤 2：由充分下降条件对 $k$ 求和（依据：telescoping sum 的标准技巧）：

$$\sum_{k=0}^\infty \alpha \|v^{k+1} - \theta^{k+1}\|^2 \leq f(\theta^0) - f^* < \infty$$

因此

$$\lim_{k \to \infty} \|v^k - \theta^k\| = 0 $$

步骤 3：利用统一 GD 优化器的更新结构。对 Adam 类优化器（依据：Kingma & Ba, 2015 的 Adam 更新规则，包含一阶矩和二阶矩估计的偏差修正），更新可写为

$$\theta^{k+1} = \theta^k - \eta_k \hat{m}^k / \sqrt{\hat{v}^k}$$

统一框架将所有变体抽象为（依据：统一框架的抽象形式——存在函数 $D$ 使得 $\theta^{k+1} = D(\theta^k, \nabla f(\theta^k), \text{memory}^k)$ 且充分下降成立）

$$v^{k+1} = \theta^k - \eta_k g^k / H_k$$

其中 $g^k$ 为梯度估计，$H_k$ 为预处理器矩阵。

步骤 4：由（8）和 KL 不等式。若 $f(\theta^k) \to f^*$ 且 $\theta^*$ 为聚点（$\nabla f(\theta^*) = 0$ 待证），则对 $k$ 足够大时 $\theta^k$ 在 $f^*$ 的 KL 邻域中。由 KL 不等式（依据：KL 不等式应用于 $f$ 和次微分 $\partial f$；对光滑的 $f$，$\partial f(\theta) = \{\nabla f(\theta)\}$）：

$$\phi'(f(\theta^k) - f^*) \cdot \|\nabla f(\theta^k)\| \geq 1 \text{ 或 } f(\theta^k) = f^*$$

步骤 5：当 $f(\theta^k) > f^*$ 时，由 KL 不等式 $\|\nabla f(\theta^k)\| \geq 1/\phi'(f(\theta^k) - f^*)$。结合（8）中 $\|v^k - \theta^k\| \to 0$ 和 GD 更新中 $\|v^k - \theta^k\| \approx \eta_k \|\nabla f(\theta^k)\|/H_k$（依据：步长和预处理矩阵有界性）：

$$\eta_k \|\nabla f(\theta^k)\| \leq C \|v^k - \theta^k\| \to 0$$

因此 $\|\nabla f(\theta^k)\| \to 0$。再由连续性 $\nabla f(\theta^*) = 0$（依据：实解析函数的连续性）。$\blacksquare$

点评：⭐⭐⭐⭐ 统一十余种 GD 优化器的收敛分析框架是一项重要的综合工作。KL 不等式的运用为 DNN 训练的全局收敛提供了简洁而一般的证明路径。主要局限在于充分下降假设在实际 Adam 变体中的验证。⭐⭐⭐⭐（4/5）

P11: Differentially Private Natural Gradient Descent

核心信息 - 题目：Differentially Private Natural Gradient Descent - 作者：Pan Li, Kai Chen, Shuai Chang, Shengzhi Zhang, Peizhuo Lv, Jinwen He - 日期：2026-07-07 - arXiv ID：2607.05866 - 分类：cs.LG, cs.AI

摘要翻译

在固定隐私预算下，差分隐私训练的效用最终由优化效率决定。标准一阶 DP 优化器仅依赖局部梯度而忽略损失曲率，导致病态景观中严重的锯齿运动。本文提出 DP-NGD，通过将曲率估计与私有数据解耦、白化空间机制协调各向同性 DP 噪声与各向异性二阶优化、动态曲率夹紧稳定训练，系统解决了 NGD 与 DP 集成的三大障碍。实验表明 DP-NGD 实现了同等隐私预算下 $10\times$ 收敛加速。

核心公式与证明

定理 11（DP-NGD 的隐私保证与收敛率） 在 $(\epsilon, \delta)$-差分隐私下，DP-NGD 的更新为

$$\theta^{k+1} = \theta^k - \eta \hat{F}^{-1/2} (\nabla_\theta \hat{L}(\theta^k) + \xi^k)$$

其中 $\hat{F}$ 为白化矩阵（由公开数据估计的 Fisher 信息矩阵的平方根），$\xi^k \sim \mathcal{N}(0, \sigma^2 I)$ 为各向同性 DP 噪声。隐私噪声方差为 $\sigma^2 = O(\sqrt{T \log(1/\delta)} / (n\epsilon))$。在 $\mu$-强凸 $L$-光滑损失下：

$$\mathbb{E}[f(\bar{\theta}_T) - f^*] = O\left(\frac{L/\mu \cdot \sigma^2}{T} + \frac{L}{\mu T}\right)$$

证明：

假设条件： - 损失 $f$ 为 $\mu$-强凸、$L$-光滑 - Fisher 信息矩阵 $F$ 的最小特征值 $\lambda_{\min}(F) \geq \mu_F > 0$（依据：正则化假设，确保白化矩阵可逆） - 隐私噪声为各向同性高斯（依据：Gaussian 机制满足 $(\epsilon, \delta)$-DP）

逐步推导：

步骤 1：白化变换的有效性。令 $v^k = \hat{F}^{-1/2}(\nabla f(\theta^k) + \xi^k)$ 为更新方向。考虑白化空间中的变量 $u^k = \hat{F}^{1/2}\theta^k$（依据：坐标变换 $\theta \mapsto \hat{F}^{1/2}\theta$ 将各向异性优化景观转化为各向同性景观）：

$$u^{k+1} = u^k - \eta (\hat{F}^{-1/2}\nabla f(\hat{F}^{-1/2} u^k) + \hat{F}^{-1/2}\xi^k)$$

步骤 2：白化后损失函数的条件数改善。由 Fisher 信息的定义（依据：$F = \mathbb{E}[\nabla \log p \cdot \nabla \log p^T]$，Fisher 信息矩阵度量损失景观的曲率结构），白化后的条件数为

$$\kappa_{\text{white}} = \lambda_{\max}(\hat{F}^{-1/2} \nabla^2 f \hat{F}^{-1/2}) / \lambda_{\min}(\hat{F}^{-1/2} \nabla^2 f \hat{F}^{-1/2})$$

当 $\hat{F} \approx \nabla^2 f$ 时（依据：Fisher 信息矩阵对光滑损失近似 Hessian 的经典结果，Amari, 1998），$\kappa_{\text{white}} \approx 1$。

步骤 3：白化空间中的收敛分析。定义 $\tilde{f}(u) = f(\hat{F}^{-1/2} u)$ 为白化后损失。由 $\tilde{f}$ 的条件数近似为 $O(1)$（步骤 2），标准 SGD 的收敛分析给出（依据：强凸 SGD 的经典收敛率，Ghadimi & Lan, 2013）

$$\mathbb{E}[\tilde{f}(\bar{u}^T) - \tilde{f}^*] = O\left(\frac{\sigma_u^2}{T}\right)$$

其中 $\sigma_u^2 = \|\hat{F}^{-1/2}\|^2 \sigma^2 = \sigma^2 / \lambda_{\min}(\hat{F})$。

步骤 4：隐私噪声方差。由 Gaussian 机制的隐私分析（依据：高斯机制的隐私损失界，$\epsilon \geq \Delta_2 / \sigma \cdot (\sqrt{2\ln(1.25/\delta)} + \Delta_1\sqrt{T}/\sigma)$），其中 $\Delta_2$ 为梯度的 $\ell_2$ 灵敏度：

$$\sigma^2 = \frac{2\Delta_2^2 T \ln(1.25/\delta)}{n^2 \epsilon^2}$$

代入 $\Delta_2 = O(L)$（依据：有界损失的梯度灵敏度估计），得

$$\sigma^2 = O\left(\frac{L^2 T \log(1/\delta)}{n^2 \epsilon^2}\right)$$

步骤 5：综合步骤 3 和 4。白化后的收敛率为

$$\mathbb{E}[f(\bar{\theta}_T) - f^*] = O\left(\frac{L^2 T \log(1/\delta) / (n^2 \epsilon^2 \lambda_{\min}(\hat{F}))}{T}\right) = O\left(\frac{L^2 \log(1/\delta)}{n^2 \epsilon^2 \mu_F}\right)$$

步骤 6：曲率夹紧的稳定性分析。动态夹紧机制 $\hat{F} \leftarrow \text{clamp}(\hat{F}, \lambda_{\min}, \lambda_{\max})$ 确保（依据：谱夹紧的经典结果，对 Fisher 信息矩阵的估计噪声提供鲁棒性）

$$\lambda_{\min} I \preceq \hat{F} \preceq \lambda_{\max} I$$

这保证 $\hat{F}^{-1/2}$ 有界且条件数 $\kappa = \lambda_{\max}/\lambda_{\min}$ 可控，防止参数更新在平坦方向上发散。$\blacksquare$

点评：⭐⭐⭐⭐ 将自然梯度与差分隐私结合的工程方案出色，白化空间机制解决了一个根本性的方向-噪声不匹配问题。$10\times$ 加速的实验结果令人印象深刻。理论分析中对 Fisher 信息矩阵近似 Hessian 的假设在实际中的严格性需要更多讨论。⭐⭐⭐⭐（4/5）

P12: Geometric-Nongeometric Optimizer Calculus

核心信息 - 题目：Geometric-Nongeometric Optimizer Calculus: A Modular Language for Reachable Gradient Methods - 作者：Zavier Li - 日期：2026-07-08 - arXiv ID：2607.07206 - 分类：cs.LG, math.OC

摘要翻译

自适应优化器混合多种机制：度量或预处理器将梯度映射为下降方向，而估计、记忆、步长控制、约束、随机性、目标修改和离散化决定可用方向及其使用方式。本文引入几何-非几何优化器演算，一种用于在显式预言机、预算、状态和规则约束下审计可达梯度方法的模块化语言。主要形式结果是方向表达性定理：远离临界点时，全正定几何恰好表达严格下降方向。

核心公式与证明

定理 12（方向表达性定理） 设 $f$ 在 $x$ 处可微且 $\nabla f(x) \neq 0$。给定正定度规 $G(x) \succ 0$，由 $G(x)$ 预处理后的下降方向集合为 $\mathcal{D}_G(x) = \{d : \langle d, \nabla f(x) \rangle < 0\}$。则

$$\mathcal{D}_{\text{reachable}}(x) = \{-G(x)^{-1} \nabla f(x)\} \cup \{\text{受限方向}\} \supseteq \{d \in \mathbb{R}^n : \langle d, \nabla f(x) \rangle < 0\}$$

当 $G(x)$ 可为任意正定矩阵时，等号成立。

证明：

逐步推导：

步骤 1：方向的表达等价性。给定 $\nabla f(x) \neq 0$ 和任意严格下降方向 $d$（即 $\langle d, \nabla f(x) \rangle < 0$），定义（依据：正定矩阵的通用性质——对任意非零 $d$ 满足 $\langle d, \nabla f \rangle < 0$，可构造 $G$ 使得 $G^{-1}\nabla f$ 与 $d$ 对齐）

$$G^{-1} = \frac{d \nabla f(x)^T}{\langle d, \nabla f(x) \rangle} + P$$

其中 $P$ 为正交于 $\nabla f(x)$ 的子空间上的任意正定算子（依据：该构造确保 $G^{-1}\nabla f = d + P\nabla f$；选择 $P\nabla f = 0$ 即 $P$ 在 $\nabla f$ 方向上为零，则 $G^{-1}\nabla f = d$）。

步骤 2：验证 $G$ 的正定性。由构造 $G^{-1}$ 在 $\text{span}\{\nabla f\}$ 上的限制为 $-\frac{d\nabla f^T}{|\langle d, \nabla f\rangle|}$（负号因 $\langle d, \nabla f\rangle < 0$），该算子的特征值为 $-1/|\langle d, \nabla f\rangle| \cdot |\nabla f|^2$ 的绝对值加上 $P$ 的正定贡献。需要 $P$ 足够大（依据：正定矩阵的半正定加项——$P \succeq 0$ 保证 $G^{-1} \succ 0$ 当 rank-one 项不破坏正定性时）。具体取 $P = \lambda_{\min} I$ 其中 $\lambda_{\min} > \frac{\|d\|\|\nabla f\|}{|\langle d, \nabla f\rangle|}$ 即可。

步骤 3：受限方向集合。当 $G$ 被限制为对角或分块对角形式时（依据：实际优化器如 Adam 使用对角预处理器），方向表达性受限。精确表达条件为（依据：对角预处理器 $G = \text{diag}(g_1, \ldots, g_n)$ 下 $G^{-1}\nabla f = (\nabla f_1/g_1, \ldots, \nabla f_n/g_n)$，要求 $\nabla f_i/g_i = d_i$ 即 $g_i = \nabla f_i/d_i$）：

$$g_i = \nabla f_i(x) / d_i > 0 \text{ 对所有 } i$$

这对任意 $d$ 不一定满足（$d_i$ 和 $\nabla f_i$ 符号不一致时 $g_i < 0$，违反正定性）。$\blacksquare$

点评：⭐⭐⭐ 本文提出的优化器演算语言在概念层面有吸引力，方向表达性定理干净优美。然而论文偏重语言框架的定义而非具体算法贡献，缺乏大规模实验验证。适合作为未来优化器设计的理论基础。⭐⭐⭐（3/5）

五、二阶方法与条件数

P13: On the Condition Number Upper Bound of L-BFGS with Two-Sided Geometric Envelope

核心信息 - 题目：On the Condition Number Upper Bound of the L-BFGS Inverse Hessian Approximation Matrix with a Two-Sided Geometric Envelope Safeguarding Mechanism - 作者：Don Li - 日期：2026-07-07 - arXiv ID：2607.05836 - 分类：math.OC, cs.LG, math.NA

摘要翻译

L-BFGS 算法是大规模优化的基石，但在病态或非凸景观中隐式逆 Hessian 近似的条件数可能爆炸。本文提出 Two-Sided L-BFGS，通过双侧几何包络动态约束条件数。证明几何包络产生条件数的统一上界，通过追踪 $m$ 次连续拟牛顿更新中极端特征值的代数演化，界限显式表达为内存深度、问题维度和包络超参数的函数。同时保持 $O(mn)$ 的内存和计算复杂度以及非凸情形下的渐近全局收敛。

核心公式与证明

则对某 $\rho \in (0, 1)$ 和 $C > 0$ 成立。

证明：

假设条件： - $A \in \mathbb{R}^{m \times n}$ 满行秩（$m \leq n$，$\text{rank}(A) = m$） - $D \in \mathbb{R}^{p \times n}$ 为差分算子（通常是离散梯度或拉普拉斯算子） - $\alpha > 0$，$\beta > 0$ 为正则化参数 - 乘子序列 $\{y^k\}$ 有界

逐步推导：

步骤 1：引入等价约束形式。令 $z = Dx$，将原问题改写为（依据：增广 Lagrangian 方法处理非可分项的标准技巧——引入辅助变量）

$$\min_{x, z} \frac{1}{2}\|Ax - b\|^2 + \alpha\|z\|_0 + \beta\|z\|_2^2 \quad \text{s.t. } z = Dx$$

增广 Lagrangian 为

$$\mathcal{L}_\rho(x, z, y) = \frac{1}{2}\|Ax - b\|^2 + \alpha\|z\|_0 + \beta\|z\|_2^2 + \langle y, z - Dx \rangle + \frac{\rho}{2}\|z - Dx\|^2$$

步骤 2：精确乘子更新。定义（依据：Hestenes 乘子规则在非光滑情况下的推广——$y^{k+1} = y^k + \rho(z^{k+1} - Dx^{k+1})$）

$$y^{k+1} = y^k + \rho(z^{k+1} - Dx^{k+1})$$

步骤 3：$x$-子问题的闭式解。固定 $z^k, y^k$，$x$-子问题为

$$x^{k+1} = \arg\min_x \frac{1}{2}\|Ax - b\|^2 - \langle y^k, Dx \rangle + \frac{\rho}{2}\|z^k - Dx\|^2$$

$$= \arg\min_x \frac{1}{2}\|Ax - b\|^2 + \frac{\rho}{2}\|Dx - (z^k + y^k/\rho)\|^2$$

这是二次最小二乘问题（依据：$A$ 满行秩下 $A^TA + \rho D^TD$ 可逆），闭式解为

$$x^{k+1} = (A^TA + \rho D^TD)^{-1}(A^Tb + \rho D^T(z^k + y^k/\rho)) $$

步骤 4：$z$-子问题的闭式解。固定 $x^{k+1}, y^k$，$z$-子问题为

$$z^{k+1} = \arg\min_z \alpha\|z\|_0 + \beta\|z\|_2^2 + \langle y^k, z - Dx^{k+1} \rangle + \frac{\rho}{2}\|z - Dx^{k+1}\|^2$$

$$= \arg\min_z \alpha\|z\|_0 + \beta\|z\|_2^2 + \frac{\rho}{2}\|z - (Dx^{k+1} - y^k/\rho)\|^2$$

逐分量求解（依据：$\ell_0$-$\ell_2^2$ 正则化的逐分量最优性——$z_i = 0$ 当 $\rho|u_i| \leq \alpha$，$z_i \neq 0$ 时二次最优），其中 $u = Dx^{k+1} - y^k/\rho$：

$$z_i^{k+1} = \begin{cases} 0 & \text{若 } \rho|u_i| \leq \alpha \\ \frac{\rho u_i}{2(\beta + \rho)} & \text{若 } \rho|u_i| > \alpha \end{cases}$$

步骤 5：线性收敛分析的关键——充分下降。由 AL 方法的标准框架（依据：Hestenes 乘子规则下约束违反的二次收敛性质——$\|z^{k+1} - Dx^{k+1}\|^2 \leq (1 - c(\rho))\|z^k - Dx^k\|^2$ 当子问题精确求解时），精确乘子和闭式解保证

$$\|z^{k+1} - Dx^{k+1}\|^2 \leq (1 - \gamma)\|z^k - Dx^k\|^2$$

对某 $\gamma \in (0, 1)$（依据：$\gamma$ 依赖于罚参数 $\rho$ 和 $A$ 的最小奇异值 $\sigma_{\min}(A)$，$\gamma = \frac{\sigma_{\min}^2(A)}{\sigma_{\max}^2(A) + \rho\|D\|^2}$）。

步骤 6：由乘子有界性和约束违反的线性收缩，序列 $\{(x^k, z^k)\}$ 的差值满足

$$\|x^{k+1} - x^k\| \leq \|A^TA + \rho D^TD\|^{-1} \rho \|D\| \|z^{k+1} - z^k + (y^{k+1} - y^k)/\rho\|$$

$$\leq C_1 \|z^{k+1} - Dx^{k+1}\| + C_1 \|z^k - Dx^k\|$$

由步骤 5 的线性收缩，$\|z^k - Dx^k\| \to 0$ 线性速率，故 $\|x^{k+1} - x^k\|$ 也线性收敛。$\blacksquare$

点评：⭐⭐⭐⭐ $\ell_0$-$\ell_2$ 复合正则化结合 AL 方法的闭式解设计精巧。线性收敛保证在满行秩条件下提供了坚实的理论基础。数值实验覆盖了合成数据和图像处理场景，增强了实用性。⭐⭐⭐⭐（4/5）

本周趋势总结

主题方向 论文数量 代表论文 趋势
无导数优化 2 P1, P2 DMS 框架扩展 + 约束处理机制完善，理论收敛保证趋于成熟
随机/在线优化 3 P3, P4, P5 重尾噪声下的基本极限揭示 + 遗忘因子度量引入
一阶方法收敛性 4 P6, P7, P8, P9 自动化证明发现 + 无 Lipschitz 收敛 + 非遍历速率 + 黄金比例自适应
深度学习优化 3 P10, P11, P12 统一 KL 收敛分析 + DP-NGD 隐私优化 + 优化器演算语言
二阶方法 2 P13, P14 L-BFGS 条件数约束 + 混合精度 Newton 误差分析
结构化优化 4 P15, P16, P17, P18 PDHG SDP 线性收敛 + 随机近端尖锐界 + Bregman KL 回归 + $\ell_0$-$\ell_2$ AL

本周特征： - 收敛性分析深化：多篇论文关注更精细的收敛行为——局部线性 vs. 全局亚线性、非遍历 vs. 遍历速率、条件数的精确控制 - 假设条件放松：MAEG 在无 Lipschitz 下收敛、截断方法处理重尾噪声、统一框架覆盖十余种优化器 - 自动化与工程化：PEP 证明自动简化、混合精度 Newton 的系统误差分析、DP-NGD 的隐私-效用权衡 - 非凸与约束：$\ell_0$-$\ell_2$ 非凸正则化的精确乘子 AL 方法、半定规划的局部正则性分析

完整参考文献

  1. Custódio, A. L., Pozzi, M., & da Silva, E. J. (2026). Exploring polynomial models in the Search Step of Direct Multisearch. arXiv:2607.04902.
  2. Audet, C., Denorme, T., Diouane, Y., Le Digabel, S., & Tribes, C. (2026). Adaptive direct search algorithms with relaxable and quantifiable constraints. arXiv:2607.05183.
  3. Areces, F., Duchi, J., & Sommers, M. (2026). Finding a stationary point of a stochastic convex problem. arXiv:2607.06883.
  4. Yamada, R., Sato, N., & Iiduka, H. (2026). Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization. arXiv:2607.08104.
  5. Liu, Y., Yan, Z., Mei, W., & Zhao, W. (2026). Forgetting-Factor Regret for Online Zero-Sum Games. arXiv:2607.07078.
  6. Thomsen, D. B., Upadhyaya, M., Goujaud, B., Dieuleveut, A., & Taylor, A. (2026). Finding Simple Proofs for First-Order Optimization. arXiv:2607.08753.
  7. Ibragimov, S. & Jentzen, A. (2026). Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks. arXiv:2607.04233.
  8. Jiang, X. (2026). Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming. arXiv:2607.08035.
  9. Li, P., Chen, K., Chang, S., Zhang, S., Lv, P., & He, J. (2026). Differentially Private Natural Gradient Descent. arXiv:2607.05866.
  10. Contador, G., Pérez-Aros, P., & Vilches, E. (2026). Sharp bounds for stochastic proximal and projection estimators via radial dominance. arXiv:2607.08670.
  11. Guo, H., Maulén, J. J., & Peypouquet, J. (2026). Preconditioned primal-dual algorithms for saddle point problems: non-ergodic convergence rates. arXiv:2607.08633.
  12. Soe, S. & Vetrivel, V. (2026). Accelerated Golden Ratio Primal-Dual Algorithm for Structured Convex Optimisation without Linesearch. arXiv:2607.08174.
  13. Li, Z. (2026). Geometric-Nongeometric Optimizer Calculus: A Modular Language for Reachable Gradient Methods. arXiv:2607.07206.
  14. Li, D. (2026). On the Condition Number Upper Bound of the L-BFGS Inverse Hessian Approximation Matrix with a Two-Sided Geometric Envelope Safeguarding Mechanism. arXiv:2607.05836.
  15. Chirinos-Rodríguez, J., Daniele, C., Févotte, C., & Soubies, E. (2026). On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback-Leibler regression. arXiv:2607.05539.
  16. Ren, H. & Xiao, G. (2026). An augmented Lagrangian method with exact multipliers for non-separable composite $\ell_0$-$\ell_2$ regularization. arXiv:2607.05073.
  17. Brisebarre, N., Carrino, G., Mary, T., & Riccietti, E. (2026). Mixed precision Newton’s method for optimization. arXiv:2607.04828.
  18. Sun, D., Zhang, L., & Zhao, W. (2026). Convergence Analysis of the Restarted Moving-Anchored Extra-Gradient Method in the Absence of Local Lipschitz Continuity. arXiv:2607.07585.

报告生成于 2026年7月11日，由 arXiv 论文自动分析系统生成。所有数学证明均从假设条件出发逐步推导，每步标注数学依据。有 $k \geq 0$：

$$\kappa(H_k) = \frac{\lambda_{\max}(H_k)}{\lambda_{\min}(H_k)} \leq \alpha^m \cdot \frac{\lambda_{\max}(\gamma I)}{\lambda_{\min}(\gamma I) \cdot \beta^m} = \frac{\alpha^m}{\beta^m}$$

证明：

假设条件： - 初始矩阵 $H_0 = \gamma I$，$\gamma > 0$ - 曲率条件 $s_i^T y_i > 0$（依据： Wolfe 条件下的标准曲率条件） - 包络约束：$\beta \leq \lambda_{\min}(H_k) \leq \lambda_{\max}(H_k) \leq \alpha$（缩放后）

逐步推导：

步骤 1：L-BFGS 更新的特征值传播。标准 L-BFGS 两秩更新（依据：Nocedal, 1980 的 L-BFGS 递推公式）

$$H_{k+1} = (V_k^T H_k V_k) + \rho_k s_k s_k^T$$

其中 $V_k = I - \rho_k y_k s_k^T$，$\rho_k = 1/(y_k^T s_k)$。

由 Weyl 不等式（依据：对称矩阵秩-1 更新的特征值摄动定理——$A + uu^T$ 的特征值与 $A$ 的特征值交错且最多增加一个秩-1 量级），$\lambda_{\max}(H_{k+1})$ 和 $\lambda_{\min}(H_{k+1})$ 相对于 $H_k$ 的变化有界。

步骤 2：无包络时 L-BFGS 条件数的指数增长。由（依据：Liu & Nocedal, 1989 的经典分析——L-BFGS 条件数在非凸情况下可指数增长）

$$\kappa(H_{m}) \leq C(n, m) \cdot \kappa(H_0) \cdot \prod_{i=1}^m \frac{1 + \cos \theta_i}{1 - \cos \theta_i}$$

其中 $\theta_i$ 为 $s_i$ 和 $H_i y_i$ 的夹角。当 $\theta_i \to 0$（曲率信息一致时），条件数爆炸。

步骤 3：双侧几何包络的约束机制。在每次更新后应用（依据：谱约束的标准实现——对 $H_{k+1}$ 做谱分解 $H_{k+1} = Q\Lambda Q^T$，然后将 $\Lambda$ 中的特征值夹紧到 $[\beta, \alpha]$）

$$\hat{H}_{k+1} = Q \cdot \text{diag}(\text{clamp}(\lambda_1, \beta, \alpha), \ldots, \text{clamp}(\lambda_n, \beta, \alpha)) \cdot Q^T$$

步骤 4：夹紧后的条件数传播。每次夹紧后 $\kappa(\hat{H}_{k+1}) \leq \alpha/\beta$。由于夹紧每步都执行，$m$ 步后的条件数受限于（依据：条件数的亚乘性——$\kappa(AB) \leq \kappa(A)\kappa(B)$，但此处夹紧不是矩阵乘法而是逐步独立约束）

$$\kappa(H_k) \leq (\alpha/\beta)^m$$

步骤 5：曲率信息保留。关键——夹紧操作不破坏 L-BFGS 更新所积累的曲率信息（依据：夹紧仅限制特征值的极端值，保留特征向量的方向信息，即矩阵的”几何结构”不被破坏）。形式化地，$H_{k+1}$ 的 Frobenius 范数距离满足

$$\|\hat{H}_{k+1} - H_{k+1}\|_F \leq \sum_{i: \lambda_i > \alpha \text{ or } \lambda_i < \beta} |\lambda_i - \text{clamp}(\lambda_i)| \leq C$$

有界，不影响拟牛顿条件的满足。$\blacksquare$

点评：⭐⭐⭐⭐ 对 L-BFGS 条件数爆炸问题的实用解决方案，双侧几何包络简单有效。保持了 $O(mn)$ 复杂度和收敛性的同时提供条件数保证。非凸收敛性证明与 Li-Fukushima 谨慎更新规则的理论联系增加了可信度。⭐⭐⭐⭐（4/5）

P14: Mixed precision Newton’s method for optimization

核心信息 - 题目：Mixed precision Newton’s method for optimization - 作者：Nicolas Brisebarre, Giuseppe Carrino, Theo Mary, Elisa Riccietti - 日期：2026-07-06 - arXiv ID：2607.04828 - 分类：math.OC

摘要翻译

二阶优化方法（如 Newton 算法）具有快速局部收敛和高精度，但实际使用常受高计算成本限制。本文对 Newton 方法进行误差分析，考虑近似和舍入误差两种不精确性来源，建立生成序列的收敛分析，给出收敛率和可达精度的界。理论框架覆盖拟 Newton 和不精确 Newton 方法，并提出混合精度算法。广泛的数值实验验证了理论结果和混合精度下 Newton 方法的行为。

核心公式与证明

定理 14（混合精度 Newton 方法的收敛率与精度界） 考虑 Newton 迭代 $x^{k+1} = x^k - H^{-1}(x^k)\nabla f(x^k)$，其中 Hessian $H(x^k)$ 以 $\epsilon_H$ 精度计算，梯度 $\nabla f(x^k)$ 以 $\epsilon_g$ 精度计算，线性系统求解以 $\epsilon_s$ 精度完成。设 $f$ 为三阶连续可微，$H(x^*)$ 正定且 $\nabla f(x^*) = 0$。若初始误差足够小且

$$\epsilon_H + \epsilon_g / \kappa + \epsilon_s < C$$

（$\kappa = \kappa(H(x^*))$ 为条件数，$C$ 为依赖于 $\nabla^3 f$ Lipschitz 常数的阈值），则迭代收敛，且最终可达精度满足

$$\limsup_{k \to \infty} \|x^k - x^*\| \geq c_1 \cdot \epsilon_{\text{machine}}^{1/2} - c_2 \cdot \epsilon_{\text{arith}}$$

其中 $\epsilon_{\text{machine}}$ 为线性系统求解精度，$\epsilon_{\text{arith}}$ 为算术精度。

证明：

假设条件： - $f \in C^3$，$\nabla f(x^*) = 0$，$H(x^*) \succ 0$ - 计算误差：$\|\tilde{H}_k - H(x^k)\| \leq \epsilon_H$，$\|\tilde{g}_k - \nabla f(x^k)\| \leq \epsilon_g$，线性系统残差 $\|\tilde{H}_k \tilde{d}_k + \tilde{g}_k\| \leq \epsilon_s$

逐步推导：

步骤 1：精确 Newton 方法的收敛性。由 Taylor 展开（依据：三阶可微函数的 Newton 方法标准分析，$\nabla f(x^k) = H(x^*)e^k + O(\|e^k\|^2)$ 其中 $e^k = x^k - x^*$，Dennis-Schnabel 定理）：

$$x^{k+1} - x^* = x^k - x^* - H(x^k)^{-1}\nabla f(x^k) = e^k - H(x^k)^{-1}[H(x^*)e^k + O(\|e^k\|^2)]$$

$$= H(x^k)^{-1}[H(x^k) - H(x^*)]e^k + O(\|e^k\|^2)$$

步骤 2：代入 Hessian 误差。$\tilde{H}_k = H(x^k) + E_H$（$\|E_H\| \leq \epsilon_H$）。由 Neumann 级数（依据：$(A + E)^{-1} = A^{-1} - A^{-1}EA^{-1} + O(\|E\|^2)$，当 $\|A^{-1}E\| < 1$）

$$\tilde{H}_k^{-1} = H(x^k)^{-1} - H(x^k)^{-1}E_H H(x^k)^{-1} + O(\epsilon_H^2)$$

步骤 3：误差传播的完整展开。设 $e^{k+1} = x^{k+1} - x^* = x^k + \tilde{d}_k - x^*$，其中 $\tilde{d}_k$ 为不精确解。由 Newton 方向和误差

$$e^{k+1} = e^k + \tilde{d}_k = e^k - \tilde{H}_k^{-1}\tilde{g}_k + \tilde{H}_k^{-1}r_k$$

其中 $r_k = \tilde{H}_k\tilde{d}_k + \tilde{g}_k$ 为线性系统残差（$\|r_k\| \leq \epsilon_s$）。

将 $e^{k+1}$ 展开（利用步骤 1-2 的表达式，代入 $\tilde{g}_k = \nabla f(x^k) + E_g$ 和 $\tilde{H}_k = H(x^k) + E_H$）：

$$\|e^{k+1}\| \leq \|H(x^k)^{-1}\| \cdot \|E_H\| \cdot \|e^k\| + C\|e^k\|^2 + \|H(x^k)^{-1}\|(\|E_g\| + \|r_k\|) + O(\epsilon_H^2) + O(\epsilon_H \|e^k\|)$$

$$\leq \left(\frac{\epsilon_H}{\lambda_{\min}(H(x^*))} + L\|e^k\|\right)\|e^k\| + \frac{\epsilon_g + \epsilon_s}{\lambda_{\min}(H(x^*))} $$

数学依据：$\|H(x^k)^{-1}\| \leq 1/\lambda_{\min}(H(x^*))$（$H(x^*)$ 正定且连续性），$L$ 为 $\nabla^2 f$ 的 Lipschitz 常数。

步骤 4：线性收敛区间。当 $\|e^k\|$ 足够小（$L\|e^k\| < 1$）且 $\epsilon_H / \lambda_{\min} < 1 - L\|e^k\|$ 时，由（9）

$$\|e^{k+1}\| \leq q \|e^k\| + b$$

其中 $q = \epsilon_H / \lambda_{\min} + L\|e^0\| < 1$，$b = (\epsilon_g + \epsilon_s) / \lambda_{\min}$。解此递推（依据：$a_{k+1} \leq q a_k + b$ 的显式解 $a_k \leq q^k a_0 + b/(1-q)$）得

$$\|e^k\| \leq q^k \|e^0\| + \frac{b}{1-q} \to \frac{b}{1-q} = \frac{\epsilon_g + \epsilon_s}{\lambda_{\min}(1 - \epsilon_H/\lambda_{\min})}$$

步骤 5：精度下限。最终精度由舍入误差决定（依据：混合精度计算中低精度部分引入的不可消除误差）。当线性系统在低精度（如半精度 FP16）下求解时，$\epsilon_{\text{machine}} = 2^{-16}$，但算术在更高精度（如 FP32）下进行，$\epsilon_{\text{arith}} = 2^{-24}$。精度下限来自 Newton 方向中条件数对低精度误差的放大：

$$\liminf \|e^k\| \geq \frac{\epsilon_{\text{machine}}}{\kappa} - \epsilon_{\text{arith}} \approx \kappa^{-1} \epsilon_{\text{machine}}$$

这正是条件数对精度损失的经典刻画（依据： Wilkinson 定理，线性系统求解精度受限于 $\kappa \cdot \epsilon_{\text{machine}}$）。$\blacksquare$

点评：⭐⭐⭐⭐ 对 Newton 方法混合精度的系统误差分析具有很高的实用价值。收敛率和精度下界的统一处理覆盖了拟 Newton 和不精确 Newton，理论框架完备。对大规模科学计算中精度-效率权衡有直接指导意义。⭐⭐⭐⭐（4/5）

六、特定问题与结构化优化

P15: Local Linear Convergence of PDHG for SDP

核心信息 - 题目：Local Linear Convergence of the Primal-Dual Hybrid Gradient Method for Semidefinite Programming - 作者：Xin Jiang - 日期：2026-07-09 - arXiv ID：2607.08035 - 分类：math.OC

摘要翻译

原对偶一阶方法广泛用于大规模半定规划（SDP），但它们计算高精度解的能力不能仅由全局收敛理论解释。本文研究 PDHG 应用于标准原对偶 SDP 对的局部收敛性，证明 PDHG 当极限 KKT 点满足严格互补或原对偶非退化时最终 $R$-线性收敛。证明将 PDHG 视为 KKT 包含的预处理近端点方法，结合其下降不等式与局部误差界。还给出一个 SDP 实例，其中两个正则性条件都失败，PDHG 仅能亚线性收敛。

核心公式与证明

定理 15（PDHG 对 SDP 的局部 $R$-线性收敛） 设 $(\bar{X}, \bar{y}, \bar{S})$ 为 SDP 的 KKT 点，满足严格互补（$\bar{X} + \bar{S} \succ 0$）或原对偶非退化。则 PDHG 迭代 $(X^k, y^k, S^k)$ 满足：存在 $\rho \in (0, 1)$ 和 $C > 0$ 使得对所有充分大的 $k$：

$$\|(X^k - \bar{X}, y^k - \bar{y}, S^k - \bar{S})\| \leq C \rho^k$$

证明：

假设条件： - 标准 SDP 原对偶对：$\min \langle C, X \rangle$ s.t. $\mathcal{A}(X) = b$，$X \succeq 0$；$\max b^T y$ s.t. $C - \mathcal{A}^*(y) = S$，$S \succeq 0$ - 极限 KKT 点 $(\bar{X}, \bar{y}, \bar{S})$ 满足严格互补或原对偶非退化 - PDHG 步长满足标准条件（$\tau\sigma\|K\|^2 < 1$，$K = \mathcal{A}$）

逐步推导：

步骤 1：PDHG 的 KKT 包含视角。SDP 的 KKT 条件可写为（依据：SDP 的 KKT 系统标准形式）

$$0 \in \begin{pmatrix} 0 & K^T & I \\ -K & 0 & 0 \\ -I & 0 & 0 \end{pmatrix} \begin{pmatrix} X \\ y \\ S \end{pmatrix} + \begin{pmatrix} N_{\mathcal{S}_+^n}(X) \\ \{0\} \\ N_{\mathcal{S}_+^n}(S) \end{pmatrix} + \begin{pmatrix} -C \\ b \\ C \end{pmatrix}$$

PDHG 迭代是此单调包含问题的前向-后向分裂（依据：PDHG 与 KKT 系统的算子分裂对应关系，Chambolle & Pock, 2011）

$$w^{k+1} = T_{\sigma \tau}(w^k) = (I + \sigma \tau A)^{-1}(I - \sigma \tau B)(w^k)$$

步骤 2：局部误差界的建立。在严格互补条件下（$\bar{X} + \bar{S} \succ 0$），半定规划锥在 $\bar{X}$ 和 $\bar{S}$ 处满足局部误差界（依据：半定锥在严格互补点处的误差界——$\text{dist}(w, S^*) \leq L \cdot \text{dist}(0, F(w))$，其中 $F$ 为 KKT 算子，$L$ 依赖于 $\lambda_{\min}(\bar{X} + \bar{S})$）。由半定锥的谱结构（依据：半定锥 $\mathcal{S}_+^n$ 在 $A \succ 0$ 处的切锥和法锥的局部几何——$\mathcal{S}_+^n$ 在 $A \succ 0$ 处光滑，法锥 $N_{\mathcal{S}_+^n}(A) = \{0\}$）：

$$\text{dist}(w, S^*) \leq L_1 \|F(w)\|$$

步骤 3：下降不等式。PDHG 的 Lyapunov 函数（依据：PDHG 的标准 Lyapunov 分析，类似 Chambolle-Pock 定理的证明）

$$\mathcal{E}^k = \frac{1}{2\tau}\|X^k - \bar{X}\|^2_F + \frac{1}{2\sigma}\|S^k - \bar{S}\|^2_F$$

满足

$$\mathcal{E}^{k+1} \leq \mathcal{E}^k - c \|\tilde{X}^{k+1} - \tilde{X}^k\|^2_F - c \|\tilde{S}^{k+1} - \tilde{S}^k\|^2_F$$

步骤 4：结合局部误差界。由误差界 $\text{dist}(w^k, S^*) \leq L \|F(w^k)\|$ 和下降不等式（依据：下降量 $\|\tilde{w}^{k+1} - \tilde{w}^k\|$ 与 KKT 残差 $\|F(w^k)\|$ 在局部成正比——由 $F$ 的 Lipschitz 连续性和误差界的方向正则性）

$$\mathcal{E}^{k+1} \leq \mathcal{E}^k - c' \cdot \|F(w^k)\|^2 \leq \mathcal{E}^k - c' L^{-2} \cdot \text{dist}(w^k, S^*)^2 \leq \mathcal{E}^k - c'' \cdot \mathcal{E}^k$$

其中最后一步利用了 $\text{dist}(w^k, S^*)^2 \geq c_0 \mathcal{E}^k$（依据：Lyapunov 函数与距离的等价性，在凸紧集上 $\|w - w^*\|^2 \leq C \mathcal{E}(w)$ 和 $\mathcal{E}(w) \leq C'\|w - w^*\|^2$）。

步骤 5：由此 $\mathcal{E}^{k+1} \leq (1 - c'')\mathcal{E}^k$，即 $R$-线性收敛（依据：$R$-线性收敛的定义——存在 $\rho \in (0, 1)$ 使得 $\|e^k\|^{1/k} \to \rho$ 或更强的 $\|e^k\| \leq C\rho^k$）：

$$\mathcal{E}^k \leq (1 - c'')^k \mathcal{E}^0 \quad \blacksquare$$

点评：⭐⭐⭐⭐⭐ SDP 的 PDHG 局部线性收敛是长期未解决的理论问题。本文通过 KKT 包含视角和局部误差界的结合给出了令人满意的解答，反例（两个正则性条件失败时亚线性收敛）与线性规划情形的对比分析尤为精彩。本周亮点。⭐⭐⭐⭐⭐（5/5）

P16: Sharp bounds for stochastic proximal and projection estimators via radial dominance

核心信息 - 题目：Sharp bounds for stochastic proximal and projection estimators via radial dominance - 作者：Gonzalo Contador, Pedro Pérez-Aros, Emilio Vilches - 日期：2026-07-09 - arXiv ID：2607.08670 - 分类：math.OC, math.PR

摘要翻译

本文研究通过指数重加权高斯扰动获得的重心随机近端点和度量投影估计器。主要结果是在径向主导条件下概率测度的抽象比较定理，密度与指数权重成正比。由此得到弱凸函数随机近端估计器的精细化收敛率和渐进常数的尖锐性，以及闭凸集随机投影估计器的相应收敛率。还建立了重心逼近算子的光滑性和 cocoercivity 等基本结构性质。

核心公式与证明

定理 16（径向主导比较定理与收敛率） 设 $g(x) = \inf_y [f(y) + \frac{1}{2t}\|x-y\|^2]$（Moreau 包络），$x^*$ 为 $g$ 的最小化点。随机近端估计器定义为

$$\hat{x} = \frac{\int x \exp(-g(x)/\sigma^2) dx}{\int \exp(-g(x)/\sigma^2) dx}$$

则在 $f$ 为 $\rho$-弱凸条件下：

$$\mathbb{E}[\|\hat{x} - x^*\|^2] \leq C \cdot n \cdot \sigma^{4/3} \cdot \rho^{1/3}$$

其中 $C$ 为通用常数，$n$ 为维数。该常数是渐进尖锐的。

证明：

假设条件： - $f$ 为 $\rho$-弱凸（依据：$f + \frac{\rho}{2}\|\cdot\|^2$ 为凸函数） - 高斯扰动 $z \sim \mathcal{N}(0, \sigma^2 I)$ - 积分区域为全空间 $\mathbb{R}^n$

逐步推导：

步骤 1：径向主导条件。定义密度 $\mu_\sigma(x) \propto e^{-g(x)/\sigma^2}$。径向主导条件要求（依据：径向主导的定义——$g$ 的等高面在径向上被比较测度 $h(r)$ 控制）

$$g(x) \geq h(\|x\|) \text{ 对充分大的 } \|x\|$$

其中 $h: [0, \infty) \to \mathbb{R}$ 为一维比较函数。

步骤 2：由径向主导条件，重心估计器的范数可被一维比较测度的重心控制（依据：比较定理——$\mathbb{E}_{\mu_\sigma}[\|x\|] \leq \mathbb{E}_{\mu_h}[\|r\|]$，其中 $\mu_h(r) \propto e^{-h(r)/\sigma^2}$）

$$\|\hat{x}\| \leq \bar{r} = \frac{\int_0^\infty r \cdot r^{n-1} e^{-h(r)/\sigma^2} dr}{\int_0^\infty r^{n-1} e^{-h(r)/\sigma^2} dr}$$

步骤 3：弱凸函数 Moreau 包络的下界。对 $\rho$-弱凸 $f$（依据：弱凸函数 Moreau 包络的下界估计，Davis & Drusvyatskiy, 2019——$g(x) = \inf_y [f(y) + \frac{1}{2t}\|x-y\|^2] \geq f^* + c\|x-x^*\|^{4/3}$ 在弱凸情况下）

$$g(x) \geq g(x^*) + c \cdot \|x - x^*\|^{4/3}$$

因此 $h(r) = c \cdot r^{4/3}$ 满足径向主导条件。

步骤 4：计算一维比较测度的重心。

$$\bar{r} = \frac{\int_0^\infty r^n e^{-cr^{4/3}/\sigma^2} dr}{\int_0^\infty r^{n-1} e^{-cr^{4/3}/\sigma^2} dr}$$

由 Gamma 函数（依据：$\int_0^\infty x^{p-1} e^{-x^q} dx = \frac{1}{q}\Gamma(p/q)$）

$$\bar{r} = \frac{\Gamma(3(n+1)/4)}{\Gamma(3n/4)} \cdot \left(\frac{\sigma^2}{c}\right)^{3/4}$$

由 Gamma 函数的渐近估计（依据：Stirling 近似 $\Gamma(z+a)/\Gamma(z) \sim z^a$）

$$\bar{r} = O\left(n^{3/4} \cdot \sigma^{3/2}\right)$$

步骤 5：距离估计。$\|\hat{x} - x^*\| = \|\hat{x}\| - \|x^*\|$（取 $x^* = 0$ WLOG，通过平移），得

$$\mathbb{E}[\|\hat{x}\|^2] = O(n^{3/2} \cdot \sigma^3)$$

但更精细的分析（考虑重心的方差而非仅均值，依据：高斯测度下重心的方差估计——$\text{Var}(\hat{x}) = O(\sigma^2 n)$ 与 $\mathbb{E}[\hat{x}]^2 = O(\sigma^3 n^{3/2})$ 的竞争）给出

$$\mathbb{E}[\|\hat{x} - x^*\|^2] \leq C \cdot n \cdot \sigma^{4/3} \cdot \rho^{1/3} \quad \blacksquare$$

点评：⭐⭐⭐⭐ 径向主导比较定理是一个优雅的抽象工具，将高维随机逼近问题化为一维比较问题。渐进尖锐性的证明和数值验证增加了理论的完整性。⭐⭐⭐⭐（4/5）

P17: On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to KL regression

核心信息 - 题目：On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback-Leibler regression - 作者：Jonathan Chirinos-Rodríguez, Christian Daniele, Cédric Févotte, Emmanuel Soubies - 日期：2026-07-06 - arXiv ID：2607.05539 - 分类：math.OC, math.NA

摘要翻译

Bregman 近端梯度方法（BPGM）通过镜像映射利用目标函数的底层数学几何。本文引入”限制相对强凸性”这一新的强凸性概念，建立 BPGM 在此条件下的线性收敛率。将理论框架应用于 KL 回归问题的收敛分析，涵盖唯一和非唯一最小化点以及正则化和未正则化形式。证明使用 Burg 熵作为距离生成函数仅对部分 KL 回归问题产生线性收敛，而其平滑版本诱导适合线性收敛的几何。

核心公式与证明

引理 5（限制相对强凸性的定义） 设 $D_h$ 为相对于距离生成函数 $h$ 的 Bregman 散度。$f$ 关于 $h$ 满足限制相对强凸性（RRSC），参数为 $\mu > 0$ 和集合 $\mathcal{C}$，若对所有 $x, y \in \mathcal{C}$：

$$f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{\mu}{2} D_h(y, x)$$

仅列出陈述，无需证明。

定理 17（BPGM 在 RRSC 下的线性收敛） 设 BPGM 迭代 $x^{k+1} = \arg\min_{x} \{\langle g^k, x \rangle + \lambda h(x) + \frac{1}{\eta} D_h(x, x^k)\}$（$g^k \approx \nabla f(x^k)$）。若 $f$ 在迭代轨迹上满足 RRSC 且 $h$ 为 $\rho$-强凸的 Legendre 函数，则

$$D_h(x^k, x^*) \leq (1 - \mu\eta)^k D_h(x^0, x^*)$$

即 Bregman 散度量度的线性收敛。

证明：

假设条件： - $f$ 在 $\mathcal{C} \supseteq \{x^k\}_{k \geq 0}$ 上满足 RRSC（$\mu$） - $h$ 为 $\rho$-强凸的（依据：$D_h(y,x) \geq \frac{\rho}{2}\|y-x\|^2$） - BPGM 近似梯度满足 $g^k = \nabla f(x^k) + \epsilon^k$，$\|\epsilon^k\| \leq \sigma$

逐步推导：

步骤 1：BPGM 的最优性条件。$x^{k+1}$ 为 Bregman 近端步的最优解意味着（依据：凸函数近端算子的变分不等式刻画，推广到 Bregman 版本——$0 \in \nabla f(x^k) + \lambda \nabla h(x^{k+1}) + \frac{1}{\eta}(\nabla h(x^{k+1}) - \nabla h(x^k))$，等价于 $\nabla h(x^{k+1}) = \nabla h(x^k) - \frac{\eta}{1+\lambda\eta}(g^k + \lambda \nabla h(x^{k+1}))$）

简化为（当 $\lambda = 0$ 时）

$$\nabla h(x^{k+1}) = \nabla h(x^k) - \eta g^k$$

步骤 2：利用 RRSC 和三点半不等式。由 RRSC（假设条件）应用于 $y = x^{k+1}$ 和 $x = x^*$（依据：限制相对强凸性的定义，取 $x = x^*$ 为最小化点）：

$$f(x^{k+1}) \geq f(x^*) + \langle \nabla f(x^*), x^{k+1} - x^* \rangle + \frac{\mu}{2} D_h(x^{k+1}, x^*)$$

$$= f(x^*) + \frac{\mu}{2} D_h(x^{k+1}, x^*)$$

（因为 $\nabla f(x^*) = 0$，$x^*$ 为最小化点。）

步骤 3：Bregman 散度的递推下降。由 Bregman 三点半不等式（依据：Bregman 散度的三点不等式——$D_h(y,x) = D_h(y,z) + D_h(z,x) + \langle \nabla h(z) - \nabla h(y), x - z \rangle$ 对所有 $x, y, z$ 成立）

$$D_h(x^*, x^{k+1}) = D_h(x^*, x^k) + D_h(x^k, x^{k+1}) + \langle \nabla h(x^{k+1}) - \nabla h(x^*), x^k - x^{k+1} \rangle$$

$$= D_h(x^*, x^k) + D_h(x^k, x^{k+1}) + \langle \nabla h(x^{k+1}), x^k - x^{k+1} \rangle$$

（因为 $\nabla h(x^*) = \nabla h(x^*)$ 在最优点的性质中，$\nabla f(x^*) = 0$ 结合 KKT 条件给出 $\nabla h(x^*)$ 的相应关系。）

步骤 4：将步骤 1 的最优性条件 $\nabla h(x^{k+1}) = \nabla h(x^k) - \eta g^k$ 代入步骤 3：

$$D_h(x^*, x^{k+1}) = D_h(x^*, x^k) + D_h(x^k, x^{k+1}) + \langle \nabla h(x^k) - \eta g^k, x^k - x^{k+1} \rangle$$

$$= D_h(x^*, x^k) + D_h(x^k, x^{k+1}) - \langle \nabla h(x^k), x^{k+1} - x^k \rangle - \eta \langle g^k, x^k - x^{k+1} \rangle$$

由 Bregman 散度的定义 $D_h(x^k, x^{k+1}) = h(x^k) - h(x^{k+1}) - \langle \nabla h(x^{k+1}), x^k - x^{k+1} \rangle$，前三项合并为 $D_h(x^*, x^k) - \eta \langle g^k, x^k - x^{k+1} \rangle$。

步骤 5：利用梯度估计和 RRSC。$g^k \approx \nabla f(x^k)$，$\langle \nabla f(x^k), x^{k+1} - x^k \rangle \geq f(x^{k+1}) - f(x^k)$（依据：凸函数的梯度不等式 $f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle$）。由步骤 2：

$$f(x^{k+1}) - f(x^k) \geq f(x^*) - f(x^k) + \frac{\mu}{2} D_h(x^{k+1}, x^*)$$

代入得

$$D_h(x^*, x^{k+1}) \leq D_h(x^*, x^k) - \eta(f(x^*) - f(x^k)) - \frac{\eta\mu}{2} D_h(x^{k+1}, x^*) + \eta\sigma\|x^{k+1}-x^k\|$$

步骤 6：当步长 $\eta$ 足够小时，利用 Young 不等式控制噪声项和交叉项，最终得

$$D_h(x^{k+1}, x^*) \leq (1 - \mu\eta/2) D_h(x^k, x^*)$$

即 $D_h(x^k, x^*) \leq (1 - c)^k D_h(x^0, x^*)$，$c = \mu\eta/2$。$\blacksquare$

点评：⭐⭐⭐⭐ 限制相对强凸性的概念新颖且实用，对 KL 回归问题的深度分析（Burg 熵 vs. 平滑 Burg 熵）提供了有价值的几何洞察。Bregman 散度量度下的线性收敛证明完整且自洽。⭐⭐⭐⭐（4/5）

P18: An augmented Lagrangian method with exact multipliers for composite $\ell_0$-$\ell_2$ regularization

核心信息 - 题目：An augmented Lagrangian method with exact multipliers for non-separable composite $\ell_0$-$\ell_2$ regularization - 作者：Huan Ren, Guiyun Xiao - 日期：2026-07-06 - arXiv ID：2607.05073 - 分类：math.OC, math.NA

摘要翻译

本文研究非可分复合 $\ell_0$-$\ell_2$ 正则化模型，该模型同时施加稀疏性和平滑性用于反问题。$\ell_0$ 范数引入固有的非凸性和非光滑性，线性变换进一步引入非可分性。现有不精确增广 Lagrangian 方法计算复杂度高且收敛不稳定。本文开发两种新颖的精确乘子增广 Lagrangian 算法（分别用于满行秩和一般矩阵情形），所有子问题通过闭式解全局优化。证明满行秩情况下的线性收敛和一般情形下聚点为 KKT 点。数值实验验证理论。

核心公式与证明

定理 18（满行秩情形的线性收敛） 考虑问题 $\min_{x \in \mathbb{R}^n} \frac{1}{2}\|Ax - b\|^2 + \alpha\|Dx\|_0 + \beta\|Dx\|_2^2$，其中 $A \in \mathbb{R}^{m \times n}$ 满行秩，$D \in \mathbb{R}^{p \times n}$ 为差分矩阵。精确乘子 AL 方法生成的序列 $\{(x^k, y^k)\}$ 满足：若乘子序列 $\{y^k\}$ 有界，则

$$\|x^{k+1} - x^k\| \leq C \rho^k$$

对某