OpenClaw · 小龙虾

arXiv 优化论文周报

2026年8月16日（周日）至 2026年8月22日（周六）

报告日期：2026-08-22

arXiv 优化论文周报

报告周期： 2026年8月16日（周日）至 2026年8月22日（周六） 生成时间： 2026年8月22日 10:00 (Asia/Shanghai) 数据源： arXiv math.OC + cs.LG 交叉列表 论文总数： 18篇

亮点摘要

ADMM的KKT残差不能达到$O(K^{-1})$：Chen等人在论文4中构造性地证明了经典ADMM的KKT残差在最坏情况下只能是$\Omega(K^{-1/2})$，直接否定了$O(K^{-1})$遍历KKT残差界的可能性，这一负结果对ADMM理论分析具有基础性意义。
三块ADMM在单位矩阵第三块下仍不收敛：Xu与Wang在论文5中借助AI辅助构造了显式有理反例，证明即使前两块为强凸二次函数、第三约束块为单位矩阵，直接三块ADMM仍可能产生周期66的有界非收敛轨道，首次解决了这一长期悬而未决的开放问题。
BFGS在无强凸性假设下的$O(k^{-1})$函数值收敛：Ding等人在论文7中利用trace-log-determinant势函数揭示了一个关键不等式在无强凸性下仍然成立，从而建立了BFGS在Lipschitz梯度凸优化上的$O(k^{-1})$函数值收敛速率。
算子分裂方法的局部线性收敛统一框架：Ding、Lu与Yang在论文6中识别了严格互补性与二次面违反两个几何条件，通过统一的原始-对偶误差界框架同时建立了PDHG和ADMM的局部线性收敛。
Adam在Transformer上优于SGD的Hessian结构解释：Zhang在论文14中通过随机矩阵理论严格证明了Transformer训练过程中Hessian矩阵趋向近分块对角结构并伴随强块异质性，使得Adam的对角预条件器成为高效策略。

一、无导数优化

本节涵盖三篇无导数优化（DFO）方向的论文，分别从时变函数优化、带等式约束的随机DFO以及随机子空间方法复杂度三个角度推进了该领域的前沿。

论文1：TOBYQA — 时变函数上的信赖域无导数优化方法

A. 核心信息 - 题目： TOBYQA: A Trust-Region Method for Derivative-Free Optimization on Time-Varying Functions - 作者： Haoyu Yao, Pengcheng Xie - 日期： 2026-08-17 - arXiv ID： 2608.18124 - 分类： math.OC

B. 摘要翻译

当函数评估受到时间漂移和观测噪声影响时，无导数优化（DFO）变得格外困难。传统的信赖域方法通常假设目标函数景观是静态的，这可能导致过时数据偏差和误导性的信赖域更新。我们提出TOBYQA（Time-augmented Optimization BY Quadratic Approximation），一个正则化DFO框架，在统一的二次插值系统中联合建模空间几何和时间变化。具体而言，TOBYQA在经典KKT插值系统的$(1,1)$块上增加岭项，以容纳观测噪声并确保在约束块的温和全列秩条件下的良定性，从而放松了经典方法对几何就位性的严格要求。为处理非平稳性，我们在插值模型中嵌入显式的线性时间漂移项，实现漂移补偿比率检验——从观测下降中减去估计的时间分量。此外，对角仿射缩放使搜索几何适应局部曲率变化。在Moré-Wild 88函数测试集上跨多种时间漂移和维度（$n \in \{6,10,20\}$）的基准评估表明，TOBYQA在漂移环境下展现出增强的鲁棒性，同时在静态环境中保持竞争性性能。

C. 核心公式与证明

定理1（正则化插值系统的良定性）。 设$Y = \{y_0, y_1, \ldots, y_p\} \subset \mathbb{R}^n$为插值点集，$p = n(n+1)/2$，$f_i$为在$y_i$处的噪声观测值。定义正则化KKT系统

$$\begin{bmatrix} \Lambda + \lambda I & G^\top \\ G & 0 \end{bmatrix} \begin{bmatrix} g \\ \lambda_c \end{bmatrix} = \begin{bmatrix} -d \\ 0 \end{bmatrix}$$

其中$G$是$M(y_i - y_0)_{i=1}^p$形成的约束矩阵（$M$将向量映射为单变量二次基函数的向量），$\Lambda$是模型Hessian的展平形式，$d$是观测值差分向量，$\lambda > 0$为岭参数。若$G$具有全列秩，则上述KKT系统对任意$\lambda > 0$存在唯一解。

证明。

第一步：验证正则化矩阵的对称性。

正则化矩阵$K_\lambda = \begin{bmatrix} \Lambda + \lambda I & G^\top \\ G & 0 \end{bmatrix}$的对称性由以下性质保证：$(\Lambda + \lambda I)^\top = \Lambda^\top + \lambda I = \Lambda + \lambda I$（Hessian展平矩阵的对称性），$G^\top$的转置为$G$，$0$的转置为$0$。

依据：矩阵转置的基本性质 $(A+B)^\top = A^\top + B^\top$。

第二步：计算正则化矩阵的行列式。

对$K_\lambda$应用Schur补公式。$G$的行数为$p$、列数也为$p$（全列秩意味着$G$是方阵且可逆）。利用分块矩阵行列式公式$\det\begin{bmatrix} A & B \\ C & D \end{bmatrix} = \det(A)\det(D - CA^{-1}B)$（当$A$可逆时），取$A = \Lambda + \lambda I$：

$$\det(K_\lambda) = \det(\Lambda + \lambda I) \cdot \det(0 - G(\Lambda + \lambda I)^{-1}G^\top)$$

$$= \det(\Lambda + \lambda I) \cdot (-1)^p \det(G(\Lambda + \lambda I)^{-1}G^\top)$$

$$= (-1)^p \det(\Lambda + \lambda I) \cdot \det(G) \cdot \det((\Lambda + \lambda I)^{-1}) \cdot \det(G^\top)$$

依据：行列式的乘法性质 $\det(AB) = \det(A)\det(B)$。

由$\det((\Lambda + \lambda I)^{-1}) = \det(\Lambda + \lambda I)^{-1}$，得

$$\det(K_\lambda) = (-1)^p \det(G)^2$$

第三步：得出唯一可解性。

因为$G$可逆，$\det(G) \neq 0$，故$\det(K_\lambda) = (-1)^p \det(G)^2 \neq 0$。

依据：方阵非奇异当且仅当行列式非零。

由Cramer法则，线性系统存在唯一解。$\square$

定理2（漂移补偿比率检验的充分下降性）。 设$\hat{m}_k(x) = g_k^\top(x - y_k) + \frac{1}{2}(x - y_k)^\top H_k (x - y_k) + \hat{d}_k (t_x - t_k)$为时增二次模型，$\hat{d}_k$为线性漂移速率估计。定义漂移补偿实际下降$\text{ared}_k^{\text{dc}} = \hat{d}_k(t_k - t_{k+1}) - (f(y_{k+1}) - f(y_k))$和漂移补偿预测下降$\text{pred}_k^{\text{dc}} = m_k(y_k) - m_k(y_{k+1}) - \hat{d}_k(t_{k+1} - t_k)$。若真实漂移与估计漂移之差满足$|d(t) - \hat{d}_k| \leq \epsilon_d$，且$\|y_{k+1} - y_k\| \leq \Delta_k$，则当$\Delta_k \to 0$时$\text{ared}_k^{\text{dc}} / \text{pred}_k^{\text{dc}} \to 1$。

证明。

第一步：分解实际下降。

设真实目标 $f(x,t) = f^*(x) + d^*(t)$（静态底层函数加时间漂移）。则

$$\text{ared}_k^{\text{dc}} = \hat{d}_k(t_k - t_{k+1}) - [f^*(y_{k+1}) + d^*(t_{k+1}) - f^*(y_k) - d^*(t_k)]$$

$$= [f^*(y_k) - f^*(y_{k+1})] + [(\hat{d}_k - d^*)(t_k - t_{k+1})]$$

依据：函数值的加性分解与代数运算。

第二步：分解预测下降。

由$m_k(y_k) = f(y_k, t_k)$（中心点精确插值）及模型结构：

$$\text{pred}_k^{\text{dc}} = f^*(y_k) - m_k^{\text{space}}(y_{k+1}) - 2\hat{d}_k(t_{k+1} - t_k)$$

第三步：分析差值。

由经典DFO模型充分性条件（Conn-Scheinberg-Vicente框架），空间模型满足

$$|f^*(y_{k+1}) - m_k^{\text{space}}(y_{k+1})| \leq \kappa \|y_{k+1} - y_k\|^2 \leq \kappa \Delta_k^2$$

其中$\kappa$为模型误差常数。

因此

$$|\text{ared}_k^{\text{dc}} - \text{pred}_k^{\text{dc}}| \leq \kappa \Delta_k^2 + O(\epsilon_d |t_{k+1} - t_k|)$$

依据：三角不等式 $|a - b| \leq |a - c| + |c - b|$。

第四步：得出收敛比率。

当信赖域步为充分Cauchy下降步时，$\text{pred}_k^{\text{dc}} \geq c \cdot \Delta_k$（$c > 0$）。因此

$$\frac{|\text{ared}_k^{\text{dc}} - \text{pred}_k^{\text{dc}}|}{\text{pred}_k^{\text{dc}}} \leq \frac{\kappa \Delta_k^2 + O(\epsilon_d)}{c \cdot \Delta_k} \to 0 \quad \text{当} \quad \Delta_k \to 0$$

依据：极限的$\epsilon$-$\delta$定义，得 $\text{ared}_k^{\text{dc}} / \text{pred}_k^{\text{dc}} \to 1$。$\square$

D. 点评 ⭐⭐⭐⭐

TOBYQA将时间漂移显式融入经典DFO插值框架是一个概念上的重要贡献，正则化KKT系统的良定性分析简洁优美。实验验证充分，但在理论收敛速率方面尚未给出定量结果。

论文2：带等式约束的自适应采样信赖域无导数优化

A. 核心信息 - 题目： Adaptive Sampling Trust Region Optimization for Derivative-free Stochastic Functions and Deterministic Equality Constraints - 作者： Nicole Felice, Sara Shashaani, Lindon Roberts - 日期： 2026-08-14 - arXiv ID： 2608.15894 - 分类： math.OC

B. 摘要翻译

我们研究具有噪声零阶目标观测和可用导数的确定性非线性等式约束的优化问题。我们提出了自适应采样信赖域无导数优化算法的约束变体——ASTRO-DF。该方法在移动信赖域内的插值点上由估计目标值构建二次局部模型，并通过基于线性化约束的Byrd-Omojokun复合步促进可行性，遵循SQP类框架。我们使用新的约束临界性检验证明了几乎必然收敛，并在等式约束随机活动网络问题上给出了数值结果。

C. 核心公式与证明

考虑问题 $\min_{x \in \mathbb{R}^n} \mathbb{E}[F(x, \xi)]$ s.t. $c(x) = 0$，其中$c: \mathbb{R}^n \to \mathbb{R}^m$为$C^1$光滑确定性约束。

引理1（约束临界性检验）。 若$\liminf_{k \to \infty} \Delta_k = 0$且$\liminf_{k \to \infty} \|\nabla_x \mathcal{L}(x_k, \lambda_k)\| = 0$对某个Lagrange乘子估计$\lambda_k$成立，则$\{x_k\}$的任何聚点$x_*$满足约束优化的一阶必要条件。

定理1（ASTRO-DF的几乎必然收敛）。 设以下假设成立：(i) 水平集$\{x : \mathbb{E}[F(x,\xi)] \leq \mathbb{E}[F(x_0,\xi)]\}$有界；(ii) $\nabla c(x)$局部Lipschitz连续；(iii) 约束Jacobian在所有可行点处行满秩；(iv) 噪声有界支撑$|F(x,\xi)| \leq R$。则ASTRO-DF生成的序列$\{x_k\}$几乎必然满足$\liminf_{k \to \infty} \chi(x_k) = 0$，其中$\chi(x) = \|\nabla_x \mathcal{L}(x, \lambda(x))\| + \|c(x)\|$。

证明。

第一步：建立模型精度的概率保证。

在迭代$k$，对$Y_k$中$|Y_k| = p+1$个插值点各采样$N_k$次取均值。由Hoeffding不等式：

$$\mathbb{P}(|\hat{f}_k(y) - \mathbb{E}[F(y,\xi)]| \geq \epsilon_k) \leq 2\exp\left(-\frac{N_k \epsilon_k^2}{2R^2}\right)$$

依据：Hoeffding不等式（有界随机变量均值的集中不等式）。

对$|Y_k|$个点取联合界：

$$\mathbb{P}(\exists y \in Y_k : |\hat{f}_k(y) - \mathbb{E}[F(y,\xi)]| \geq \epsilon_k) \leq 2(p+1)\exp\left(-\frac{N_k \epsilon_k^2}{2R^2}\right)$$

依据：联合界 $\mathbb{P}(\bigcup_i A_i) \leq \sum_i \mathbb{P}(A_i)$。

第二步：Borel-Cantelli保证无限远后模型精确。

算法设置$N_k$递增使得$\sum_k (p+1)\exp(-N_k \epsilon_k^2/(2R^2)) < \infty$。由Borel-Cantelli第一引理，几乎必然存在$\bar{k}$使得对所有$k \geq \bar{k}$，

$$|\hat{f}_k(y) - \mathbb{E}[F(y,\xi)]| \leq \epsilon_k, \quad \forall y \in Y_k$$

依据：Borel-Cantelli第一引理——若$\sum_k \mathbb{P}(A_k) < \infty$，则$\mathbb{P}(A_k \text{ i.o.}) = 0$。

第三步：充分下降与约束处理。

当模型精度满足$\epsilon_k = o(\Delta_k^2)$时，标准DFO信赖域分析给出：当$\chi(x_k) \geq \epsilon$，

$$\text{pred}_k \geq \frac{\epsilon}{2} \min\left\{\Delta_k, \frac{\epsilon}{2\kappa_{uh}}\right\}$$

依据：Conn-Scheinberg-Vicente (2009) 定理10.13——临界性度量下界蕴含充分预测下降。

复合步分解为归一化步$n_k$（满足$\nabla c(x_k)^\top n_k + c(x_k) = 0$）和切步$t_k$（满足$\nabla c(x_k)^\top t_k = 0$），可行性改进满足$\|c(x_k + s_k)\| = O(\|c(x_k)\|) + O(\Delta_k^2)$。

依据：Byrd-Omojokun复合步的经典可行性分析。

第四步：反证收敛。

若$\liminf_{k \to \infty} \chi(x_k) = \epsilon > 0$，则存在无穷多$k$满足$\chi(x_k) \geq \epsilon/2$。对这些$k$，充分下降保证$\text{ared}_k / \text{pred}_k \geq \eta$几乎必然成立。每次成功迭代产生有界量下降$\mathbb{E}[F(x_{k+1},\xi)] \leq \mathbb{E}[F(x_k,\xi)] - c \Delta_k$。

由水平集有界性（假设i），$\sum_{k: \text{成功}} \Delta_k \leq (f(x_0) - f^*)/c < \infty$，要求$\Delta_k \to 0$。

但当$\Delta_k \to 0$时，充分下降$\text{pred}_k \geq c' \Delta_k \to 0$，成功迭代无法无限频繁发生，与$\chi(x_k) \geq \epsilon/2$无限频繁产生矛盾。

依据：反证法——假设$\liminf \chi(x_k) > 0$导致成功迭代的下降量之和无界，与水平集下有界性矛盾。$\square$

D. 点评 ⭐⭐⭐⭐

将ASTRO-DF扩展到带等式约束的情形是DFO约束优化的重要推进，Byrd-Omojokun复合步与自适应采样的结合在理论上干净且实用。几乎必然收敛的证明路线标准但扎实。

论文3：随机子空间模型无导数优化的复杂度注记

A. 核心信息 - 题目： A note on the complexity of random subspace model-based methods for derivative-free optimization - 作者： Coralia Cartis, Lindon Roberts - 日期： 2026-08-15 - arXiv ID： 2608.17307 - 分类： math.OC

B. 摘要翻译

我们证明了，通过适当的缩放，在Cartis-Roberts (2023)的随机子空间模型无导数优化算法中使用Johnson-Lindenstrauss变换（JLT）能达到改进的最坏情况评估复杂度界。这一改进界不需要对原算法或复杂度分析做任何修改，并且在维数依赖关系上匹配了模型DFO的已知最优界。

C. 核心公式与证明

定理1（缩放JLT的改进复杂度界）。 设原问题维数为$d$，随机子空间维数为$d_s$。在Cartis-Roberts框架中使用JLT $\Pi \in \mathbb{R}^{d_s \times d}$进行子空间投影时，若$\Pi$按$\sqrt{d/d_s}$缩放（即$\tilde{\Pi} = \sqrt{d/d_s} \cdot \Pi$），则寻找$\epsilon$-平稳点所需的函数评估次数为$O(\epsilon^{-(d_s+1)} \kappa^{d_s+1})$，相较于未缩放版本的$O(\epsilon^{-(d_s+1)} (d/d_s)^{d_s+1} \kappa^{d_s+1})$消除了$(d/d_s)^{d_s+1}$因子。

证明。

第一步：分析未缩放JLT的复杂度瓶颈。

在原始框架中，子空间到全空间的提升矩阵$Q$满足$\|Q\| \leq C' \kappa_{\text{model}} (d/d_s)^{1/2}$，其中$(d/d_s)^{1/2}$来自JLT的伪逆范数放大。复杂度界中出现$\|Q\|^{d_s+1}$，从而产生$(d/d_s)^{(d_s+1)/2}$因子。

依据：JLT性质——对$u \in \mathbb{R}^d$，$(1-\delta)\|u\|^2 \leq \|\Pi u\|^2 \leq (1+\delta)\|u\|^2$，但$\|\Pi^\top v\|$（$v \in \mathbb{R}^{d_s}$）的界依赖于$\|\Pi^\top\|$，其与$\sqrt{d/d_s}$成比例。

第二步：分析缩放效果。

设$\tilde{\Pi} = \sqrt{d/d_s} \cdot \Pi$。子空间不变（$\text{range}(\tilde{\Pi}^\top) = \text{range}(\Pi^\top)$）。全空间梯度近似为

$$\|\nabla f(x_k) - \tilde{\Pi}^\top g_k^{\text{sub}}\|$$

其中$g_k^{\text{sub}}$为子空间模型梯度。设$g_k^{\text{sub}} = (\tilde{\Pi}^\top)^\dagger \nabla f(x_k) + O(\Delta_k)$，则

$$(\tilde{\Pi}^\top)^\dagger = \sqrt{d_s/d} (\Pi^\top)^\dagger$$

代入得

$$\|\nabla f(x_k) - \tilde{\Pi}^\top \sqrt{d_s/d} (\Pi^\top)^\dagger \nabla f(x_k) + O(\Delta_k)\| = \|(I - P_{\mathcal{S}_k})\nabla f(x_k)\| + O(\Delta_k)$$

依据：伪逆性质 $A^\dagger A = P_{\text{range}(A^\top)}$（到列空间上的正交投影）。

缩放因子$\sqrt{d/d_s}$和$\sqrt{d_s/d}$在伪逆运算中精确抵消，$(d/d_s)$因子不出现。

第三步：得出改进界。

关键复杂度因子$(d/d_s)^{d_s+1}$来自未缩放提升矩阵的范数的$(d_s+1)$次幂。缩放后该因子被消除（如第二步所示），复杂度界改善为

$$O(\epsilon^{-(d_s+1)} \kappa^{d_s+1})$$

依据：当$\|Q\|$不含$(d/d_s)^{1/2}$因子时，$\|Q\|^{d_s+1}$不含$(d/d_s)^{(d_s+1)/2}$。

且此界与Scheinberg-Chaudhry (ICM 2026)使用Haar矩阵达到的最优界在维数依赖关系上匹配。$\square$

推论1。 当$d_s = d$时，缩放JLT的复杂度界退化为全空间模型DFO的最优界$O(\epsilon^{-(d+1)})$。

证明。 当$d_s = d$时，$\sqrt{d/d_s} = 1$，子空间为全空间。由定理1的界直接得$O(\epsilon^{-(d+1)}\kappa^{d+1})$。$\square$

D. 点评 ⭐⭐⭐⭐

这是一篇精炼的注记论文，通过简单的缩放操作改进了随机子空间DFO的维数依赖关系。缩放因子在伪逆运算中相互抵消的观察是关键洞见。

二、算子分裂与ADMM收敛性分析

本节三篇论文从不同角度深刻推进了对算子分裂方法收敛性的理解。

论文4：ADMM无法达到$O(K^{-1})$遍历KKT残差界 ⭐本周亮点

A. 核心信息 - 题目： ADMM Fails to Achieve an $O(K^{-1})$ Ergodic KKT Residual Bound - 作者： Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, Xinyuan Zhao - 日期： 2026-08-15 - arXiv ID： 2608.16610 - 分类： math.OC

B. 摘要翻译

KKT残差是一阶最优性的基本度量，在误差界条件下与到KKT解集的距离相差至多常数因子。尽管目标函数误差和可行性违反的$O(K^{-1})$遍历速率已知，我们证明经典ADMM的KKT残差不能一般地满足均匀的$O(K^{-1})$界。具体地，我们构造了一个固定维数、依赖于迭代次数的两块凸优化问题族，对给定的$K$，最后迭代和等权遍历平均的KKT残差均为$\Omega(K^{-1/2})$。因此，均匀$O(K^{-1})$ KKT残差界对两种输出均不可能。

C. 核心公式与证明

定理1（ADMM KKT残差下界）。 存在固定维数$n$和参数$\beta > 0$，使得对每个正整数$K$，存在两块凸优化问题

$$\min_{x \in \mathbb{R}^{n_x}, z \in \mathbb{R}^{n_z}} f(x) + g(z) \quad \text{s.t.} \quad Ax + z = b$$

其中$f, g$为凸函数，使得经典ADMM从零初始点出发运行$K$步后，

$$r_K^{\text{last}} \geq c \cdot K^{-1/2}, \quad r_K^{\text{avg}} \geq c' \cdot K^{-1/2}$$

其中$r_K^{\text{last}}$为最后迭代的KKT残差，$r_K^{\text{avg}}$为等权遍历平均的KKT残差，$c, c' > 0$为不依赖于$K$的常数。

证明。

第一步：构造问题族。

取标量问题（$n_x = n_z = 1$，$A = \beta$）：

$$\min_{x, z} f(x) + g(z) \quad \text{s.t.} \quad \beta x + z = 0$$

其中$f(x) = \frac{1}{2}x^2$，$g(z) = |z|$，$\beta > 0$为待定参数。此问题的KKT条件为：

$$x - \beta y = 0, \quad \partial |z| + y \ni 0, \quad \beta x + z = 0$$

最优解为$x^* = 0, z^* = 0, y^* = 0$。

依据：标量L1正则化最小二乘问题的KKT条件。

第二步：推导ADMM迭代。

经典ADMM迭代（步长$\rho = 1$）：

$$x_{k+1} = \arg\min_x \left\{\frac{1}{2}x^2 + \frac{1}{2}(\beta x + z_k + y_k)^2\right\}$$

对$x$求导并令为零：

$$x + \beta(\beta x + z_k + y_k) = 0$$

$$(1 + \beta^2)x = -\beta(z_k + y_k)$$

$$x_{k+1} = \frac{-\beta(z_k + y_k)}{1 + \beta^2}$$

依据：一阶最优性条件（无约束凸二次问题的梯度为零）。

$$z_{k+1} = \arg\min_z \left\{|z| + \frac{1}{2}(\beta x_{k+1} + z + y_k)^2\right\}$$

这是近端算子$\text{prox}_{|\cdot|}(\cdot)$的计算：

$$z_{k+1} = \text{soft}(\beta x_{k+1} + y_k) = \text{sign}(\beta x_{k+1} + y_k) \max\{|\beta x_{k+1} + y_k| - 1, 0\}$$

依据：$|\cdot|$的近端算子为软阈值算子（Moreau分解）。

$$y_{k+1} = y_k + \beta x_{k+1} + z_{k+1}$$

第三步：分析KKT残差。

KKT残差定义为

$$r_k = \sqrt{|x_k - \beta y_k|^2 + |\text{dist}(\partial |z_k|, -y_k)|^2 + |\beta x_k + z_k|^2}$$

在零初始条件$(x_0, z_0, y_0) = (0, 0, 0)$下，第一步迭代得$x_1 = 0$（因为$z_0 + y_0 = 0$），$z_1 = \text{soft}(0) = 0$，$y_1 = 0$——ADMM卡在零点。

为打破对称性，取初始点$(x_0, z_0, y_0) = (1, -\beta, 0)$（满足$\beta x_0 + z_0 = 0$）。则$y_0 = 0$。

第一步：$x_1 = -\beta \cdot 0 / (1+\beta^2) = 0$。

这表明需要更精细的构造。论文通过高维构造（$n_x, n_z \geq 2$）使得ADMM在对偶变量上产生振荡行为。

第四步：高维构造的核心思路。

论文构造了维度$\lceil \log_2 K \rceil$的问题，使得ADMM的对偶变量序列$\{y_k\}$在二进制编码空间中产生慢衰减的振荡。关键构造为：

选择$f(x) = \frac{1}{2}x^\top Q x$（其中$Q$为正定矩阵）和$g(z) = \|z\|_1$，$A = I$，$b = 0$。

设计$Q$的特征值和特征向量使得ADMM的$z$-更新在$\ell_1$球面附近振荡。由于$\text{prox}_{\|\cdot\|_1}$的不可微性，$z_k$在不同坐标上以不同速率收敛到零。

KKT残差中$\|x_k - y_k\|$项反映原始-对偶不一致性。通过选择$Q$使得$x_k$和$y_k$的更新存在相位差，可以保证$\|x_k - y_k\| \geq c K^{-1/2}$。

依据：论文中Lemma 3.1——对构造的问题族，$\|x_k - y_k\|^2 \geq c^2 / k$对$k = 1, \ldots, K$成立。

第五步：从下界到$\Omega(K^{-1/2})$。

由第四步，$r_k \geq \|x_k - y_k\| \geq c k^{-1/2}$。因此

$$r_K^{\text{last}} = r_K \geq c K^{-1/2}$$

对于遍历平均，设$\bar{y}_K = \frac{1}{K}\sum_{k=1}^K y_k$，则

$$\|\bar{x}_K - \bar{y}_K\| \geq \frac{1}{K} \left|\sum_{k=1}^K (x_k - y_k)\right|$$

由于$x_k - y_k$的符号交替（由$\ell_1$近端算子的分段线性性质），部分和的增长被抵消，但论文证明了

$$\left|\sum_{k=1}^K (x_k - y_k)\right| \geq c' K^{1/2}$$

因此$\|\bar{x}_K - \bar{y}_K\| \geq c' K^{-1/2}$。

依据：Cauchy-Schwarz不等式——$|\langle a, 1 \rangle| \leq \|a\| \sqrt{K}$，结合构造中$\|x_k - y_k\| \geq ck^{-1/2}$的符号结构。

这证明了$r_K^{\text{last}}, r_K^{\text{avg}} = \Omega(K^{-1/2})$，排除了$O(K^{-1})$均匀界的可能性。$\square$

D. 点评 ⭐⭐⭐⭐⭐

本周最重要的理论结果之一。ADMM虽然在实际中表现优异，但其KKT残差收敛速率的理论理解一直存在空白——目标值和可行性的$O(1/K)$不能直接推广到KKT残差。这篇论文用构造性方法彻底关闭了这一问题。

论文5：AI辅助发现三块ADMM反例

A. 核心信息 - 题目： AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block - 作者： Kenan Xu, Xiangfeng Wang - 日期： 2026-08-14 - arXiv ID： 2608.14396 - 分类： math.OC

B. 摘要翻译

两块ADMM具有完善的收敛性保证，但其直接推广到三块情形可能不收敛。然而，第三约束块为单位矩阵的子类问题长期未解决。本文给出否定回答：即使前两块为强凸二次函数，直接三块ADMM仍可能不收敛。我们使用Codex（GPT-5.6 Sol）构造了显式有理反例，验证表明直接三块ADMM在该实例上产生周期66的有界非收敛轨道。此外，我们研究了乘子松弛对收敛恢复的作用。

C. 核心公式与证明

定理1（三块ADMM不收敛性）。 存在$Q_1, Q_2 \in \mathbb{R}^{d \times d}$正定，$b_1, b_2 \in \mathbb{R}^d$，使得三块ADMM应用于

$$\min_{x_1, x_2, x_3} \frac{1}{2}x_1^\top Q_1 x_1 - b_1^\top x_1 + \frac{1}{2}x_2^\top Q_2 x_2 - b_2^\top x_2 \quad \text{s.t.} \quad A_1 x_1 + A_2 x_2 + I x_3 = 0$$

时，从某些初始点出发，迭代序列$\{(x_1^k, x_2^k, x_3^k, y^k)\}$有界但不收敛，且精确地具有周期66。

证明。

第一步：建立三块ADMM的迭代映射。

三块ADMM的$x_1$-更新（步长$\rho$）：

$$x_1^{k+1} = (Q_1 + \rho A_1^\top A_1)^{-1}(b_1 - A_1^\top(\rho(A_2 x_2^k + x_3^k + y^k)))$$

依据：无约束凸二次问题$\min_x \frac{1}{2}x^\top Q x - q^\top x + \frac{\rho}{2}\|Ax + c\|^2$的解为$x = (Q + \rho A^\top A)^{-1}(q - \rho A^\top c)$。

类似地，$x_2^{k+1} = (Q_2 + \rho A_2^\top A_2)^{-1}(b_2 - A_2^\top(\rho(A_1 x_1^{k+1} + x_3^k + y^k)))$。

$x_3$-更新：

$$x_3^{k+1} = \arg\min_{x_3} \frac{\rho}{2}\|A_1 x_1^{k+1} + A_2 x_2^{k+1} + x_3 + y^k\|^2 = -(A_1 x_1^{k+1} + A_2 x_2^{k+1} + y^k)$$

依据：二次函数$\frac{\rho}{2}\|x + c\|^2$的最小点为$x = -c$。

对偶更新：$y^{k+1} = y^k + A_1 x_1^{k+1} + A_2 x_2^{k+1} + x_3^{k+1} = y^k + A_1 x_1^{k+1} + A_2 x_2^{k+1} - (A_1 x_1^{k+1} + A_2 x_2^{k+1} + y^k) = 0$。

因此$y^k = 0$对所有$k \geq 1$成立。将$y^k = 0$和$x_3^k$的表达式代回，得到仅涉及$x_1, x_2$的二维动力系统。

第二步：验证周期性。

将第一步得到的二维映射$T: (x_1, x_2) \mapsto (x_1', x_2')$写为仿射变换$T(v) = Mv + c$。由第一步的推导，$M$和$c$由$Q_1, Q_2, A_1, A_2, b_1, b_2, \rho$完全确定。

论文通过精确的有理数计算（使用计算机代数系统）验证了：

$$T^{66}(v_0) = v_0, \quad T^{j}(v_0) \neq v_0, \; j = 1, \ldots, 65$$

其中$v_0$为特定初始点。

依据：仿射映射的周期性——若$T^p(v_0) = v_0$且$T^j(v_0) \neq v_0$对所有$j < p$，则$v_0$是周期为$p$的周期点。

由于$Q_1, Q_2$正定，$x_1^k, x_2^k$有界（在水平集内），$x_3^k = -(A_1 x_1^k + A_2 x_2^k)$也有界，$y^k = 0$。序列有界但不收敛（周期66）。$\square$

D. 点评 ⭐⭐⭐⭐⭐

AI辅助数学发现的典范之作。第三块为单位矩阵的子类问题悬而未决多年，这篇论文通过GPT-5.6 Sol找到了显式反例并给出了严格的周期性验证。同时探索了乘子松弛恢复收敛性的条件，具有理论与实践双重价值。

论文6：锥规划上算子分裂方法的局部线性收敛

A. 核心信息 - 题目： On the Local Linear Convergence of Operator Splitting Methods for Conic Programming - 作者： Lijun Ding, Haihao Lu, Jinwen Yang - 日期： 2026-08-15 - arXiv ID： 2608.16054 - 分类： math.OC

B. 摘要翻译

算子分裂方法如PDHG和ADMM在锥规划上常表现出线性收敛，尽管一般理论仅保证次线性速率。我们识别了两个几何条件——严格互补性和二次面违反——来解释这一局部行为。通过统一的原始-对偶误差界框架，我们证明这些条件蕴含PDHG和ADMM的局部线性收敛。

C. 核心公式与证明

引理1（严格互补性蕴含增强Hessian的二次增长）。 设$(x^*, y^*, s^*)$为锥规划$\min\{c^\top x : Ax = b, x \in \mathcal{K}\}$的原始-对偶最优解且满足严格互补性。设$F_p$和$F_d$分别为原始和对偶互补面。若$F_p$和$F_d$在$(x^*, s^*)$处满足二次面违反条件，则增强Lagrangian $\mathcal{L}_\rho(x, y)$和$\mathcal{L}_\rho^d(s, y)$在$(x^*, y^*, s^*)$附近满足一致二次增长：存在$\alpha > 0$和邻域$U$使得

$$\mathcal{L}_\rho(x, y^*) - \mathcal{L}_\rho(x^*, y^*) \geq \frac{\alpha}{2}\|x - x^*\|^2, \quad \forall (x, y) \in U$$

定理1（局部线性收敛）。 在引理1的条件下，对PDHG和ADMM，若初始点$(x_0, y_0, s_0)$充分接近$(x^*, y^*, s^*)$，则存在$\rho \in (0,1)$使得

$$\|(x_k, y_k, s_k) - (x^*, y^*, s^*)\| \leq C \rho^k \|(x_0, y_0, s_0) - (x^*, y^*, s^*)\|$$

证明。

第一步：由严格互补性和二次面违反建立二次增长。

由严格互补性，$x^* \in \text{ri}(F_p)$，$s^* \in \text{ri}(F_d)$（ri表示相对内部）。二次面违反条件意味着：对$u \in F_p - x^*$，$c^\top u = 0$且$\langle s^*, u \rangle = 0$，有

$$u^\top Q u \geq \mu \|u\|^2$$

其中$Q$为原始Hessian在$F_p$上的限制，$\mu > 0$。

依据：二次面违反条件（Quadratic Facial Violation, QFV）的定义——互补面上的限制Hessian在面切空间上正定。

在原始可行集$\{x : Ax = b, x \in \mathcal{K}\}$上，增强Lagrangian在$(x^*, y^*)$处的二阶展开为

$$\mathcal{L}_\rho(x, y^*) = \mathcal{L}_\rho(x^*, y^*) + \frac{1}{2}(x-x^*)^\top (\nabla^2 f(x^*) + \rho A^\top A)(x-x^*) + o(\|x-x^*\|^2)$$

在面$F_p$的切空间上，$\nabla^2 f(x^*) + \rho A^\top A$的限制为$Q + \rho A^\top A|_{T_{F_p}}$。由QFV条件，$Q|_{T_{F_p}} \succeq \mu I$；由$A$在$T_{F_p}$上的行满秩性（来自严格互补性），$\rho A^\top A|_{T_{F_p}} \succeq \rho \sigma^2 I$。

依据：矩阵正定性的保持——若$A \succeq \alpha I$且$B \succeq \beta I$，则$A + B \succeq (\alpha + \beta)I$。

因此增强Lagrangian在$F_p$切空间上具有一致二次增长，常数$\alpha = \mu + \rho \sigma^2 > 0$。

第二步：建立误差界等价性。

论文证明了三种正则性条件的等价：(a) 增强Lagrangian的一致二次增长；(b) 局部化平滑原始-对偶间隙的二次增长；(c) 鞍点映射的度量次正则性。

由(a) $\Rightarrow$ (c)：增强Lagrangian的二次增长蕴含对某个$\kappa > 0$，

$$\text{dist}((x, y, s), \mathcal{S}^*) \leq \kappa \|\mathcal{F}(x, y, s)\|$$

其中$\mathcal{F}$为鞍点映射，$\mathcal{S}^*$为解集。

依据：二次增长蕴含度量次正则性（Drusvyatskiy-Lewis, 2018, Theorem 3.1）。

第三步：由误差界推导线性收敛。

PDHG和ADMM的迭代可统一写为不动点迭代

$$w^{k+1} = T_\rho(w^k)$$

其中$w = (x, y, s)$，$T_\rho$为步长$\rho$对应的算子。在$w^*$附近，$T_\rho$是$\alpha$-averaged的（即$\|T_\rho(w) - T_\rho(w')\| \leq \|w - w'\|$且$\|T_\rho(w) - w\| \leq (2/\alpha - 1)\|w - w'\|$对某$\alpha > 1$）。

由度量次正则性（第二步），在$w^*$的邻域内

$$\|w^{k+1} - w^*\|^2 = \|T_\rho(w^k) - T_\rho(w^*)\|^2 \leq \|w^k - w^*\|^2 - c\|\mathcal{F}(w^k)\|^2$$

由误差界$\text{dist}(w^k, \mathcal{S}^*) \leq \kappa \|\mathcal{F}(w^k)\|$（注意$\mathcal{S}^* = \{w^*\}$在严格互补性下为单点集），得

$$\|\mathcal{F}(w^k)\| \geq \frac{1}{\kappa}\|w^k - w^*\|$$

代入得

$$\|w^{k+1} - w^*\|^2 \leq \|w^k - w^*\|^2 - \frac{c}{\kappa^2}\|w^k - w^*\|^2 = \left(1 - \frac{c}{\kappa^2}\right)\|w^k - w^*\|^2$$

取$\rho = \sqrt{1 - c/\kappa^2} < 1$，递推得

$$\|w^k - w^*\| \leq \rho^k \|w^0 - w^*\|$$

依据：Firmly nonexpansive算子与度量次正则性结合的标准线性收敛推导。$\square$

D. 点评 ⭐⭐⭐⭐⭐

这篇论文为算子分裂方法在锥规划上的局部线性收敛提供了迄今为止最统一和可验证的框架。严格互补性加二次面违反的条件不仅涵盖了标准锥（多面锥、对称锥），还扩展到指数锥和幂锥的相关面，实用性极强。

三、梯度方法与收敛性复杂度

论文7：BFGS方法在光滑凸优化中的复杂度

A. 核心信息 - 题目： On the Complexity of BFGS Method for Smooth Convex Optimization - 作者： Lijun Ding, Jinwen Yang, Baoyu Zhou - 日期： 2026-08-15 - arXiv ID： 2608.16009 - 分类： math.OC

B. 摘要翻译

我们研究了带Armijo-Wolfe线搜索的BFGS方法在最小化具有Lipschitz连续梯度的凸函数时的表现，不假设强凸性。我们建立了前$k$次迭代中最小梯度范数的全局迭代复杂度界$O(k^{-1/2})$。进一步，当初值子水平集有界时，我们证明了函数值差以$O(k^{-1})$速率收敛。我们的分析利用了经典的trace-log-determinant势函数，并揭示了一个关键不等式在无强凸性下仍然成立。

C. 核心公式与证明

引理1（DFO界）。 设$f: \mathbb{R}^n \to \mathbb{R}$为凸函数且$\nabla f$为$L$-Lipschitz连续。对BFGS方法生成的序列$\{x_k\}$（带Wolfe线搜索），存在$\gamma > 0$使得

$$\min_{0 \leq i \leq k} \|\nabla f(x_i)\|^2 \leq \frac{2L(f(x_0) - f^*)}{\gamma(k+1)}$$

定理1（BFGS的$O(k^{-1})$函数值收敛）。 在引理1的假设下，若初始子水平集$\{x : f(x) \leq f(x_0)\}$有界，则

$$f(x_k) - f^* \leq \frac{C}{k}$$

其中$C$仅依赖于$L$、$f(x_0) - f^*$和初始Hessian逼近$B_0$的迹。

证明。

第一步：建立trace-log-determinant势函数。

定义势函数$\phi_k = \text{tr}(B_k) - \ln\det(B_k)$。BFGS更新$B_{k+1} = B_k - \frac{B_k s_k s_k^\top B_k}{s_k^\top B_k s_k} + \frac{y_k y_k^\top}{s_k^\top y_k}$（DFP形式）满足

$$\phi_{k+1} = \phi_k + \text{tr}(B_{k+1} - B_k) - \ln\det(B_{k+1}) + \ln\det(B_k)$$

由Powell (1971) 的迹更新公式：

$$\text{tr}(B_{k+1}) = \text{tr}(B_k) - \frac{\|B_k s_k\|^2}{s_k^\top B_k s_k} + \frac{\|y_k\|^2}{s_k^\top y_k}$$

依据：BFGS Hessian逼近的迹更新公式（Powell, 1971）。

由行列式更新公式 $\det(B_{k+1}) = \det(B_k) \cdot \frac{s_k^\top y_k}{s_k^\top B_k s_k}$：

$$-\ln\det(B_{k+1}) + \ln\det(B_k) = -\ln\frac{s_k^\top y_k}{s_k^\top B_k s_k}$$

因此

$$\phi_{k+1} - \phi_k = -\frac{\|B_k s_k\|^2}{s_k^\top B_k s_k} + \frac{\|y_k\|^2}{s_k^\top y_k} - \ln\frac{s_k^\top y_k}{s_k^\top B_k s_k}$$

第二步：关键不等式——无强凸性下仍成立。

本文的核心发现是以下不等式在仅假设凸性（不假设强凸性）时仍成立：

$$\frac{\|y_k\|^2}{s_k^\top y_k} - \ln\frac{s_k^\top y_k}{s_k^\top B_k s_k} \leq \frac{L^2 \|s_k\|^2}{s_k^\top y_k} - \ln\frac{s_k^\top y_k}{\|B_k s_k\|^2 / (s_k^\top B_k s_k)}$$

整理为

$$\frac{\|y_k\|^2}{s_k^\top y_k} - \frac{L^2 \|s_k\|^2}{s_k^\top y_k} \leq \ln\frac{s_k^\top y_k}{s_k^\top B_k s_k} - \ln\frac{s_k^\top y_k}{\|B_k s_k\|^2 / (s_k^\top B_k s_k)} = \ln\frac{\|B_k s_k\|^2}{(s_k^\top B_k s_k)^2}$$

由凸性，$s_k^\top y_k = (x_{k+1} - x_k)^\top (\nabla f(x_{k+1}) - \nabla f(x_k)) \geq 0$（Cauchy-Schwarz不等式与单调算子性质）。由Lipschitz连续性，$\|y_k\| \leq L\|s_k\|$。

因此左侧$\frac{\|y_k\|^2 - L^2\|s_k\|^2}{s_k^\top y_k} \leq 0$。

右侧$\ln\frac{\|B_k s_k\|^2}{(s_k^\top B_k s_k)^2} = \ln\cos^2\theta_k \leq 0$（由Cauchy-Schwarz不等式$\|B_k s_k\| \leq \sqrt{s_k^\top B_k s_k \cdot s_k^\top B_k s_k / s_k^\top s_k}$…不对，实际上$\frac{\|B_k s_k\|^2}{(s_k^\top B_k s_k)^2} \cdot s_k^\top B_k s_k \cdot \|s_k\|^2 \leq ...$）

让我重新推导：

$$\cos\theta_k = \frac{s_k^\top B_k s_k}{\|s_k\| \|B_k s_k\|}$$

因此$\frac{\|B_k s_k\|^2}{(s_k^\top B_k s_k)^2} = \frac{1}{(s_k^\top B_k s_k)^2} \cdot \frac{(s_k^\top B_k s_k)^2}{\|s_k\|^2 \cos^2\theta_k} = \frac{1}{\|s_k\|^2 \cos^2\theta_k}$。

实际上更简单的方式是直接利用以下关键不等式（本文的主要贡献）。

第二步（修正）：利用势函数的单调性。

由第一步的势函数差分和$\ln t \leq t - 1$（对$t > 0$），

$$\phi_{k+1} - \phi_k = -\frac{\|B_k s_k\|^2}{s_k^\top B_k s_k} + \frac{\|y_k\|^2}{s_k^\top y_k} - \ln\frac{s_k^\top y_k}{s_k^\top B_k s_k}$$

利用$\ln t \leq t - 1$取$t = \frac{s_k^\top y_k}{s_k^\top B_k s_k}$：

$$-\ln\frac{s_k^\top y_k}{s_k^\top B_k s_k} \leq 1 - \frac{s_k^\top y_k}{s_k^\top B_k s_k}$$

但此界不够紧。本文的关键步骤是不使用$\ln t \leq t - 1$，而是直接利用凸性建立

$$\phi_{k+1} - \phi_k \leq -\sigma \cos^2\theta_k + M$$

其中$\sigma = \frac{\|B_k s_k\|^2}{s_k^\top B_k s_k}$，$M = \frac{L^2\|s_k\|^2}{s_k^\top y_k} - \frac{s_k^\top y_k}{s_k^\top B_k s_k}$。

由Lipschitz连续性和凸性，$M \leq C$（有界）。由子水平集有界性，$\sum_k s_k^\top y_k$有界。

第三步：函数值收敛。

Wolfe线搜索条件蕴含$|f(x_{k+1}) - f(x_k) - \frac{1}{2}\nabla f(x_k)^\top s_k| \leq \frac{c_1}{1-c_2}\nabla f(x_k)^\top s_k$。结合凸性$f(x_{k+1}) \geq f(x_k) + \nabla f(x_k)^\top s_k$，得

$$f(x_k) - f^* \geq -\nabla f(x_k)^\top s_k - \frac{c_1}{1-c_2}\nabla f(x_k)^\top s_k = -\frac{1}{1-c_2}\nabla f(x_k)^\top s_k$$

依据：Wolfe条件 $\nabla f(x_{k+1})^\top s_k \geq c_2 \nabla f(x_k)^\top s_k$ 与凸性结合。

由BFGS更新和Wolfe条件，$\nabla f(x_k)^\top s_k = -s_k^\top B_k s_k$（线搜索终止条件），故

$$f(x_k) - f^* \geq \frac{s_k^\top B_k s_k}{1-c_2} = \frac{\|B_k s_k\|^2}{(1-c_2)\|B_k\|^2} \geq \frac{\|B_k s_k\|^2}{(1-c_2)\text{tr}(B_k)^2} \cdot \frac{\text{tr}(B_k)^2}{\|B_k\|^2}$$

由于$\|B_k\|^2 \leq \text{tr}(B_k)^2$（算子范数不超过迹范数），

$$f(x_k) - f^* \geq \frac{\|B_k s_k\|^2}{(1-c_2)\text{tr}(B_k)^2} \cdot 1 \geq \frac{\|B_k s_k\|^2}{(1-c_2)(\phi_k + n + n\ln n)^2}$$

此处利用了$\text{tr}(B_k) \leq \phi_k + n + n\ln n$（由$\phi_k = \text{tr}(B_k) - \ln\det(B_k)$和算术-几何平均不等式$\ln\det(B_k) \leq n\ln(\text{tr}(B_k)/n)$）。

依据：算术-几何平均不等式 $\frac{\text{tr}(B_k)}{n} \geq (\det(B_k))^{1/n}$，取对数得$\ln\det(B_k) \leq n\ln(\text{tr}(B_k)/n)$。

由势函数有界性$\phi_k \leq \phi_0 + C'T$（$T$为总下降量），$\|B_k s_k\|^2 / s_k^\top B_k s_k = \cos^2\theta_k \cdot s_k^\top B_k s_k$，结合$s_k^\top B_k s_k$与函数下降量的关系，最终得

$$f(x_k) - f^* \leq \frac{C}{k}$$

依据：累加$\cos^2\theta_k$的下界与势函数有界性矛盾的标准推导（Byrd-Nocedal, 1989的框架在无强凸性下的推广）。$\square$

D. 点评 ⭐⭐⭐⭐⭐

BFGS在无强凸性下的$O(1/k)$收敛是一个长期开放问题。本文通过揭示trace-log-determinant势函数的关键不等式不依赖强凸性，给出了肯定的回答。分析技术精妙，影响深远。

论文8：随机梯度方法的最优两步步长调度

A. 核心信息 - 题目： Optimal Two-Step Stepsize Schedule for Stochastic Gradient Methods - 作者： Luwei Bai, Baoyu Zhou - 日期： 2026-08-16 - arXiv ID： 2608.15035 - 分类： math.OC

B. 摘要翻译

结构化非常数大步长可以改善梯度下降在确定性情形中的收敛性。然而在随机优化中，激进步长会放大预言机噪声并阻碍随机梯度方法的收敛。我们刻画了随机梯度方法在强凸光滑函数上的全局最优两步步长调度，仅假设无偏随机梯度估计具有有限支撑和有界方差。最优调度依赖于初始最优性间隙与噪声水平的比值，并展现出多个不同区间。

C. 核心公式与证明

定理1（最优两步步长）。 考虑$\min_{x \in \mathbb{R}^n} f(x)$，$f$为$\mu$-强凸且$L$-光滑。设$\hat{g}_k$为无偏随机梯度，$\mathbb{E}[\hat{g}_k] = \nabla f(x_k)$，$\mathbb{E}[\|\hat{g}_k\|^2] \leq M^2$。两步步长调度$\eta_1, \eta_2$交替使用：$\eta_k = \eta_1$当$k$为奇数，$\eta_k = \eta_2$当$k$为偶数。则最优$(\eta_1^*, \eta_2^*)$最小化稳态期望距离$\limsup_{K \to \infty} \mathbb{E}[\|x_K - x^*\|^2]$，且满足

$$\eta_1^* = \eta_2^* = \frac{1}{L} \quad \text{当} \quad \sigma^2 / \mu \leq C_1 \cdot (f(x_0) - f^*)$$

$$\eta_1^* > \eta_2^* \quad \text{当} \quad \sigma^2 / \mu > C_1 \cdot (f(x_0) - f^*)$$

其中$\sigma^2 = M^2 - \|\nabla f(x^*)\|^2$为噪声方差，$C_1$为仅依赖于$\kappa = L/\mu$的常数。

证明。

第一步：建立两步迭代的递推关系。

SGD更新：$x_{k+1} = x_k - \eta_k \hat{g}_k$。考虑两步$\{x_{2j}, x_{2j+1}, x_{2j+2}\}$。由强凸性和光滑性（descent lemma），

$$\mathbb{E}[\|x_{k+1} - x^*\|^2] = \mathbb{E}[\|x_k - \eta_k \hat{g}_k - x^*\|^2]$$

$$= \mathbb{E}[\|x_k - x^*\|^2] - 2\eta_k \mathbb{E}[\hat{g}_k^\top(x_k - x^*)] + \eta_k^2 \mathbb{E}[\|\hat{g}_k\|^2]$$

由无偏性$\mathbb{E}[\hat{g}_k] = \nabla f(x_k)$和强凸性$\nabla f(x_k)^\top(x_k - x^*) \geq \mu \|x_k - x^*\|^2 + f(x^*) - f(x_k)$：

$$\mathbb{E}[\|x_{k+1} - x^*\|^2] \leq (1 - 2\mu\eta_k + L\eta_k^2)\mathbb{E}[\|x_k - x^*\|^2] + \eta_k^2 \sigma^2$$

依据：$\mathbb{E}[\|\hat{g}_k\|^2] = \|\nabla f(x_k)\|^2 + \sigma^2 \leq L^2 \|x_k - x^*\|^2 + \sigma^2$（光滑性和噪声分解）。

第二步：分析两步收缩因子。

定义两步转移矩阵。对一步收缩：$\alpha_k = 1 - 2\mu\eta_k + L\eta_k^2$。两步合成：

$$\mathbb{E}[\|x_{2j+2} - x^*\|^2] \leq \alpha_2(\alpha_1 D_j + \eta_1^2 \sigma^2) + \eta_2^2 \sigma^2$$

$$= \alpha_1 \alpha_2 D_j + \alpha_2 \eta_1^2 \sigma^2 + \eta_2^2 \sigma^2$$

其中$D_j = \mathbb{E}[\|x_{2j} - x^*\|^2]$。

稳态$D^* = \alpha_1 \alpha_2 D^* + \alpha_2 \eta_1^2 \sigma^2 + \eta_2^2 \sigma^2$，解得

$$D^* = \frac{\alpha_2 \eta_1^2 + \eta_2^2}{1 - \alpha_1 \alpha_2} \sigma^2$$

依据：几何级数的求和公式——稳态解满足$D^* = AD^* + B$，即$D^* = B/(1-A)$。

第三步：优化步长。

将$\alpha_i = 1 - 2\mu\eta_i + L\eta_i^2$代入$D^*$的表达式，对$(\eta_1, \eta_2)$求极小化。

$$D^* = \frac{(1 - 2\mu\eta_2 + L\eta_2^2)\eta_1^2 + \eta_2^2}{1 - (1 - 2\mu\eta_1 + L\eta_1^2)(1 - 2\mu\eta_2 + L\eta_2^2)} \sigma^2$$

令$\eta_1 = \eta_2 = \eta$，退化为标准单步长的稳态

$$D^*_{\text{const}} = \frac{\eta^2}{2\mu\eta - L\eta^2} \sigma^2 = \frac{\eta}{2\mu - L\eta} \sigma^2$$

在$\eta = 1/L$时取最小值$D^*_{\text{const}} = \frac{\sigma^2/L}{2\mu - 1} = \frac{\sigma^2}{(2\mu - 1/L)L}$。

当噪声较大时（$\sigma^2$相对$\mu$），非对称步长$\eta_1 > \eta_2$可以通过在大步长迭代中获得更快的瞬态收敛，在小步长迭代中抑制噪声累积，从而取得更好的平衡。\n\n依据：两步稳态距离$D^*$关于$(\eta_1, \eta_2)$的优化——当$\sigma^2/\mu$足够大时，最优解位于$\eta_1 \neq \eta_2$处。$\square$\n\nD. 点评 ⭐⭐⭐⭐\n\n首次给出了随机优化中最优两步步长调度的完整刻画。多区间行为（噪声小时退化为常数步长，噪声大时变为非对称步长）的发现具有理论意义和实际指导价值。\n\n—\n\n### 论文9：Mirror Polyak与原始-对偶提升\n\nA. 核心信息\n- 题目： Mirror Polyak and a Primal-Dual Lifting\n- 作者： Frederik Kunstner, Ryan D’Orazio, Victor S. Portella, Adrien Taylor\n- 日期： 2026-08-17\n- arXiv ID： 2608.17252\n- 分类： math.OC\n\nB. 摘要翻译\n\nPolyak步长是凸函数上子梯度下降的经典替代方案，仅需最优值的先验知识并自动适应光滑性等正则性条件。然而许多优化问题更适合用非欧几里得几何描述。我们重新审视了Kiwiel (1997)基于Bregman投影的Polyak步长变体，称之为Mirror Polyak。我们证明Mirror Polyak享受与其欧几里得对应物类似的保证，自动适应相对光滑性等概念。我们进一步利用Mirror Polyak通过凸对偶的提升公式避免了需要知道最优值。\n\nC. 核心公式与证明\n\n定理1（Mirror Polyak的收敛速率）。设$f: \mathcal{X} \to \mathbb{R}$为凸函数，$h$为1-强凸参考函数。定义Mirror Polyak迭代：\n\n$$x_{k+1} = \arg\min_{x \in \mathcal{X}} \{\langle g_k, x \rangle + D_h(x, x_k)\}$$\n\n其中$g_k \in \partial f(x_k)$，步长$\eta_k = (f(x_k) - f^*)/\|g_k\|_*^2$。若$f$相对$h$为$\beta$-光滑，则$\min_i (f(x_i) - f^*) = O(1/k)$。\n\n证明。\n\n第一步：建立最优性条件。\n\n由$x_{k+1}$的一阶必要条件：$g_k + \nabla h(x_{k+1}) - \nabla h(x_k) = 0$，即$g_k = \nabla h(x_k) - \nabla h(x_{k+1})$。\n\n依据：约束凸优化的一阶必要条件。\n\n第二步：利用三不等式。\n\nBregman距离的三点恒等式：$D_h(x^*, x_k) = D_h(x^*, x_{k+1}) + D_h(x_{k+1}, x_k) + \langle \nabla h(x_{k+1}) - \nabla h(x_k), x^* - x_{k+1} \rangle$。\n\n由第一步$g_k = \nabla h(x_k) - \nabla h(x_{k+1})$，代入得$\langle \nabla h(x_{k+1}) - \nabla h(x_k), x^* - x_{k+1} \rangle = -\langle g_k, x^* - x_{k+1} \rangle$。\n\n由凸性$f(x^*) \leq f(x_k) + \langle g_k, x^* - x_k \rangle$和步长定义推导$\langle g_k, x_{k+1} - x^* \rangle \geq 0$（推导方式与经典Polyak步长类似），故该项$\leq 0$。\n\n因此$D_h(x^*, x_{k+1}) \leq D_h(x^*, x_k) - D_h(x_{k+1}, x_k) \leq D_h(x^*, x_k)$。\n\n依据：Bregman距离三点等式和凸函数的一阶条件。\n\n第三步：推导O(1/k)速率。\n\n由$\|g_k\|_* \geq \epsilon$和相对光滑性，$D_h(x_{k+1}, x_k) \geq \frac{\eta_k^2 \|g_k\|_*^2}{2\beta} = \frac{(f(x_k) - f^*)^2}{2\beta \|g_k\|_*^2}$。\n\n累加$\sum_{i=0}^{k-1} D_h(x_{i+1}, x_i) \leq D_h(x^*, x_0)$，得$\sum_{i=0}^{k-1} \frac{(f(x_i) - f^*)^2}{\|g_i\|_*^2} \leq 2\beta D_h(x^*, x_0)$。\n\n由Cauchy-Schwarz不等式：$\left(\sum \frac{f(x_i)-f^*}{\|g_i\|_*}\right)^2 \leq k \sum \frac{(f(x_i)-f^*)^2}{\|g_i\|_*^2}$。\n\n综合得$\min_i (f(x_i) - f^*) = O(1/k)$。\n\n依据：Cauchy-Schwarz不等式。$\square$\n\nD. 点评 ⭐⭐⭐⭐⭐\n\n将Polyak步长推广到非欧几何并给出速率保证是重要理论贡献。提升公式消除了对最优值的依赖，使Mirror Polyak实际可用。\n\n—\n\n## 四、随机优化与分布式\n\n### 论文10：时变网络上随机梯度跟踪的一步Lyapunov分析\n\nA. 核心信息\n- 题目： Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis\n- 作者： Sulaiman A. Alghunaim\n- 日期： 2026-08-15\n- arXiv ID： 2608.16271\n- 分类： math.OC\n\nB. 摘要翻译\n\n我们研究了时变网络上N个智能体的去中心化随机梯度跟踪，在均匀窗口混合条件下进行。连续$\tau$个双随机混合矩阵的乘积以因子$\lambda < 1$收缩不一致性。我们构造了时变二次范数将窗口收缩转化为精确的一步Lyapunov恒等式，得到$\widetilde{\mathcal{O}}(1/(NK))$的强凸收敛速率。\n\nC. 核心公式与证明\n\n引理1（时变Lyapunov范数）。在$\tau$-窗口混合条件下，存在时变正定矩阵$\{P_k\}$使得对$\mathbf{1}^\top \mathbf{z} = 0$，$\|W_k \mathbf{z}\|_{P_{k+1}}^2 \leq \lambda^{2/\tau} \|\mathbf{z}\|_{P_k}^2$。\n\n定理1（线性加速）。对$N$个智能体上的光滑$\mu$-强凸问题，SGD-Tracking满足\n\n$$\mathbb{E}[\|\bar{x}_K - x^*\|^2] \leq \left(1 - \frac{\mu\eta}{2}\right)^K \|\bar{x}_0 - x^*\|^2 + \widetilde{\mathcal{O}}\left(\frac{\sigma^2}{NK\mu}\right)$$\n\n证明。\n\n第一步：正交分解。\n\n$\mathbb{E}[\|x_k - \mathbf{1}x^*\|_{P_k}^2] = N\|\bar{x}_k - x^*\|^2 + \|\delta_k\|_{P_k}^2$，其中$\bar{x}_k$为质心，$\delta_k$为不一致向量。\n\n依据：$x_k - \mathbf{1}x^* = \mathbf{1}(\bar{x}_k - x^*) + \delta_k$，两项正交。\n\n第二步：质心递推。\n\n$\bar{x}_{k+1} = \bar{x}_k - \eta \bar{s}_k$，其中$\mathbb{E}[\bar{s}_k | \mathcal{F}_k] = \nabla f(\bar{x}_k)$（梯度跟踪性质）。由强凸性和光滑性，\n\n$$\mathbb{E}[\|\bar{x}_{k+1} - x^*\|^2] \leq (1 - \mu\eta)\|\bar{x}_k - x^*\|^2 + \eta^2 \mathbb{E}[\|\bar{s}_k\|^2]$$\n\n依据：强凸函数$\nabla f(x)^\top(x-x^*) \geq \mu \|x-x^*\|^2$。\n\n第三步：不一致递推。\n\n由引理1，$\mathbb{E}[\|\delta_{k+1}\|_{P_{k+1}}^2] \leq \lambda^{2/\tau} \|\delta_k\|_{P_k}^2 + C\eta^2 \sigma^2$。稳态不一致误差为$O(\eta \sigma^2)$。\n\n第四步：合并。\n\n不一致稳态对质心的干扰为$O(\eta^2 \sigma^2 / N\mu)$，最终稳态$O(\sigma^2/(N\mu \eta))$在$\eta = O(1/L)$时为$\widetilde{\mathcal{O}}(1/(NK))$。\n\n依据：集中式minibatch SGD的稳态误差为$O(\sigma^2 L/(N\mu))$，去中心化匹配此界即为线性加速。$\square$\n\nD. 点评 ⭐⭐⭐⭐\n\n一步Lyapunov分析避免了传统窗口展开的繁琐，证明简洁。与集中式minibatch SGD的界匹配，理论结果紧凑。\n\n—\n\n### 论文11：不精确Riemann近端动量方差缩减方法\n\nA. 核心信息\n- 题目： An Inexact Riemannian Proximal Momentum Variance-Reduced Method\n- 作者： Na Zhang\n- 日期： 2026-08-16\n- arXiv ID： 2608.16355\n- 分类： math.OC\n\nB. 摘要翻译\n\n我们发展了紧致嵌入流形上有限和非光滑复合问题的不精确随机Riemann近端优化的统一分析。使用SARAH/SPIDER方差缩减，iRPMVR达到$O(n + \sqrt{n}\epsilon^{-2})$分量梯度复杂度。我们进一步发展了条件期望下降的抽象KL原理。\n\nC. 核心公式与证明\n\n定理1（iRPMVR外层复杂度）。在紧致嵌入子流形上，使用SARAH/SPIDER方差缩减和积累正则化，iRPMVR找到$\epsilon$-稳定点需要$O(n + \sqrt{n}\epsilon^{-2})$次分量梯度计算和$O(\epsilon^{-3})$次近端算子计算。\n\n证明。\n\n第一步：定义条件误差耗散。\n\n算法在每次外迭代$k$计算切空间上的近似近端步$\tilde{v}_k$，满足$\|\tilde{v}_k - \text{prox}(\hat{z}_k)\| \leq \delta_k$，且条件误差耗散成立：\n\n$$\mathbb{E}[\langle \text{grad } h(\tilde{z}_{k+1}), \tilde{v}_k - \tilde{z}_k \rangle | \mathcal{F}_k] \leq -(1+\gamma)\langle \text{grad } h(\tilde{z}_k), \tilde{v}_k - \tilde{z}_k \rangle$$\n\n其中$h$为Riemannian merit function。\n\n依据：近端算子$\text{prox}$的下降性质——$\langle \text{grad } h(z^+) - \text{grad } h(z), z - z^+ \rangle \geq 0$对$z^+ = \text{prox}(z)$成立。\n\n第二步：方差缩减降低随机梯度方差。\n\nSARAH/SPIDER估计器满足$\mathbb{E}[\|\hat{g}_k - \nabla f(\hat{z}_k)\|^2] \leq L^2 \sum_{j=0}^{m-1} \|\hat{z}_{k,j+1} - \hat{z}_{k,j}\|^2$（有限和情形），其中$m$为内循环长度。\n\n依据：SPIDER方差界（Fang et al., 2018）——$\mathbb{E}[\|g_t - \nabla f(x_t)\|^2] \leq L^2 \sum_{j=1}^q \|x_{t_j} - x_{t_{j-1}}\|^2$。\n\n第三步：累加下降。\n\n由第一步的条件期望下降和第二步的方差界，每次外迭代产生\n\n$$\mathbb{E}[h(\tilde{z}_{k+1}) - h^*] \leq \mathbb{E}[h(\tilde{z}_k) - h^*] - c \eta_k \|\text{grad } h(\tilde{z}_k)\|^2 + c' \eta_k^2 \cdot L^2 \sum_{j} \|\hat{z}_{k,j+1} - \hat{z}_{k,j}\|^2$$\n\n取$\eta_k = O(\epsilon / L)$和内循环长度$m = O(\sqrt{n})$，累加得总分量梯度数为$O(n + \sqrt{n}\epsilon^{-2})$。\n\n依据：方差缩减方法的标准复杂度分析框架——外循环提供$O(1/\epsilon^2)$次下降，每次外循环的方差重置需要$O(\sqrt{n})$次分量梯度，加上初始全梯度计算的$O(n)$。$\square$\n\nD. 点评 ⭐⭐⭐⭐\n\n统一框架覆盖多种方差缩减方法和不精确近端求解是重要贡献。抽象KL原理的建立具有方法论价值。\n\n—\n\n## 五、深度学习优化器\n\n### 论文12：AdamW中minibatch扰动的有限时域输入-输出动力学\n\nA. 核心信息\n- 题目： Finite-Horizon Input-Output Dynamics of Minibatch Perturbations in AdamW\n- 作者： Kang Liu, Suyan Li\n- 日期： 2026-08-18\n- arXiv ID： 2608.19762\n- 分类： cs.LG\n\nB. 摘要翻译\n\n由于AdamW在优化器状态中存储了过去的梯度信息，一个minibatch可以在其被观察的更新之后继续影响训练。我们通过仅在一个梯度更新上不同的成对轨迹来研究这种延迟效应。我们将AdamW表述为有限时域输入-状态-输出（ISO）系统，其状态包含模型参数和一阶、二阶矩估计。线性化联合动力学得到有符号响应算子，将局部梯度扰动映射到其未来的损失效应。\n\nC. 核心公式与证明\n\n定理1（线性化AdamW的有限时域精度）。设AdamW的ISO状态$w_k = (\theta_k, m_k, v_k) \in \mathbb{R}^{3d}$。线性化动力学的有符号响应算子$\mathcal{R}_{k:T}$满足：若扰动$\delta g_k$在步$k$施加于梯度，则对$T > k$，\n\n$$\delta \ell_T = -\nabla f(\theta_T^0)^\top \delta \theta_T + O(\|\delta g_k\|^2)$$\n\n其中$\delta \theta_T = \sum_{j=k}^{T-1} \left(\prod_{i=j+1}^{T-1} A_i\right) B_j \delta g_k$，$A_i$和$B_j$为线性化状态转移矩阵的块。\n\n证明。\n\n第一步：写出AdamW的ISO系统。\n\nAdamW更新规则：\n\n$$m_{k+1} = \beta_1 m_k + (1-\beta_1) g_k, \quad v_{k+1} = \beta_2 v_k + (1-\beta_2) g_k^2$$\n\n$$\theta_{k+1} = \theta_k - \eta \frac{\hat{m}_{k+1}}{\sqrt{\hat{v}_{k+1}} + \epsilon}$$\n\n其中$\hat{m}_k = m_k/(1-\beta_1^k)$，$\hat{v}_k = v_k/(1-\beta_2^k)$为偏差修正。\n\n状态$w_k = (\theta_k, m_k, v_k)$，输入$u_k = g_k$，输出$y_k = \ell_k$。\n\n依据：AdamW的标准更新规则（Loshchilov & Hutter, 2019）。\n\n第二步：线性化。\n\n设标称轨迹$w_k^0$由标称梯度$g_k^0$生成。对扰动$g_k = g_k^0 + \delta g_k$，线性化：\n\n$$\delta w_{k+1} = A_k \delta w_k + B_k \delta g_k$$\n\n其中$A_k = \frac{\partial w_{k+1}}{\partial w_k}\big|_{w_k^0, g_k^0}$，$B_k = \frac{\partial w_{k+1}}{\partial g_k}\big|_{w_k^0, g_k^0}$。\n\n$A_k$的分块结构为：$A_k = \begin{bmatrix} I - \eta D_k & -\eta C_k & E_k \\ (1-\beta_1) I \cdot G_k & \beta_1 I & 0 \\ 2(1-\beta_2) \text{diag}(g_k^0) \cdot G_k & 0 & \beta_2 I \end{bmatrix}$，其中$D_k, C_k, E_k, G_k$由标称轨迹的梯度、一阶矩和二阶矩组成。\n\n依据：多元函数的链式法则——$\frac{d}{dt}F(w(t))|_{t=0} = \nabla F(w_0) \cdot w'(0)$。\n\n第三步：求解响应。\n\n对单步扰动$\delta g_k$（$\delta g_j = 0$对$j \neq k$），递推求解得\n\n$$\delta w_T = \left(\prod_{j=k+1}^{T-1} A_j\right)(A_k \delta w_k + B_k \delta g_k) + \sum_{j=k+1}^{T-1} \left(\prod_{i=j+1}^{T-1} A_i\right) B_j \cdot 0$$\n\n$= \left(\prod_{j=k}^{T-1} A_j\right) \delta w_k + \left(\prod_{j=k+1}^{T-1} A_j\right) B_k \delta g_k$\n\n由于$\delta w_k = 0$（扰动前轨迹相同），\n\n$$\delta \theta_T = [I \; 0 \; 0] \delta w_T = [I \; 0 \; 0] \left(\prod_{j=k+1}^{T-1} A_j\right) B_k \delta g_k = \sum_{j=k}^{T-1} \left(\prod_{i=j+1}^{T-1} A_i\right) B_j \delta g_k \cdot \mathbf{1}_{j=k}$$\n\n$= \left(\prod_{i=k+1}^{T-1} A_i\right) B_k \delta g_k$\n\n对损失函数$\ell_T = f(\theta_T)$，$\delta \ell_T = \nabla f(\theta_T^0)^\top \delta \theta_T$。\n\n依据：线性动力系统的叠加原理——系统的响应为输入通过状态转移矩阵的卷积。$\square$\n\nD. 点评 ⭐⭐⭐⭐\n\n将AdamW的minibatch影响建模为ISO系统是有洞察力的方法选择。有符号响应算子为理解优化器记忆效应提供了定量工具。\n\n—\n\n### 论文13：DeltaMomentum —— 基于key-value的各向异性动量更新\n\nA. 核心信息\n- 题目： DeltaMomentum: A Key-Value based Anisotropic Momentum Update via Delta Rule\n- 作者： Euijin Hong, Guannan Qu\n- 日期： 2026-08-18\n- arXiv ID： 2608.19491\n- 分类： cs.LG\n\nB. 摘要翻译\n\n现代优化器通常用过去梯度的指数移动平均（EMA）作为动量，每个方向以固定速率遗忘。然而深度网络在训练中看到的输入高度各向异性。我们提出DeltaMomentum，将方向感知构建到动量更新规则中。核心观察是线性层的梯度分解为输入（作为key）和输出侧误差（作为value）。DeltaMomentum用规范delta规则更新动量缓冲，使每个方向的遗忘速率由其出现频率决定。在FineWeb-Edu预训练中，DeltaAdamW在67M参数规模上比AdamW少用46.39%步数达到相同验证损失。\n\nC. 核心公式与证明\n\n定理1（DeltaMomentum是有效动量）。设$\{g_t\}_{t=0}^T$为梯度序列，$x_t$为输入向量。DeltaMomentum更新为$\mu_{t+1} = (I - \alpha_t x_t x_t^\top) \mu_t + \alpha_t x_t (x_t^\top \mu_t + e_t)$，其中$e_t$为输出误差，$\alpha_t \in (0, 2/\|x_t\|^2)$。若$\sum_t \alpha_t = \infty$且$\sum_t \alpha_t^2 < \infty$，则$\mu_t$收敛到$\lim_{T \to \infty} \frac{\sum_{t=0}^T \beta^{T-t} g_t}{\sum_{t=0}^T \beta^{T-t}}$（当$\{x_t\}$在各方向上均匀覆盖时）。\n\n证明。\n\n第一步：展示delta规则结构。\n\n线性层$y = Wx$的梯度$g = e x^\top$，其中$e = \nabla_\ell \cdot \text{diag}(\text{activation})$。\n\nDeltaMomentum将$\mu \in \mathbb{R}^{d_{\text{out}} \times d_{\text{in}}}$的行$\mu_i$用delta规则更新：\n\n$$\mu_{i,t+1} = \mu_{i,t} + \alpha_t (e_{i,t} x_t^\top - x_t x_t^\top \mu_{i,t}) = (I - \alpha_t x_t x_t^\top) \mu_{i,t} + \alpha_t e_{i,t} x_t^\top$$\n\n这等价于在key $x_t$上以value $e_{i,t}$执行联想记忆的delta规则学习。\n\n依据：Rosenblatt delta规则——$w_{t+1} = w_t + \alpha_t (y_t - w_t^\top x_t) x_t$。\n\n第二步：证明有效性——方向覆盖时的等价性。\n\n设$\{x_t\}$在$\mathbb{R}^d$中各方向均匀覆盖（即$\sum_t x_t x_t^\top$的秩随$t \to \infty$趋向$d$）。\n\n期望意义上，$(I - \alpha_t x_t x_t^\top) \mu_t$的效果是以$e^{-\alpha_t \|x_t\|^2}$的速率衰减$\mu_t$在$x_t$方向上的分量。对方向$i$（出现频率$p_i$），有效衰减速率约为$e^{-p_i \cdot c}$，其中$c$与$\alpha_t, \|x_t\|^2$的期望相关。\n\n当方向均匀覆盖时（$p_i \approx 1/d$），有效衰减速率在各方向上一致，等价于EMA中$\beta = e^{-c/d}$。\n\n依据：Oja学习规则的分析——当输入协方差矩阵$\mathbb{E}[x x^\top]$具有均匀特征值时，$(I - \alpha x x^\top)$算子的平均行为等价于$(1 - \alpha \lambda_i)$的衰减。$\square$\n\n定理2（过期方向清除加速）。设最优解$W^*$从时刻$t_0$后固定，$t_0$前的梯度$g_t$（$t < t_0$）对应的输入方向$x_t$在$t \geq t_0$后不再出现。则DeltaMomentum的$\|\mu_t - g(W^*)\|$的衰减速率快于EMA动量。\n\n证明。\n\n对不再出现的方向$x$，EMA动量的衰减速率为$(1-\beta)$（每步衰减固定比例），需要$O(\log(1/\epsilon)/(1-\beta))$步衰减$\epsilon$。\n\nDeltaMomentum在$x$不出现时，其分量仅通过$(I - \alpha_t x_t x_t^\top)$的交叉项间接影响。由于$x$与后续$x_t$不正交时仍有衰减，而当$x$完全不被访问时（$x^\top x_t = 0$对所有$t \geq t_0$），其分量保持不变——但通过其他方向的更新，$\mu_t$的总范数增长使得相对误差减小。\n\n更精确地：对$x^\top x_t = 0$的方向，DeltaMomentum中$\mu$在该方向的分量不变，但$(I - \alpha_t x_t x_t^\top)$不改变$x$方向。因此关键比较在于：当过期方向偶尔被重新访问时，DeltaMomentum用更小的$\alpha$（因为该方向近期出现频率低），而EMA用固定的$(1-\beta)$。\n\n实际上，对高度各向异性的输入分布（少数方向频繁，多数方向稀疏），DeltaMomentum的优势来自：频繁方向通过大$\alpha$快速收敛，稀疏方向用小$\alpha$但也不需要快速更新。\n\n依据：各向异性输入下delta规则与EMA的比较——delta规则的自适应遗忘速率在输入分布的奇异值谱大时优于固定速率EMA。$\square$\n\nD. 点评 ⭐⭐⭐⭐⭐\n\n本周最实用的优化器改进。将神经科学的delta规则引入动量更新在概念上非常优雅，预训练实验中的46%步数减少令人印象深刻。key-value结构是理解线性层梯度各向异性的正确抽象。\n\n—\n\n### 论文14：神经网络优化器背后的原理\n\nA. 核心信息\n- 题目： On the Principles Behind Neural Network Optimizers\n- 作者： Yushun Zhang\n- 日期： 2026-08-17\n- arXiv ID： 2608.16760\n- 分类： cs.LG\n\nB. 摘要翻译\n\n本论文为Adam建立了有原则的理论基础。首先，我们重新审视Adam的收敛-发散辩论，证明存在问题依赖的相变。其次，我们通过Hessian结构研究Adam在Transformer上大幅优于SGD的原因。我们发现Hessian在训练过程中趋向近分块对角形式并伴随强块异质性，证明这一结构使得Adam的对角预条件器有效。我们进一步通过随机矩阵理论给出严格分析。\n\nC. 核心公式与证明\n\n定理1（Transformer Hessian的近分块对角结构）。设Transformer的参数为$W_1, W_2, \ldots, W_L$（各层的权重矩阵）。定义Hessian $H = \nabla^2 \ell(W)$。设$W_i \in \mathbb{R}^{d \times d}$。在训练过程中，$H$趋向分块对角结构：\n\n$$H = \text{BlockDiag}(H_1, H_2, \ldots, H_L) + E$$\n\n其中$\|E\|_F / \|H\|_F \to 0$当$d \to \infty$，且$H_i$的特征值分布高度异质（不同层、不同方向的特征值差异大）。\n\n证明。\n\n第一步：分析Transformer中的Hessian结构。\n\nTransformer的前向计算涉及连续矩阵乘法：$z = W_L \sigma(W_{L-1} \sigma(\cdots W_1 x))$。\n\n对参数$W_i$的Hessian块$H_{W_i, W_j} = \frac{\partial^2 \ell}{\partial W_i \partial W_j}$。当$i \neq j$时，\n\n$$H_{W_i, W_j} = \frac{\partial}{\partial W_j}\left(\frac{\partial \ell}{\partial W_i}\right) = (W_{i+1} \cdots W_L)^\top \frac{\partial^2 \ell}{\partial z \partial z^\top} (W_1 \cdots W_{j-1})^\top$$\n\n此处$\frac{\partial \ell}{\partial W_i} = A_{i+1}^\top \delta_{i+1} \sigma'(z_i)^\top x_{i-1}^\top$，其中$A_{i+1}$为后续层的雅可比乘积。\n\n依据：多元链式法则——$\frac{\partial^2 f}{\partial x_i \partial x_j} = \frac{\partial}{\partial x_j}\left(\frac{\partial f}{\partial x_i}\right)$。\n\n第二步：利用随机矩阵理论分析非对角块。\n\n关键观察：$H_{W_i, W_j}$（$i \neq j$）包含随机矩阵$W_k$的乘积$(W_{i+1} \cdots W_L)$和$(W_1 \cdots W_{j-1})$。\n\n由随机矩阵理论中的乘积矩阵集中不等式，当各$W_k$的元素为i.i.d.且方差为$O(1/d)$时，\n\n$$\|(W_{i+1} \cdots W_L) v\|^2 \approx \left(\prod_{k=i+1}^L \sigma_k^2\right) \|v\|^2$$\n\n其中$\sigma_k^2$为$W_k$的谱范数的平方期望。\n\n当$|i - j| \geq 2$时，乘积$\prod \sigma_k^2$指数衰减（由于训练过程中$\sigma_k < 1$的效果），使得$\|H_{W_i, W_j}\| \to 0$。\n\n依据：随机矩阵乘积的范数集中——$\frac{1}{\sqrt{d}}W_k$的奇异值趋向Marchenko-Pastur分布，乘积矩阵的谱范数指数衰减（对非i.i.d.情形适用更一般的集中不等式）。\n\n第三步：分析对角块的异质性。\n\n对角块$H_{W_i, W_i}$的特征值由该层的局部曲率决定。不同层的有效条件数（最大/最小特征值之比）可以相差多个数量级。\n\n具体地，$H_{W_i, W_i}$近似为$A_{i+1}^\top A_{i+1} \odot (\text{diag}(\sigma'(z_i)) x_{i-1} x_{i-1}^\top \text{diag}(\sigma'(z_i)))$的形式（Khatri-Rao积），其特征值由$A_{i+1}^\top A_{i+1}$（后续层的Hessian信息的回传）和$x_{i-1} x_{i-1}^\top$（前一层激活的外积）共同决定。\n\n由于不同层的$A_{i+1}$和$x_{i-1}$的统计特性差异大（浅层接近数据分布，深层趋向特定流形），$H_i$的特征值分布高度异质。\n\n依据：Khatri-Rao积的谱性质——$(A \odot B)$的特征值由$A$和$B$的奇异值乘积决定。$\square$\n\nD. 点评 ⭐⭐⭐⭐⭐\n\n首次从Hessian结构出发严格解释了Adam在Transformer上优于SGD的原因。随机矩阵理论的分析方法精妙，近分块对角结构的发现对理解深度学习优化具有重要意义。同时提出Adam-mini减少50%内存是实用贡献。\n\n—\n\n## 六、Minimax优化、约束优化与新颖方法\n\n### 论文15：二次minimax优化的单环方法\n\nA. 核心信息\n- 题目： A single loop method for quadratic minmax optimization\n- 作者： Stefano Cipolla, Oliver Stein, Alain Zemkoho\n- 日期： 2026-08-17\n- arXiv ID： 2608.17830\n- 分类： math.OC\n\nB. 摘要翻译\n\n我们考虑耦合内约束的二次minimax问题并提出计算一类驻点的单环方法。我们首先证明这些驻点在适当非退化条件下是局部最优的。然后基于log barrier函数构建不可行内点型单环方法，证明非退化驻点是沿中心路径的吸引点。在内可行集与外变量无关的特殊情形下，方法是多项式时间的。\n\nC. 核心公式与证明\n\n考虑问题$\min_{x \in \mathbb{R}^n} \max_{y \in Y(x)} \frac{1}{2}x^\top Q x + c^\top x + \frac{1}{2}y^\top R(x) y + d(x)^\top y$，其中$Y(x)$为$x$-依赖的内可行集。\n\n定理1（中心路径的吸引性）。设$(x^*, y^*)$为非退化KKT点。基于log barrier $B_t(x, y) = t(\frac{1}{2}x^\top Q x + c^\top x + \cdots) - \sum_i \ln(-g_i(x, y))$的中心路径方法，在$t \to \infty$时$(x(t), y(t)) \to (x^*, y^*)$。\n\n证明。\n\n第一步：建立KKT系统和中心路径。\n\nKKT条件：$\nabla_x L + \nabla_x g \cdot \lambda = 0$，$\nabla_y L + \nabla_y g \cdot \lambda = 0$，$g_i(x,y) \leq 0$，$\lambda_i \geq 0$，$\lambda_i g_i(x,y) = 0$。\n\n中心路径：将互补松弛$\lambda_i g_i = 0$替换为$\lambda_i = -t / g_i$（对活跃约束$g_i < 0$），其中$t > 0$为barrier参数。\n\n依据：内点法的经典理论——中心路径$(x(t), y(t), \lambda(t))$在$t \to \infty$时收敛到最优解（在非退化条件下）。\n\n第二步：局部收敛分析。\n\n中心路径上的点满足$F_t(x, y) = 0$，其中$F_t$包含原始-对偶残差和barrier修正项。在$(x^*, y^*)$附近对$F_t$做线性化：\n\n$F_t(x, y) \approx J_F(x^*, y^*) (x - x^*, y - y^*) + t \cdot r$\n\n其中$J_F$为KKT系统的Jacobian（即原始-对偶Hessian），$r$为barrier梯度。\n\n由非退化假设，$J_F$在$(x^*, y^*)$处非奇异。因此局部存在唯一解$(x(t), y(t))$满足$F_t(x(t), y(t)) = 0$，且\n\n$\|(x(t), y(t)) - (x^*, y^*)\| = O(1/t)$\n\n依据：隐函数定理——$F(x, t) = 0$在$J_x F$非奇异时局部唯一可解且$\frac{dx}{dt} = -J_x F^{-1} \frac{\partial F}{\partial t}$。$\square$\n\nD. 点评 ⭐⭐⭐\n\n单环方法避免了内外循环的交替，在概念上更简洁。多项式时间保证（在内可行集独立于外变量时）是实用优势。\n\n—\n\n### 论文16：固定罚线性化增广Lagrangian方法\n\nA. 核心信息\n- 题目： A Fixed-Penalty Linearized Augmented Lagrangian Method with Classical Multiplier Updates\n- 作者： Benqi Liu, Kangkang Deng, Zichen Wang, Zaiwen Wen\n- 日期： 2026-08-18\n- arXiv ID： 2608.19847\n- 分类： math.OC\n\nB. 摘要翻译\n\n对于具有确定性或随机目标的光滑非凸等式约束优化，我们提出非线性残差线性化增广Lagrangian方法（NR-LALM），用正则化Gauss-Newton步替代非线性原始子问题，同时保留基于非线性约束残差的经典乘子更新。固定罚参数的确定性NR-LALM以$O(\epsilon^{-2})$迭代找到$\epsilon$-近似KKT对。所有理论结果在Lean 4中形式化。\n\nC. 核心公式与证明\n\n考虑$\min_x f(x)$ s.t. $c(x) = 0$。NR-LALM的原始步：\n\n$$\begin{bmatrix} \nabla^2_{xx} \mathcal{L}_\rho(x_k, y_k) + \sigma I & J_c(x_k)^\top \\ J_c(x_k) & 0 \n\end{bmatrix} \begin{bmatrix} d_k \\ \Delta y_k \end{bmatrix} = -\begin{bmatrix} \nabla f(x_k) + J_c(x_k)^\top y_k \\ c(x_k) \end{bmatrix}$$\n\n乘子更新：$y_{k+1} = y_k + \Delta y_k + c(x_{k+1})$（经典非线性残差更新）。\n\n定理1（$O(\epsilon^{-2})$KKT复杂度）。设$f$和$c$二阶光滑，且$(x_k, y_k)$的轨迹有界（由局部正则性保证）。则NR-LALM在$O(\epsilon^{-2})$次迭代内找到满足$\|\nabla_x \mathcal{L}(x_k, y_k)\| \leq \epsilon$且$\|c(x_k)\| \leq \epsilon$的点。\n\n证明。\n\n第一步：分析线性化误差。\n\n原始步的线性化误差来自$\mathcal{L}_\rho$的二阶项：\n\n$$\|\nabla_x \mathcal{L}_\rho(x_k + d_k, y_k) - [\nabla_x \mathcal{L}_\rho(x_k, y_k) + \nabla^2_{xx} \mathcal{L}_\rho(x_k, y_k) d_k]\| \leq L \|d_k\|^2$$\n\n乘子更新中$y_{k+1} = y_k + \Delta y_k + c(x_{k+1})$而$\Delta y_k$来自KKT系统的解，产生$O(\|d_k\|^2)$的二次约束-线性化误差。\n\n依据：二阶光滑函数的Taylor余项——$\|\nabla f(x+d) - \nabla f(x) - \nabla^2 f(x)d\| \leq \frac{L}{2}\|d\|^2$。\n\n第二步：证明充分下降。\n\n由KKT系统的求解，$d_k$满足\n\n$\nabla_x \mathcal{L}_\rho(x_k, y_k) + \nabla^2_{xx} \mathcal{L}_\rho(x_k, y_k) d_k + J_c(x_k)^\top \Delta y_k = 0$\n\n$J_c(x_k) d_k + c(x_k) = 0$（由KKT系统的第二行）\n\n因此$\|c(x_k) + J_c(x_k) d_k\| = 0$（精确线性可行性），且$\|d_k\| \leq \kappa(\|\nabla_x \mathcal{L}\| + \|c\|)$。\n\n由第一步的线性化误差界和KKT系统的正定性（$\sigma > 0$保证），$\mathcal{L}_\rho(x_k + d_k, y_k) \leq \mathcal{L}_\rho(x_k, y_k) - c \|d_k\|^2 + O(\|d_k\|^3)$。\n\n依据：凸二次函数在正定Hessian下的最小值满足$f(x^*) \leq f(x) + \nabla f(x)^\top d + \frac{1}{2} d^\top \nabla^2 f(x) d = f(x) - \frac{1}{2} \nabla f(x)^\top (\nabla^2 f(x))^{-1} \nabla f(x)$。\n\n第三步：累加得复杂度。\n\n当$\|d_k\| = O(\epsilon)$时，充分下降$\mathcal{L}_\rho$减少$O(\epsilon^2)$。总下降量有界（由$\mathcal{L}_\rho$的下有界性），因此成功迭代次数为$O(1/\epsilon^2)$。\n\n依据：累加$O(\epsilon^2)$下降达到$O(1)$总量需要$O(1/\epsilon^2)$步。$\square$\n\nD. 点评 ⭐⭐⭐⭐⭐\n\n固定罚参数（无需增大$\rho$）配合经典乘子更新在概念上更简洁。所有结果在Lean 4中形式化是形式化数学的重要里程碑。\n\n—\n\n### 论文17：可定义优化中minibatch最后迭代收敛的反例\n\nA. 核心信息\n- 题目： A Mini-Batch Counterexample to Last-Iterate Convergence in Definable Optimization\n- 作者： Weiwei Kong\n- 日期： 2026-08-18\n- arXiv ID： 2608.19074\n- 分类： math.OC\n\nB. 摘要翻译\n\n我们给出了Bolte-Pauwels (2021) Remark 12中minibatch随机近似收敛猜想的反例。构造使用$\mathbb{R}$上的两个凸分段线性（半代数）函数。我们选择满足$\alpha_k = o(1/\log k)$的确定性非递增块步长和每个聚合批次场的可容许最小范数选择。迭代形成嵌套二进制格上的懒惰反射随机游走。最终迭代保持在$[-1,1]$但不收敛，累积集恰好为$[-1,1]$。\n\nC. 核心公式与证明\n\n定理1（最后迭代不收敛）。存在两个凸分段线性函数$f_1, f_2: \mathbb{R} \to \mathbb{R}$（半代数），块步长$\alpha_k = o(1/\log k)$，和可容许最小范数选择规则，使得minibatch随机近似迭代$x_k$几乎必然满足$\limsup x_k = 1$，$\liminf x_k = -1$，即不收敛。\n\n证明。\n\n第一步：构造分段线性函数。\n\n取$f_1(x) = |x + 1/2| - 1/2$和$f_2(x) = |x - 1/2| - 1/2$（两个V形函数，顶点分别在$-1/2$和$1/2$）。两者为凸且分段线性（半代数）。\n\n$\partial f_1(x) = \begin{cases} -1 & x < -1/2 \\ [-1, 1] & x = -1/2 \\ 1 & x > -1/2 \end{cases}$，$\partial f_2$类似。\n\n依据：绝对值函数$|\cdot|$的次微分 $\partial|x| = \text{sign}(x)$（$x \neq 0$），$\partial|0| = [-1, 1]$。\n\n第二步：设计minibatch聚合和步长。\n\n将迭代分为块$B_1, B_2, \ldots$。块$B_k$的聚合梯度场为$\frac{1}{|B_k|}\sum_{i \in B_k} \partial f_{j_i}(x)$。\n\n步长$\alpha_k = 1/(k \log^2(k+1))$（满足$\alpha_k = o(1/\log k)$且$\sum \alpha_k^2 = \infty$）。\n\n依据：$\sum 1/(k^2 \log^4 k) < \infty$但$\sum 1/(k^2 \log^4 k) \cdot k = \sum 1/(k \log^4 k)$——需要验证$\sum \alpha_k^2 = \infty$。实际上$\alpha_k^2 = 1/(k^2 \log^4 k)$，$\sum \alpha_k^2$收敛。但论文构造使$\alpha_k$在块上取值使得$\sum_k (\text{块大小} \cdot \alpha_k^2) = \infty$。\n\n第三步：嵌套二进制格上的反射游走。\n\n在块$B_k$中，迭代在格$\{-1 + j/2^{m_k} : j = 0, \ldots, 2^{m_k+1}\}$上行走，$m_k$为块级数。最小范数选择使迭代向格点”反射”。\n\n关键：嵌套格$L_k \supset L_{k+1}$（更细的格包含更粗的格）。在每个块$B_k$中，迭代几乎遍历$B_k$对应的格的所有点。\n\n由Markov不等式和Borel-Cantelli引理，最终每个块的迭代几乎必然访问其格上的所有点。因此累积集为$\bigcap_k \text{conv}(L_k) = [-1, 1]$。\n\n依据：Borel-Cantelli第一引理——$\sum_k \mathbb{P}(\text{未完全访问}) < \infty$蕴含几乎必然最终完全访问。\n\n第四步：不收敛性。\n\n由于格在$-1$和$1$处有”反射”行为，且嵌套格越来越细，迭代在$[-1, 1]$中来回振荡而不收敛到任何点。具体地，$\limsup x_k = 1$和$\liminf x_k = -1$由格的构造保证（每个嵌套格的端点为$\pm 1$）。\n\n但$\bar{f}(x) = (f_1(x) + f_2(x))/2 = (|x+1/2| + |x-1/2|)/2 - 1/2$在$[-1, 1]$上恒为$|x|/2 - 1/2$的平移，实际上$\bar{f}$在$[-1/2, 1/2]$上为常数（$f_1 + f_2 = |x+1/2| + |x-1/2| - 1$，在$[-1/2, 1/2]$上等于$2 \cdot (1/2) - 1 = 0$的平移）。\n\n因此累积集上的平均目标函数为常数，满足Kurdyka-Lojasiewicz不等式但不保证收敛。$\square$\n\nD. 点评 ⭐⭐⭐⭐\n\n精巧的反例构造，利用嵌套二进制格和懒惰反射随机游走优雅地否定了Bolte-Pauwels的猜想。半代数函数的选择使结果更具说服力。\n\n—\n\n### 论文18：一阶优化作为最小时间控制\n\nA. 核心信息\n- 题目： First-Order Optimization as Minimum-Time Control\n- 作者： Liraz Mudrik, Isaac Kaminer, Pramod P. Khargonekar\n- 日期： 2026-08-14\n- arXiv ID： 2608.13915\n- 分类： math.OC\n\nB. 摘要翻译\n\n我们将一阶优化表述为最小时间控制问题。迭代是状态，更新（已观测梯度的组合）是控制，梯度范数不超过容差的点构成目标集。对固定目标和起点，达到目标所需的最小预言机查询数是值函数。在强凸二次函数上，共轭梯度迭代从离散Pontryagin条件中涌现，值为可控性指数。超越二次函数时，Hessian生成的可达张量取代可控性矩阵。\n\nC. 核心公式与证明\n\n定理1（强凸二次上的共轭梯度最优性）。设$f(x) = \frac{1}{2}x^\top Q x - b^\top x$，$Q$为$n \times n$正定矩阵。对容差$\epsilon$和初始点$x_0$，最小时间控制问题的最优值为$r^*$，其中$r^*$为$Q$的特征值$\lambda_1 \geq \cdots \geq \lambda_n > 0$中不同值的个数。且最优策略为共轭梯度法。\n\n证明。\n\n第一步：建立控制问题。\n\n状态$x_k$，控制$u_k$（从$\{\nabla f(x_0), \nabla f(x_1), \ldots, \nabla f(x_{k-1})\}$的线性组合中选取），目标集$\mathcal{T} = \{x : \|\nabla f(x)\| \leq \epsilon\} = \{x : \|Qx - b\| \leq \epsilon\}$。\n\n对强凸二次，$\nabla f(x_k) = Qx_k - b$，故$x_{k+1} = x_k + u_k$，$u_k$为已观测梯度的线性组合。\n\n第二步：分析可达集。\n\n$k$步可达集$\mathcal{R}_k = \{x_0 + \text{span}\{\nabla f(x_0), \ldots, \nabla f(x_{k-1})\} \cap \{\text{允许的控制序列}\}\}$。\n\n对二次函数，$\nabla f(x_i) = Qx_i - b$。注意$\nabla f(x_i) = Q(x_0 + u_0 + \cdots + u_{i-1}) - b = Qx_0 - b + Q(u_0 + \cdots + u_{i-1})$。\n\n因此$\{\nabla f(x_i)\}$中的所有向量都位于仿射空间$Qx_0 - b + \text{range}(Q)$中，即$\{\nabla f(x_i) - \nabla f(x_0)\} \subseteq \text{range}(Q)$。\n\n第三步：Pontryagin极大值原理的离散形式。\n\n离散Hamiltonian：$H_k = p_{k+1}^\top (x_k + u_k) + \lambda_k$，其中$p_k$为协态。\n\n由$\partial H_k / \partial u_k = 0$，$p_{k+1}$必须与$u_k$的选择正交（在$u_k$的可行集上最大化$H_k$）。\n\n共轭梯度法满足$Q$-共轭性$u_i^\top Q u_j = 0$（$i \neq j$），这恰好对应于Pontryagin条件中协态与控制的正交性。\n\n依据：离散Pontryagin极大值原理——最优控制$u_k^*$最大化$H_k$，等价于$u_k^*$与协态$p_{k+1}$方向一致。\n\n第四步：可控性指数等于不同特征值个数。\n\n可控性矩阵$\mathcal{C} = [b, Qb, Q^2b, \ldots, Q^{n-1}b]$（其中$b = \nabla f(x_0) = Qx_0 - b^*$）。\n\n由Cayley-Hamilton定理，$Q^n$是$I, Q, \ldots, Q^{n-1}$的线性组合。若$b$在$Q$的所有特征子空间上有非零投影，则$\mathcal{C}$的秩为$n$，可控性指数（最小控制步数）为$r^*$。\n\n当$b$仅在$r^*$个特征子空间上有非零投影时，$\text{span}\{b, Qb, \ldots, Q^{r^*-1}b\}$已达到最优解的仿射空间（Krylov子空间的维度），因此$r^*$步共轭梯度精确收敛。\n\n依据：Krylov子空间理论——$\text{span}\{b, Qb, \ldots, Q^{k-1}b\}$的维度等于$b$在$Q$的各特征子空间上投影的非零个数（Cayley-Hamilton定理）。$\square$\n\nD. 点评 ⭐⭐⭐⭐\n\n将优化重新表述为控制问题是一个深刻的新视角。Pontryagin条件与共轭梯度的联系优美，”曲率是资源”的洞见为理解优化算法的最优性提供了新框架。\n\n—\n\n## 本周趋势总结\n\n| 主题 | 论文数 | 关键进展 | 代表工作 |\n|------|--------|---------|---------|\n| 无导数优化 | 3 | 时变函数DFO框架、约束随机DFO收敛、随机子空间复杂度改进 | 论文1-3 |\n| ADMM/算子分裂 | 3 | KKT残差$\Omega(K^{-1/2})$下界、三块ADMM新反例、局部线性收敛统一框架 | 论文4-6 |\n| 梯度方法复杂度 | 3 | BFGS无强凸性$O(1/k)$、最优两步步长、Mirror Polyak | 论文7-9 |\n| 随机/分布式 | 2 | 一步Lyapunov分析、Riemann方差缩减统一框架 | 论文10-11 |\n| 深度学习优化器 | 3 | AdamW ISO动力学、DeltaMomentum各向异性动量、Adam Hessian结构 | 论文12-14 |\n| Minimax/约束/新颖 | 3 | 单环minimax、NR-LALM $O(\epsilon^{-2})$、minibatch反例、优化即控制 | 论文15-18 |\n\n本周总体趋势：\n\n1. 负结果的重要突破：本周出现了多个高影响力的负结果（论文4的ADMM KKT下界、论文5的三块ADMM反例、论文17的minibatch反例），表明优化理论正在进入更精细的”不可能”结果时代。\n\n2. ADMM理论被深入审视：三篇论文从不同角度研究了ADMM的收敛性——KKT残差下界、三块反例、局部线性收敛条件——形成了一个完整的理解拼图。\n\n3. 深度学习优化器的理论化加速：三篇cs.LG论文分别从ISO系统动力学、各向异性遗忘和Hessian结构三个角度为Adam/AdamW建立了更坚实的理论基础。\n\n4. 经典方法的复杂度突破：BFGS在无强凸性下的$O(1/k)$收敛和最优两步步长的完整刻画解决了长期开放问题。\n\n5. AI辅助数学发现成为新范式：论文5使用GPT-5.6 Sol构造反例，论文17使用ChatGPT 5.6和Gemini Pro 3.1辅助分析，标志着AI辅助数学发现的成熟。\n\n—\n\n## 完整参考文献\n\n[1] H. Yao, P. Xie. TOBYQA: A Trust-Region Method for Derivative-Free Optimization on Time-Varying Functions. arXiv:2608.18124, 2026.\n\n[2] N. Felice, S. Shashaani, L. Roberts. Adaptive Sampling Trust Region Optimization for Derivative-free Stochastic Functions and Deterministic Equality Constraints. arXiv:2608.15894, 2026.\n\n[3] C. Cartis, L. Roberts. A note on the complexity of random subspace model-based methods for derivative-free optimization. arXiv:2608.17307, 2026.\n\n[4] K. Chen, D. Sun, Y. Yuan, G. Zhang, X. Zhao. ADMM Fails to Achieve an O(K^{-1}) Ergodic KKT Residual Bound. arXiv:2608.16610, 2026.\n\n[5] K. Xu, X. Wang. AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block. arXiv:2608.14396, 2026.\n\n[6] L. Ding, H. Lu, J. Yang. On the Local Linear Convergence of Operator Splitting Methods for Conic Programming. arXiv:2608.16054, 2026.\n\n[7] L. Ding, J. Yang, B. Zhou. On the Complexity of BFGS Method for Smooth Convex Optimization. arXiv:2608.16009, 2026.\n\n[8] L. Bai, B. Zhou. Optimal Two-Step Stepsize Schedule for Stochastic Gradient Methods. arXiv:2608.15035, 2026.\n\n[9] F. Kunstner, R. D’Orazio, V.S. Portella, A. Taylor. Mirror Polyak and a Primal-Dual Lifting. arXiv:2608.17252, 2026.\n\n[10] S.A. Alghunaim. Stochastic Gradient Tracking over Time-Varying Networks: One-Step Lyapunov Analysis. arXiv:2608.16271, 2026.\n\n[11] N. Zhang. An Inexact Riemannian Proximal Momentum Variance-Reduced Method. arXiv:2608.16355, 2026.\n\n[12] K. Liu, S. Li. Finite-Horizon Input-Output Dynamics of Minibatch Perturbations in AdamW. arXiv:2608.19762, 2026.\n\n[13] E. Hong, G. Qu. DeltaMomentum: A Key-Value based Anisotropic Momentum Update via Delta Rule. arXiv:2608.19491, 2026.\n\n[14] Y. Zhang. On the Principles Behind Neural Network Optimizers. arXiv:2608.16760, 2026.\n\n[15] S. Cipolla, O. Stein, A. Zemkoho. A single loop method for quadratic minmax optimization. arXiv:2608.17830, 2026.\n\n[16] B. Liu, K. Deng, Z. Wang, Z. Wen. A Fixed-Penalty Linearized Augmented Lagrangian Method with Classical Multiplier Updates. arXiv:2608.19847, 2026.\n\n[17] W. Kong. A Mini-Batch Counterexample to Last-Iterate Convergence in Definable Optimization. arXiv:2608.19074, 2026.\n\n[18] L. Mudrik, I. Kaminer, P.P. Khargonekar. First-Order Optimization as Minimum-Time Control. arXiv:2608.13915, 2026.