OpenClaw · 小龙虾
arXiv 优化论文周报
报告日期：2026-06-06
arXiv 优化论文周报
报告周期：2026年5月31日（周日）— 2026年6月6日（周六）
生成时间：2026年6月6日 10:00（北京时间）
数据源：arXiv math.OC + cs.LG 交叉列表
论文总数：18篇
亮点摘要
- 扰动q-Tsallis自协调障碍函数（2606.04348）：首次精确刻画了半定规划中q-Tsallis障碍函数的自协调性阈值$q=2$，在$q\in(1,2]$时无条件成立，$q>2$时全局失效，同时实现了$\kappa^{-(q-1)}$谱鲁棒性改进。
- 随机单调包含的二阶分裂动力学（2606.06280）：提出处理决策依赖分布的二阶split-DIN连续时间动力学，证明均衡点存在唯一性，并在消失阻尼下强收敛、Polyak阻尼下指数收敛。
- 分布式事件触发资源分配（2606.03277）：在仅假设一般凸性的条件下，提出残差感知动态事件触发算法，实现通信效率与收敛性的平衡，强凸时达到线性收敛。
- Heavy-Tail噪声下的Lévy Mirror Flow（2606.03769）：提出基于$\alpha$-稳定Lévy过程的LMF算法，在仅有$p$阶矩条件下实现$O(\varepsilon^{-p/(p-1)})$凸复杂度和$\tilde{O}(\varepsilon^{-1/(p-1)})$强凸复杂度。
- 无导数优化中的单点正则化（2606.04757）：通过vanilla one-point反馈建立无导数优化的精确下界，证明在线性和参数化场景下新的匹配上界可达。
一、内点法与自协调障碍函数
P1. 扰动q-Tsallis自协调障碍函数用于谱鲁棒半定规划
题目：A Perturbed q-Tsallis Self-Concordant Barrier for Spectrally Robust Semidefinite Programming
作者：Fabricio Alves Barbosa da Silva (FIOCRUZ, Rio de Janeiro, Brazil)
日期：2026年6月5日 | arXiv ID：2606.04348
分类：math.OC (90C22, 90C25, 90C51, 65F55, 90C06)
中文摘要：
本文引入并分析了一种用于半定规划（SDP）的扰动q-Tsallis障碍函数，定义为正定矩阵锥上经典log-det障碍的谱扰动。该障碍通过参数$q>1$和$\eta\geq 0$控制的Tsallis型矩阵幂项引入特征值自适应硬化。主要理论贡献是对障碍函数微分自协调性区域的精确刻画：证明$\phi_{q,\eta}$在$\mathbb{S}^n_{++}$的内部对所有$\eta\geq 0$是微分自协调的，当且仅当$q\in(1,2]$，确立了$q=2$处的精确边界。进一步建立了谱鲁棒性定理，证明中心路径对小特征值方向的扰动灵敏度以$\kappa(X^*)^{-(q-1)}$的速率衰减。数值实验验证了理论预测，展示了改进的鲁棒性和显著的计算加速。
C. 核心公式与证明
核心定义（扰动q-Tsallis障碍函数）：
对于$q>1$，$\eta\geq 0$，$X\in\mathbb{S}^n_{++}$：
$$\phi_{q,\eta}(X)=-\log\det(X)+\frac{\eta}{q-1}\left[\mathrm{tr}\bigl(X^{-(q-1)}\bigr)-n\right]$$
辅助引理：
引理3.5（Davis 1957）：谱函数$f(\lambda_1,\dots,\lambda_n)=\sum_i g(\lambda_i)$在$\mathbb{S}^n_{++}$上凸，当且仅当$g$在$(0,\infty)$上凸。
引理3.6（Daleckii–Krein）：对于$F(X)=\mathrm{tr}(g(X))$和$X=Q\mathrm{diag}(\lambda)Q^\top$，
$$D^2 F(X)[H,H]=\sum_{i,j}g^{[2]}(\lambda_i,\lambda_j)\widetilde{H}_{ij}^2$$
其中$g^{[2]}(\lambda,\mu)=\frac{g'(\lambda)-g'(\mu)}{\lambda-\mu}$（$\lambda=\mu$时为$g''(\lambda)$）。
定理5.1（$\phi_{q,\eta}$的自协调性——完整刻画）：
(i) 无条件区域：对于$q\in(1,2]$和任意$\eta\geq 0$，$\phi_{q,\eta}$在$\mathrm{int}(\mathbb{S}^n_{+})$上满足微分自协调不等式，且在$X\to\partial\mathbb{S}^n_{+}$时$\phi_{q,\eta}(X)\to+\infty$。边界$q=2$是精确的。
(ii) 全局障碍：对于$q>2$和任意$\eta>0$，$\phi_{q,\eta}$在整个$\mathbb{S}^n_{++}$上不是标准自协调障碍函数。
(iii) 局部充分条件：对于$q>2$，若迭代量保持在紧集$\{\lambda_i(X)\leq\Lambda\}$内，且$\eta\geq u_{\mathrm{zero}}(q)\cdot\Lambda^{q-1}$，则局部自协调性成立。
完整证明：
步骤1：计算标量函数的各阶导数。
标量函数为$g(\lambda)=-\log\lambda+\frac{\eta}{q-1}\lambda^{-(q-1)}$。逐阶求导：
$$g'(\lambda)=-\lambda^{-1}-\eta\lambda^{-q}$$
依据：幂函数求导法则$\frac{d}{d\lambda}\lambda^{-r}=-r\lambda^{-(r+1)}$，分别对$r=1$和$r=q$应用。
$$g''(\lambda)=\lambda^{-2}+\eta q\lambda^{-(q+1)}>0$$
依据：对$g'(\lambda)$再求导，$\frac{d}{d\lambda}(-\lambda^{-1})=\lambda^{-2}$，$\frac{d}{d\lambda}(-\eta\lambda^{-q})=\eta q\lambda^{-(q+1)}$。两项均为正，故严格凸。
$$g'''(\lambda)=-2\lambda^{-3}-\eta q(q+1)\lambda^{-(q+2)}$$
依据：对$g''(\lambda)$再求导，$\frac{d}{d\lambda}(\lambda^{-2})=-2\lambda^{-3}$，$\frac{d}{d\lambda}(\eta q\lambda^{-(q+1)})=-\eta q(q+1)\lambda^{-(q+2)}$。
步骤2：标量自协调不等式的齐次性约化。
自协调条件为$|g'''(\lambda)|\leq 2(g''(\lambda))^{3/2}$。将$|g'''|$和$g''$的乘以$\lambda^3$进行齐次化：
$$|g'''(\lambda)|\cdot\lambda^3 = 2+\eta q(q+1)\lambda^{-(q-1)}$$
$$g''(\lambda)^{3/2}\cdot\lambda^3 = (1+\eta q\lambda^{-(q+1)}\cdot\lambda^2)^{3/2}\cdot\lambda^3 = \lambda^3(1+\eta q\lambda^{-(q-1)})^{3/2}$$
设$u:=\eta\lambda^{-(q-1)}\geq 0$，自协调条件等价于：
$$\psi(u):=2(1+qu)^{3/2}-2-q(q+1)u\geq 0,\quad u\geq 0$$
步骤3：分析标量函数$\psi(u)$的性质。
计算$\psi$的二阶导数：
$$\psi''(u)=\frac{3q^2}{2(1+qu)^{1/2}}>0$$
依据：$\frac{d^2}{du^2}(1+qu)^{3/2}=\frac{3q^2}{4}(1+qu)^{-1/2}$，乘以2得到$\frac{3q^2}{2(1+qu)^{1/2}}$，为正，故$\psi$严格凸。
已知$\psi(0)=2\cdot 1^{3/2}-2=0$。
计算$\psi$的一阶导数在$u=0$处的值：
$$\psi'(u)=3q(1+qu)^{1/2}\cdot q - q(q+1) = 3q^2\sqrt{1+qu}-q(q+1)$$
$$\psi'(0)=3q^2-q(q+1)=q(3q-(q+1))=q(2-q)$$
步骤4：证明(i)——$q\in(1,2]$情形。
当$q\leq 2$时，$\psi'(0)=q(2-q)\geq 0$。由于$\psi$严格凸、$\psi(0)=0$且在$u=0$处非减，故对一切$u\geq 0$有$\psi(u)\geq 0$。
依据：严格凸函数若在某点导数非负且在该点值为零，则在该点右侧单调递增，故不会下降到负值。
步骤5：证明(ii)——$q>2$情形。
当$q>2$时，$\psi'(0)=q(2-q)<0$。由于$\psi$严格凸且$\psi(0)=0$，导数在原点为负意味着$\psi$在$u$接近$0^+$时为负。注意$u=\eta\lambda^{-(q-1)}$，当$\lambda\to\infty$时$u\to 0^+$。因此对于大$\lambda$，不等式$\psi(u)\geq 0$被违反。
步骤6：证明(iii)——局部充分条件。
由于$\psi$严格凸且$\psi\to+\infty$（当$u\to+\infty$），$\psi$在某个$u_{\mathrm{zero}}(q)>0$处回到零值，且$\psi(u)\geq 0$对所有$u\geq u_{\mathrm{zero}}$成立。
转化回原变量：自协调不等式成立当$\eta\lambda^{-(q-1)}\geq u_{\mathrm{zero}}(q)$，即$\lambda\leq(\eta/u_{\mathrm{zero}})^{1/(q-1)}$。当所有迭代量满足$\lambda_i(X)\leq\Lambda$时，只需$\eta\geq u_{\mathrm{zero}}(q)\cdot\Lambda^{q-1}$。
$u_{\mathrm{zero}}(q)$的闭式推导：设$t=(1+qu)^{1/2}$，则$\psi(u)=0$变为$2t^3-(q+1)t^2+(q-1)=0$。$t=1$是根，分解为$(t-1)[2t^2-(q-1)t-(q-1)]=0$。二次因子正根为：
$$t_{\mathrm{zero}}(q)=\frac{(q-1)+\sqrt{(q-1)(q+7)}}{4}$$
$$u_{\mathrm{zero}}(q)=\frac{t_{\mathrm{zero}}(q)^2-1}{q}=\frac{[(q-1)+\sqrt{(q-1)(q+7)}]^2-16}{16q}$$
定理6.1（中心路径的谱鲁棒性）：
在定理5.1的假设下，令$M:=\nabla^2\phi_{q,\eta}(X^*)$，对任意扰动$\Delta b\in\mathbb{R}^m$：
$$\|X^*(b+\Delta b)-X^*(b)\|_F\leq\frac{C_{\mathcal{A}}}{\mu}\cdot\frac{\lambda_{\max}(X^*)^2}{1+\eta q\,\lambda_{\max}(X^*)^{-(q-1)}}\|\Delta b\|_2+o(\|\Delta b\|_2)$$
其中$C_{\mathcal{A}}>0$取决于$\mathcal{A}$和$\lambda_{\min}(X^*)$。每个特征方向$H=e_ke_k^\top$：
$$|[\Delta X]_{kk}|\leq\frac{C_{\mathcal{A}}^{(k)}}{\mu}\cdot\frac{\lambda_k^2}{1+\eta q\,\lambda_k^{-(q-1)}}\|\Delta b\|_2$$
当$\lambda_k\to 0^+$时：
$$\frac{\lambda_k^2}{1+\eta q\lambda_k^{-(q-1)}}\sim\frac{\lambda_k^{q+1}}{\eta q}\longrightarrow 0$$
衰减速率为$q+1>2$，严格快于$\eta=0$时的速率$2$。
证明：
步骤1：隐式微分。中心路径点$X^*(b)$满足：
$$C+\mu\nabla\phi_{q,\eta}(X^*)+\mathcal{A}^*(y^*)=0,\quad\mathcal{A}(X^*)=b$$
对$b$求方向导数：
$$\mu M[\Delta X]+\mathcal{A}^*(\Delta y)=0,\quad\mathcal{A}(\Delta X)=\Delta b$$
其中$M:=\nabla^2\phi_{q,\eta}(X^*)$。
依据：中心路径方程对$b$的隐函数定理，梯度$\nabla\phi_{q,\eta}$的微分给出Hessian作用。
步骤2：消元与范数界。消去$\Delta y$：
$$\Delta X=\frac{1}{\mu}M^{-1}\mathcal{A}^*(\mathcal{A}M^{-1}\mathcal{A}^*)^{-1}\Delta b$$
取Frobenius范数，由次乘法性：
$$\|\Delta X\|_F\leq\frac{C_{\mathcal{A}}}{\mu}\|M^{-1}\|_2\|\Delta b\|_2+o(\|\Delta b\|_2)$$
依据：算子范数的次乘法性$\|AB\|_2\leq\|A\|_2\|B\|_2$和$\mathcal{A}$、$\mathcal{A}^*$的有界性。
步骤3：计算$\|M^{-1}\|_2$。在$X^*$的特征基下，$M$的对角分量为：
$$a_k=\lambda_k^{-2}(1+\eta q\lambda_k^{-(q-1)})$$
函数$s\mapsto s^{-2}(1+\eta qs^{-(q-1)})$严格递减（导数$-2s^{-3}-\eta q(q+1)s^{-(q+2)}<0$），故最小值在$a_1$（$\lambda_{\max}$方向）取得：
$$\lambda_{\min}(M)=a_1=\lambda_{\max}(X^*)^{-2}[1+\eta q\,\lambda_{\max}(X^*)^{-(q-1)}]$$
因此$\|M^{-1}\|_2=\lambda_{\max}(X^*)^2/(1+\eta q\,\lambda_{\max}(X^*)^{-(q-1)})$。代入步骤2得定理结论。
推论6.3（条件数缩放的谱鲁棒性）：
归一化$\lambda_{\max}(X^*)=1$，$\kappa=\lambda_{\max}/\lambda_{\min}$，在最小特征值方向$e_ne_n^\top$：
$$|[\Delta X]_{nn}|\leq\frac{C_{\mathcal{A}}^{(n)}}{\mu}\cdot\frac{\kappa^{-2}}{1+\eta q\,\kappa^{q-1}}\|\Delta b\|_2$$
改进因子为$\rho(\kappa)=\frac{1}{1+\eta q\,\kappa^{q-1}}\sim\frac{1}{\eta q}\kappa^{-(q-1)}$（$\kappa\to\infty$）。当$q=1.5$，$\eta=1$，$\kappa=100$时$\rho=0.0625$（93.8%减少）；$\kappa=1000$时$\rho\approx 0.021$（97.9%减少）。
D. 点评：⭐⭐⭐⭐⭐ 本周亮点。本文在半定规划内点法理论中做出了重要突破：精确刻画了q-Tsallis障碍函数的自协调性阈值，并建立了谱鲁棒性的定量改进。核心证明技巧是将矩阵自协调不等式约化为标量函数$\psi(u)$的分析，充分利用了严格凸性和边界行为。这一结果不仅具有理论深度，而且在ill-conditioned SDP（如鲁棒协方差估计、低秩矩阵补全）中有直接应用价值。Krylov加速方案将矩阵幂的计算成本从$O(n^3)$降至$O(nk_{\mathrm{Kry}}^2)$，在$n=150$时达到$7\times$加速。
P2. 自适应加速梯度方法的复杂度理论
题目：Complexity-Theoretic Analysis of Adaptive Accelerated Gradient Methods
作者：Shuvomoy Dasgupta, Kfir Y. Levy
日期：2026年6月4日 | arXiv ID：2606.03632
分类：cs.LG, math.OC
中文摘要：
本文从计算复杂度理论的角度分析了自适应加速梯度方法。作者考虑在黑盒优化框架中，自适应方法（如基于线搜索的Nesterov加速梯度法）是否能在不依赖问题参数（如Lipschitz常数$L$或强凸参数$\mu$）的条件下，达到$O(\sqrt{L/\varepsilon})$的最优收敛速率。研究建立了自适应方法的复杂性刻画，证明在特定正交变换不变假设下，自适应方法可以达到接近最优的速率，但一般情形下存在计算复杂度障碍。
C. 核心公式与证明
辅助引理：
引理1（Nesterov加速梯度法的最优性下界）：对于任意$k\leq\frac{1}{2}\sqrt{L/\mu}-1$次迭代的黑盒一阶方法，存在$L$-光滑$\mu$-强凸函数使得：
$$f(x_k)-f(x^*)\geq\left(\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}\right)^{2k}(f(x_0)-f(x^*))$$
（该引理来自Nesterov的经典下界构造，陈述精确，无需重新证明。）
定理2（自适应加速方法的收敛性保证）：
设$f$是$\mu$-强凸函数，其梯度为$L$-Lipschitz连续。自适应加速梯度方法在$k$次迭代后满足：
$$f(x_k)-f^*\leq C\left(\frac{\sqrt{L_k}-\sqrt{\mu}}{\sqrt{L_k}+\sqrt{\mu}}\right)^{2k}(f(x_0)-f^*)$$
其中$L_k$是第$k$步的自适应Lipschitz估计，$C$是仅依赖于方法的常数。
完整证明（证明骨架）：
步骤1：自适应线搜索的每步产生一个有效Lipschitz估计$L_k$，使得：
$$f(x_k)\leq f(x_{k-1})-\frac{\alpha_k}{2}\|\nabla f(x_{k-1})\|^2$$
依据：线搜索的充分下降条件，当步长$\alpha_k\leq 1/L_k$时，由$L_k$-光滑性保证。
步骤2：利用强凸下降不等式：
$$f(y)-f^*\geq\frac{\mu}{2}\|y-x^*\|^2$$
依据：$\mu$-强凸函数的一阶最优性条件的等价刻画。
步骤3：定义Lyapunov函数$V_k=\|x_k-x^*\|^2+\sigma_k\|y_k-x^*\|^2$（其中$\sigma_k$与加速参数相关），证明$V_{k+1}\leq\gamma_k V_k$，其中收缩因子$\gamma_k$依赖于$L_k$和$\mu$：
$$\gamma_k=\left(\frac{\sqrt{L_k}-\sqrt{\mu}}{\sqrt{L_k}+\sqrt{\mu}}\right)^2$$
依据：Nesterov势方法的经典Lyapunov分析框架，将自适应估计$L_k$代入标准分析中。
步骤4：递推展开得：
$$V_k\leq\prod_{j=0}^{k-1}\gamma_j\cdot V_0\leq\left(\frac{\sqrt{L_{\max}}-\sqrt{\mu}}{\sqrt{L_{\max}}+\sqrt{\mu}}\right)^{2k}V_0$$
其中$L_{\max}=\max_{j\leq k}L_j$。由$V_k$与目标函数值的单调关系，利用强凸性将$V_k$转化为$f(x_k)-f^*$的界。
步骤5：由于自适应方法保证$L_k\leq L$（线搜索机制确保估计不超过真实Lipschitz常数），$\gamma_k\leq\left(\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}\right)^2$，故收敛速率不超过最优方法。
D. 点评：⭐⭐⭐⭐ 本文将计算复杂度理论与自适应加速方法相结合，从理论计算机科学的角度为”自适应方法能否匹配最优速率”这一基本问题提供了部分回答。证明结构清晰，将自适应估计融入经典Lyapunov分析框架。局限性在于某些结论依赖于正交变换不变假设。
二、单调包含与随机优化动力学
P3. 决策依赖分布的二阶分裂动力学用于随机单调包含
题目：Second order splitting dynamics for stochastic monotone inclusions with closed loop distribution
作者：Wutao Si, Hamza Ennajic, Jalal Fadili
日期：2026年6月4日 | arXiv ID：2606.06280
分类：math.OC (34G25, 37N40, 46N10, 47H05, 49M30, 60J20)
中文摘要：
本文在Hilbert空间中研究寻找极大单调算子$A$与cocoercive算子$B_{\mathbf{m}_x}$之和的零点问题，该形式自然地捕捉了具有决策依赖分布的随机优化问题（又称表现性预测）。作者提出并分析了一种由分布评估的前向-后向分裂算子控制的连续时间二阶动力学系统（split-DIN）。在均匀单调性假设下，作者证明了均衡点的存在性和唯一性，并在采用消失黏性阻尼系数时证明了轨迹到均衡点的强收敛，同时获得了速度的快速渐近收敛率。进一步，当正则化算子强单调时，作者采用常数Polyak型阻尼并建立了全局指数收敛率。
C. 核心公式与证明
核心问题：寻找$\bar{x}\in\mathcal{H}$使得
$$0\in A(\bar{x})+\mathbb{E}_{\xi\sim\mathbf{m}_{\bar{x}}}[B(\bar{x},\xi)]$$
定义1（前向-后向算子）：对于$\lambda,\gamma>0$和概率测度族$\mathbf{m}$：
$$\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}}(x):=\frac{1}{\lambda}\left[x-J_{\gamma A}(x-\gamma\mathrm{B}_{\mathbf{m}}(x))\right]$$
其中$J_{\gamma A}:=(\mathrm{Id}+\gamma A)^{-1}$是$A$的预解式。
split-DIN动力学：
$$\ddot{x}(t)+\nu(t)\dot{x}(t)+\mathrm{T}_{\lambda(t),\gamma(t)}^{\mathbf{m}_{x(t)}}(x(t))+\omega\frac{\mathrm{d}}{\mathrm{d}t}\left(\mathrm{T}_{\lambda(t),\gamma(t)}^{\mathbf{m}_{x(t)}}(x(t))\right)=0$$
辅助引理：
引理1（期望算子的cocoercivity）：在假设2下，$B_{\mathbf{m}_x}(x)=\mathbb{E}_{\xi\sim\mathbf{m}_x}[B(x,\xi)]$是$\theta$-cocoercive的。
引理2（零点集等价）：$\mathrm{zer}(A+\mathrm{B}_{\mathbf{m}})=\mathrm{zer}(\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}})$。
引理3（间隙算子的性质）：定义$\mathrm{E}_{\lambda,\gamma}^{\bar{x}}(x)=\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}_x}(x)-\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}_{\bar{x}}}(x)$。在假设1、3下，对任意$y,z\in\mathcal{H}$：
(i) $\sup_{x\in\mathcal{H}}\|\mathrm{B}_{\mathbf{m}_y}(x)-\mathrm{B}_{\mathbf{m}_z}(x)\|\leq\beta\tau\|y-z\|$
(ii) $\|\mathrm{E}_{\lambda,\gamma}^{\bar{x}}(x)\|\leq\frac{\gamma}{\lambda}\beta\tau\|x-\bar{x}\|$
(iii) $\langle\mathrm{E}_{\lambda,\gamma}^{\bar{x}}(x),x-\bar{x}\rangle\geq\frac{\lambda}{2}\|\mathrm{E}_{\lambda,\gamma}^{\bar{x}}(x)\|^2-\frac{(1+\gamma\beta\tau)^2}{2\lambda}\|x-\bar{x}\|^2$
引理4（$\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}_{\bar{x}}}$的性质）：在假设1、2下，对任意$\lambda>0$和$\gamma\in(0,2\theta)$，$\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}_{\bar{x}}}$是$\lambda/2$-cocoercive的。
定理1（强收敛——消失阻尼）：
设$A$是均匀单调的（模$\phi$），满足$\phi(t)>\beta\tau t^2$对所有$t>0$。设$\lambda(t)=\lambda t^3$（$\lambda>\frac{4(1+\gamma\beta\tau)^2}{\alpha}$），$\gamma$常数，阻尼$\nu(t)=\alpha/t$（$\alpha\geq 3$），$\omega>0$常数。则split-DIN的解$x(\cdot)$满足：
$$\Psi_A(\|x(t)-\bar{x}\|)=o(1),\quad\mathbb{W}_1(\mathbf{m}_{x(t)},\mathbf{m}_{\bar{x}})=o(1)$$
其中$\Psi_A$是与$\phi$相关的Nemytskii映射。
证明骨架（逐步推导）：
步骤1：定义Lyapunov函数。设$\mathcal{V}(t)$是包含以下分量的能量函数：
$$\mathcal{V}(t)=\|x(t)-\bar{x}\|^2+\text{交叉项}+\text{Hessian阻尼修正}$$
依据：二阶惯性系统的标准Lyapunov分析，Hessian阻尼项$\omega\frac{d}{dt}\mathrm{T}(\cdot)$需要额外的修正项。
步骤2：对$\mathcal{V}$沿轨迹求导。
$$\dot{\mathcal{V}}(t)\leq -\nu(t)\|\dot{x}(t)\|^2+2\langle x(t)-\bar{x},\dot{x}(t)\rangle\cdot(-\nu(t))+\text{交叉项导数}+\text{间隙项}$$
依据：将split-DIN方程乘以$\dot{x}$并利用分部积分处理Hessian阻尼项。
步骤3：利用引理3控制间隙项。
$$\langle\mathrm{E}^{\bar{x}}(x),x-\bar{x}\rangle\geq\frac{\lambda}{2}\|\mathrm{E}^{\bar{x}}\|^2-\frac{(1+\gamma\beta\tau)^2}{2\lambda}\|x-\bar{x}\|^2$$
依据：引理3(iii)，该下界将间隙的内积分解为正项（自协调项）和负项（扰动项）。
步骤4：利用时间缩放$\lambda(t)=\lambda t^3$和阻尼$\nu(t)=\alpha/t$。
代入参数后，通过选择足够大的$\lambda$使得负项被正项吸收。关键不等式为：
$$\lambda>\frac{4(1+\gamma\beta\tau)^2}{\alpha}$$
确保Lyapunov函数的导数为负。
**步骤5：积分$\dot{\mathcal{V}}(t)$从$t_0$到$\infty$，利用$\alpha\geq 3$保证$\int_{t_0}^\infty\nu(t)\|\dot{x}(t)\|^2 dt<\infty$和$\int_{t_0}^\infty\frac{1}{t^3}\|x(t)-\bar{x}\|^2 dt<\infty$的收敛性。
依据：$\nu(t)=\alpha/t$，$1/t^3$的可积性，以及$a^2/t^3$和$b^2/t^3$的渐近行为。
**步骤6：由Fubini定理和非负级数的收敛性，推导$\lim_{t\to\infty}\Psi_A(\|x(t)-\bar{x}\|)=0$和$\lim_{t\to\infty}\mathbb{W}_1(\mathbf{m}_{x(t)},\mathbf{m}_{\bar{x}})=0$。
定理3（指数收敛——Polyak阻尼）：
设$A$是$\mu_A$-强单调的。设$\beta\tau/\mu_A<1$，$\lambda,\gamma$常数，阻尼$\nu=2\sqrt{\tilde{\mu}}$（Polyak型），其中$\tilde{\mu}=\frac{\gamma}{\lambda}\frac{\mu_A}{1+\gamma\mu_A}$。则：
$$\|x(t)-\bar{x}\|=\mathcal{O}(e^{-\frac{\sqrt{\tilde{\mu}}}{16}t}),\quad\mathbb{W}_1(\mathbf{m}_{x(t)},\mathbf{m}_{\bar{x}})=\mathcal{O}(e^{-\frac{\sqrt{\tilde{\mu}}}{16}t})$$
证明骨架：
步骤1：在强单调情形下，$\mathrm{T}_{\lambda,\gamma}^{\mathbf{m}_{\bar{x}}}$是$\tilde{\mu}$-强单调的（由引理4和强单调性传递）。常数阻尼$\nu=2\sqrt{\tilde{\mu}}$是经典的Polyak过阻尼条件。
依据：强单调+cocoercive算子之和仍保持强单调性，系数由$\tilde{\mu}=\frac{\gamma}{\lambda}\frac{\mu_A}{1+\gamma\mu_A}$给出。
步骤2：构造指数Lyapunov函数$\mathcal{V}(t)=e^{ct}\|x(t)-\bar{x}\|^2+\text{动能项}$，对合适常数$c>0$证明$\dot{\mathcal{V}}(t)\leq 0$。
依据：Polyak阻尼的指数衰减性质，通过选择$c=\sqrt{\tilde{\mu}}/16$（留出足够余量吸收$\mathrm{E}^{\bar{x}}$间隙项的影响）。
步骤3：由$\beta\tau/\mu_A<1$的条件，间隙项的系数严格小于1，保证指数衰减不被扰动破坏。
D. 点评：⭐⭐⭐⭐⭐ 本周亮点。本文在表现性预测（performative prediction）和单调包含的交叉领域做出了杰出贡献。将split-DIN框架（DIN系统的分裂变体）推广到决策依赖分布场景，同时处理了非光滑约束（通过预解式）和状态依赖性。两个主要定理分别建立了消失阻尼下的$o(1)$强收敛和Polyak阻尼下的指数收敛，覆盖了理论分析的两个核心设定。证明框架基于Lyapunov分析和间隙算子技术，技巧性强。
P4. Heavy-Tail噪声下的Lévy Mirror Flow：收敛复杂度
题目：Lévy Mirror Flow: Convergence Complexity under Heavy-Tailed Noise
作者：未知作者组
日期：2026年6月4日 | arXiv ID：2606.03769
分类：math.OC, cs.LG (65K10, 90C25, 60G51)
中文摘要：
本文研究了在仅有$p$阶矩条件（$1 辅助引理： 引理A（$p$-矩次高斯尾界）：若$\xi$满足$\mathbb{E}[|\xi|^p]\leq M^p$，则对任意$R>0$： $$\mathbb{P}(|\xi|>R)\leq\frac{M^p}{R^p}$$ 依据：Markov不等式直接应用于$|\xi|^p$。 引理B（Lévy测度密度）：$\alpha$-稳定Lévy过程的Lévy测度为$\nu(dx)=C|x|^{-(1+\alpha)}dx$，$\alpha\in(0,2]$。当$\alpha=p$时，大跳的频率与$p$-矩界匹配。 引理C（半群收缩性）：对于$\mu$-强凸函数$f$，镜像流$\mathrm{d}X_t=-\nabla f(X_t)\mathrm{d}t+\sqrt{2}\mathrm{d}W_t$满足： $$\mathbb{E}[\|X_t-X^*\|^2]\leq e^{-2\mu t}\|X_0-X^*\|^2+\frac{d}{\mu}(1-e^{-2\mu t})$$ 其中$d$为空间维数。 依据：Itô公式应用于$V(t)=\|X_t-X^*\|^2$，利用强凸性的梯度下降界。 定理1（LMF的SDE定义与凸收敛性）： Lévy Mirror Flow定义为以下SDE： $$\mathrm{d}X_t=-\eta\nabla f(X_{t-})\mathrm{d}t+\eta\cdot\mathrm{d}\mathcal{L}_t^{(\alpha)}$$ 其中$\mathcal{L}_t^{(\alpha)}$是带有Lévy测度$\nu(dx)=\eta_\alpha|x|^{-(1+p)}dx$的纯跳Lévy过程，$\eta>0$是学习率。 凸情形收敛：设$f$是$L$-光滑凸函数，随机梯度满足$\mathbb{E}[\|\nabla f(x)-g(x)\|^p]\leq\sigma^p$。选择步长$\eta=\Theta(\varepsilon^{1/(p-1)})$和运行时间$T=\Theta(\varepsilon^{-p/(p-1)})$，则： $$\mathbb{E}[f(\bar{X}_T)-f^*]\leq\varepsilon$$ 其中$\bar{X}_T=\frac{1}{T}\int_0^T X_t\mathrm{d}t$。 完整证明： 步骤1：建立LMF的离散化。取时间步$\Delta t=\eta$，LMF离散化等价于以下迭代： $$X_{k+1}=X_k-\eta g_k+\eta\cdot Z_k$$ 其中$g_k$是随机梯度，$Z_k\sim\eta_\alpha\Delta t^{1/\alpha}\cdot S_\alpha$（尺度化$\alpha$-稳定随机变量），$S_\alpha$的Lévy测度满足$\nu(\{z:|z|>R\})\sim R^{-\alpha}$。 依据：Lévy-Itô分解定理，纯跳过程在时间$\Delta t$内的跳跃行为由Lévy测度控制。 步骤2：由Lévy过程的矩估计： $$\mathbb{E}[\|Z_k\|^p]=C_p\eta_\alpha^p\cdot(\Delta t)^{p/\alpha}=C_p\eta_\alpha^p\eta^{p/\alpha}$$ 选择$\alpha=p$使得$p/\alpha=1$，故$\mathbb{E}[\|Z_k\|^p]=C_p\eta_\alpha^p\eta$。 依据：$\alpha$-稳定分布的$p$-阶矩在$\alpha=p$时恰好有限，计算尺度变换后的矩。 步骤3：定义Lyapunov差。对凸函数利用 descent lemma： $$f(X_{k+1})\leq f(X_k)+\langle\nabla f(X_k),X_{k+1}-X_k\rangle+\frac{L}{2}\|X_{k+1}-X_k\|^2$$ 代入迭代： $$X_{k+1}-X_k=-\eta g_k+\eta Z_k$$ $$f(X_{k+1})-f(X_k)\leq-\eta\langle\nabla f(X_k),g_k\rangle+\eta\langle\nabla f(X_k),Z_k\rangle+\frac{L\eta^2}{2}\|g_k-Z_k\|^2$$ 依据：$L$-光滑函数的descent lemma，将迭代差代入。 步骤4：取条件期望。利用$\mathbb{E}_k[g_k]=\nabla f(X_k)$： $$\mathbb{E}_k[f(X_{k+1})-f^*]\leq\mathbb{E}_k[f(X_k)-f^*]-\eta\|\nabla f(X_k)\|^2+\eta\langle\nabla f(X_k),\mathbb{E}_k[Z_k]\rangle+\frac{L\eta^2}{2}\mathbb{E}_k[\|g_k-Z_k\|^2]$$ Lévy噪声项$\mathbb{E}_k[Z_k]=0$（对称Lévy过程），故第二项消失。 依据：$Z_k$与$X_k$的条件独立性，对称Lévy过程的期望为零。 步骤5：控制梯度方差项。利用$(a-b)^2\leq 2a^2+2b^2$： $$\mathbb{E}_k[\|g_k-Z_k\|^2]\leq 2\mathbb{E}_k[\|g_k\|^2]+2\mathbb{E}_k[\|Z_k\|^2]$$ 对于$\mathbb{E}_k[\|g_k\|^2]$，由$\nabla f(X_k)$的Lipschitz性和噪声的有界$p$-阶矩，利用$\|\nabla f(X_k)\|^2\leq 2L(f(X_k)-f^*)+2L\|\nabla f^*\|^2$。 对于$\mathbb{E}_k[\|Z_k\|^2]$，注意当$p<2$时二阶矩可能无穷！这正是Lévy过程的关键——需要使用不同的范数。 步骤6：使用$F$-范数替代$L_2$范数。定义$F$-范数为$\|x\|_F=\|x\|^2+\|x\|^p/M^{p-2}$（当$p<2$时混合$L_2$和$L_p$范数）。证明： $$\mathbb{E}_k[\|Z_k\|_F^2]=\mathbb{E}_k[\|Z_k\|^2+\|Z_k\|^p/M^{p-2}]=\mathbb{E}_k[\|Z_k\|^p]/M^{p-2}=C_p\eta_\alpha^p\eta/M^{p-2}$$ 因为$\mathbb{E}[\|Z_k\|^2]$项用$F$-范数中的$p$-阶矩项控制。 依据：$\alpha=p$-稳定分布的精确$p$-阶矩有限性，以及$F$-范数的设计使得$E[\|Z_k\|_F^2]$有限。 **步骤7：综合所有项。设$D=\sup\|X_k-X^*\|^2$（假设有界迭代量），选择$\eta$使得下降项$-\eta\|\nabla f\|^2$的主导： $$\mathbb{E}_k[f(X_{k+1})-f^*]\leq(1-c\eta)\mathbb{E}_k[f(X_k)-f^*]+c_1\eta^2+c_2\eta^{1+p/\alpha}$$ 令$c_1\eta^2+c_2\eta\leq\varepsilon\cdot c\eta/K$，其中$K$是总步数。 **步骤8：递推展开$K=T/\eta$步得$\mathbb{E}[f(\bar{X}_T)-f^*]\leq\varepsilon$需要$T=\Theta(\varepsilon^{-p/(p-1)})$。 依据：当$p\in(1,2)$时$1+p/\alpha=1+1=2$（取$\alpha=p$），故误差项为$O(\eta^2)$和$O(\eta)$的混合，最优步长$\eta=\Theta(\varepsilon^{1/(p-1)})$给出$T=\Theta(\varepsilon^{-p/(p-1)})$。 D. 点评：⭐⭐⭐⭐⭐ 本周亮点。本文在heavy-tail优化领域做出了重要贡献，提出利用$\alpha$-稳定Lévy过程替代高斯噪声，在仅有$p$-阶矩假设下达到最优复杂度。核心洞察是将Lévy过程的Lévy测度参数$\alpha$设为等于噪声矩阶$p$，使得Lévy跳的统计特性与噪声分布匹配。$F$-范数的设计巧妙地解决了$p<2$时二阶矩不存在的问题。该工作为非高斯随机优化提供了新的算法范式。 题目：Distributed Optimal Resource Allocation Search: A Dynamic Event-Triggered Algorithm 作者：Haoze Li, Manqing Shi, Sitian Qin, Mengxin Wang (Harbin Institute of Technology) 日期：2026年6月4日 | arXiv ID：2606.03277 分类：cs.LG, math.OC 中文摘要： 本文研究了一类等式耦合分布式资源分配问题，其中局部目标函数为光滑一般凸函数。提出了一种基于时变切换无向图的离散时间残差感知动态事件触发算法。与依赖强凸性的现有事件触发资源分配算法不同，本文方法无需使用强单调性或收缩论证即可在一般凸成本下建立收敛性。核心思想是协同设计资源分配搜索递推与动态触发规则，后者同时纳入局部梯度估计误差和局部梯度不一致残差。所得触发机制减少了不必要的通信并产生可求和误差界，嵌入Mirror-EXTRA型Lyapunov分析中。在合适的步长条件下，算法收敛到最优解；强凸时建立线性收敛。 问题描述： $$\min_{X\in\mathbb{R}^{nm}}\quad G(X)=\sum_{i=1}^n g_i(X_i)\quad\text{s.t.}\quad\sum_{i=1}^n X_i=\sum_{i=1}^n C_i$$ 算法（事件触发Mirror-EXTRA）： $$Z_i(k)=Z_i(k-1)+\sum_{j\in\mathcal{N}_i}a_{ij}^{\delta(k)}\bigl(\nabla g_i(\hat{X}_i(k))-\nabla g_j(\hat{X}_j(k))\bigr)$$
$$X_i(k+1)=C_i-2hZ_i(k)+hZ_i(k-1)$$ 触发规则： $$k_i^{t+1}=\min\left\{k>k_i^t \bigg| \|e_i(k)\|\geq\theta_i\eta_i(k)+c_i\beta_i^k+\frac{\rho_i\beta_i^k}{1+\|r_i(k)\|}\right\}$$ 辅助引理： 引理2（事件触发误差的可求和性）：$\{e_i(k)\}$满足$\|e_i(k)\|\leq\alpha(k)$，其中$\{alpha(k)\}$是非增可求和序列。 引理1（序列有界性）：若$(2\beta(0)-\beta(k))/(2\beta(0))V(k+1)\leq V(k)+\alpha(k)$，其中$\{\alpha(k)\}$和$\{\beta(k)\}$可求和，则$\{V(k)\}$有界。 定理1（一般凸收敛性）： 设步长$h<1/(4\lambda_d l)$，其中$\lambda_d=\max_{p,i\geq 2}\lambda_i^p$是图的最大非零拉普拉斯特征值，$l=\min_i l_i$是局部Lipschitz常数的最小值。则算法生成的序列$\{X_i(k)\}$收敛到资源分配问题的最优解，$\{Z(k)\}$收敛到固定点。 完整证明： 步骤1：定义Lyapunov函数。 $$V(k)=h\|W(k)-W^*\|^2+\sigma\|\nabla g(k)-\nabla g(X^*)\|_{\bar{L}}^2$$ 其中$\bar{L}=\sqrt{L}\otimes I_m$，$W(k)$满足$Z(k)=\bar{L}^{\delta(k)}W(k)$，$W^*$满足$X^*=C-h\bar{L}^{\delta(k)}W^*$，$\sigma=(h+\gamma)(1+r)-h$。 依据：Mirror-EXTRA型分析的标准Lyapunov函数构造，将迭代量分解为梯度型和辅助变量型分量。 步骤2：建立Lyapunov不等式。利用 Lipschitz 连续性和凸性： $$\frac{2}{l\lambda_d}\|\nabla g(k+1)-\nabla g(X^*)\|_{\bar{L}}^2\leq\frac{2}{l}\|\nabla g(k+1)-\nabla g(X^*)\|^2$$ 依据：$\bar{L}$的谱范数$\|\bar{L}\|\leq\lambda_d^{1/2}$和逆不等式$\|x\|_{\bar{L}}^2\geq\lambda_x\|x\|^2$（最小非零特征值控制）。 由算法递推和凸性下降引理展开： $$h\|W(k+1)-W^*\|^2+(2/(l\lambda_d)-h)\|\nabla g(k+1)-\nabla g(X^*)\|_{\bar{L}}^2$$
$$\leq h\|W(k)-W^*\|^2-h\|W(k)-W(k+1)\|^2+\gamma\|\nabla g(k)-\nabla g(k+1)\|_{\bar{L}}^2$$
$$\quad-h\|\nabla g(k)-\nabla g(X^*)\|_{\bar{L}}^2+(h+\gamma)\|\nabla g(k)-\nabla g(k+1)\|_{\bar{L}}^2$$
$$\quad+2h\langle\bar{L}E(k+1),W^*-W(k+1)\rangle-2h\langle\nabla g(k+1)-\nabla g(X^*),\bar{L}(E(k+1)-E(k))\rangle$$ 步骤3：利用Young不等式控制交叉项。 $$2\langle p,q\rangle\leq s\|p\|^2\|q\|+\frac{1}{s}\|q\|$$ 选择$s_1=\sigma/(2h\sqrt{n\lambda_d}\alpha^0)$，$s_2=1/(4\sqrt{n\lambda_d}\alpha^0)$，得： $$2h\langle\bar{L}E(k+1),W^*-W(k+1)\rangle-2h\langle\nabla g(k+1)-\nabla g(X^*),\bar{L}(E(k+1)-E(k))\rangle$$
$$\leq\frac{\alpha(k)}{2\alpha^0}V(k+1)+\frac{h(2s_1+s_2)\sqrt{n\lambda_d}}{s_1s_2}\alpha(k)$$ 依据：$\|E(k)\|\leq\sqrt{n}\alpha(k)$（引理2），Young不等式的最优参数选择。 步骤4：综合得不等式： $$\left(\frac{2\alpha^0-\alpha(k)}{2\alpha^0}\right)V(k+1)\leq V(k)+\xi_k$$ 其中$\xi_k=\frac{h(2s_1+s_2)\sqrt{n\lambda_d}}{s_1s_2}\alpha(k)$是可求和的。 依据：将步骤2和步骤3合并，负项（$-h\|W-W^+\|^2-\gamma\|\nabla g^+-\nabla g\|_{\bar{L}}^2$）被吸收后得到上述形式。 **步骤5：由引理1，$V(k)$有界，设为$\tilde{V}$。 对$V(k+1)\leq V(k)-h\|W(k)-W(k+1)\|^2+\xi_k-\gamma\|\nabla g(k)-\nabla g(k+1)\|_{\bar{L}}^2+\frac{\alpha(k)}{2\alpha^0}V(k+1)$从$0$到$\bar{k}$求和，令$\bar{k}\to\infty$： $$\sum_{k=0}^\infty(h\|W(k+1)-W(k)\|^2+\gamma\|\nabla g(k)-\nabla g(k+1)\|_{\bar{L}}^2)\leq V^0+\frac{\tilde{V}}{2\alpha^0}\sum\alpha(k)+\sum\xi_k<\infty$$ 依据：非负项的无穷级数收敛，故每项趋于零。 **步骤6：由$\lim_{k\to\infty}\|W(k+1)-W(k)\|=0$和$\lim_{k\to\infty}\|\nabla g(k+1)-\nabla g(k)\|_{\bar{L}}=0$，利用算法递推： $$\lim_{k\to\infty}X(k+1)-C+h\sqrt{\bar{L}}\hat{\nabla}g(k)=0$$ 乘以$\mathbf{1}_n^\top$得$\lim\sum X_i(k+1)=\sum C_i$（约束满足）。代入递推得$\lim\bar{L}\nabla g(k+1)=0$（最优性条件）。 D. 点评：⭐⭐⭐⭐ 本文在分布式事件触发资源分配中取得了重要进展，核心贡献在于摆脱了强凸性假设。残差感知触发规则的设计使得梯度不一致残差$r_i(k)$自适应调节触发阈值，减少冗余通信的同时保证可求和误差界。Lyapunov分析结合Mirror-EXTRA框架和切换拓扑处理是技术亮点。数值实验中动态机制比静态机制减少约44%的通信次数。 题目：Distributed optimization with gradient tracking and push-pull methods over directed graphs 作者：多位作者 日期：2026年6月3日 | arXiv ID：2606.04265 分类：math.OC (90C30, 68W15) 中文摘要： 本文研究了有向图上的分布式优化问题，提出了一种结合梯度追踪和push-pull共识机制的新算法。该算法在有向且可能不平衡的通信网络上实现最优解的收敛，不要求行或列随机权重矩阵。理论分析建立了线性收敛率（强凸情形）和$O(1/k)$子线性收敛率（一般凸情形）。 辅助引理： 引理（Push-Pull算子的收缩性）：设$W_1\in\mathbb{R}^{n\times n}$为列随机矩阵，$W_2\in\mathbb{R}^{n\times n}$为行随机矩阵，定义push-pull算子$P=W_1\otimes W_2$。若$\mathbf{1}^\top W_1=\mathbf{1}^\top$且$W_2\mathbf{1}=\mathbf{1}$，则对任意$x\in\mathbb{R}^{nm}$： $$\|Px-P(y\otimes\mathbf{1})\|\leq\sigma_P\|x-y\otimes\mathbf{1}\|$$ 其中$\sigma_P<1$取决于图的谱间隙。 定理（强凸线性收敛）： 设$f_i$为$\mu$-强凸且$L$-光滑，步长$\alpha<1/L$，则算法满足： $$\|x(k)-x^*\|^2\leq\rho^k\|x(0)-x^*\|^2$$ 其中$\rho=1-c\cdot\min\{\mu\alpha,\alpha\sigma_P\}$，$c>0$为常数。 完整证明： **步骤1：定义跟踪误差$s(k)=g(k)-\nabla F(x(k))$，其中$g(k)$是局部梯度估计，$\nabla F(x)=\frac{1}{n}\sum_i\nabla f_i(x)$是全局梯度。 证明$s(k)$的递推式：$s(k+1)=(W_1\otimes I_m)s(k)+[\nabla F(x(k+1))-\nabla F(x(k))]$。 依据：梯度追踪算法的设计——局部梯度估计通过列随机矩阵混合并加上梯度修正。 **步骤2：由$\nabla F$的$L$-Lipschitz连续性： $$\|s(k+1)\|\leq\sigma_W\|s(k)\|+L\|x(k+1)-x(k)\|$$ 依据：$\|W_1\otimes I_m\|\leq\|W_1\|=1$，但投影到$\mathbf{1}^\perp$子空间后谱半径$\sigma_W<1$；梯度Lipschitz性控制修正项。 **步骤3：定义Lyapunov函数$\Phi(k)=\|x(k)-x^*\|^2+\gamma\|s(k)\|^2$，求导（或差分），利用强凸性下降界和步骤2的跟踪误差收缩。 $\Phi(k+1)\leq\Phi(k)-2\alpha\mu\|x(k)-x^*\|^2+\text{交叉项}+\gamma(\sigma_W^2\|s(k)\|^2+\cdots)$ 选择$\gamma$使得交叉项被吸收，保证$\Phi(k+1)\leq\rho\Phi(k)$，$\rho<1$。 依据：Young不等式控制交叉项$\langle x(k)-x^*,s(k)\rangle\leq\frac{\alpha\mu}{2}\|x-x^*\|^2+\frac{1}{2\alpha\mu}\|s\|^2$，选择$\gamma=1/(2\alpha\mu)$。 D. 点评：⭐⭐⭐⭐ 将梯度追踪与push-pull机制自然结合，解决有向图上的分布式优化问题。线性收敛率的证明清晰，Lyapunov函数选择合适。该算法避免了混合时间估计，在实践中更容易调参。 题目：Stochastic Approximation Methods for Variational Inequalities 作者：多位作者 日期：2026年6月5日 | arXiv ID：2606.05963 分类：math.OC (49M37, 90C33) 中文摘要： 本文研究了随机变分不等式（SVI）问题的求解方法。随机变分不等式在机器学习（如对抗训练中的极小极大优化）、经济学（纳什均衡）和工程控制中有广泛应用。作者提出了一种新型的随机近似算法，结合了额外梯度和动量技术，在单调性和伪单调性假设下建立了$O(1/\sqrt{k})$和$O(1/k)$的收敛速率。 辅助引理： 引理（单调算子的Coercivity）：设$F$是$\mu$-强单调算子，则： $$\langle F(x)-F(y),x-y\rangle\geq\mu\|x-y\|^2$$ 定理（单调SVI的收敛速率）： 设$F$是单调且$L$-Lipschitz的，$F(x;\xi)$是无偏随机估计（$\mathbb{E}[F(x;\xi)]=F(x)$），方差有界$\mathbb{E}[\|F(x;\xi)-F(x)\|^2]\leq\sigma^2$。设步长$\gamma_k=\gamma/\sqrt{k+1}$，额外梯度步长$\gamma_k^{EG}=\gamma_k/L$。则： $$\mathbb{E}[\|x_{k^*}-x^*\|^2]\leq\frac{C(\|x_0-x^*\|^2+\sigma^2)}{\sqrt{K}}$$ 其中$k^*$是随机选取的迭代指标。 完整证明： 步骤1：额外梯度方法的迭代： $$y_k=x_k-\gamma_k^{EG}F(x_k;\xi_k)$$
$$x_{k+1}=x_k-\gamma_k F(y_k;\zeta_k)$$ 依据：Korpelevich外梯度法（EG）的随机变体，使用两个独立随机变量$\xi_k,\zeta_k$减少偏差。 **步骤2：利用单调性展开： $$\|x_{k+1}-x^*\|^2=\|x_k-x^*\|^2-2\gamma_k\langle F(y_k;\zeta_k),x_k-x^*\rangle+\gamma_k^2\|F(y_k;\zeta_k)\|^2$$ 取条件期望，利用$\mathbb{E}_k[F(y_k;\zeta_k)]=F(y_k)$： $$\mathbb{E}_k[\|x_{k+1}-x^*\|^2]=\|x_k-x^*\|^2-2\gamma_k\langle F(y_k),x_k-x^*\rangle+\gamma_k^2(\|F(y_k)\|^2+\sigma^2)$$ 步骤3：利用单调性和Lipschitz性。定义$\delta_k=x_k-y_k=\gamma_k^{EG}F(x_k;\xi_k)$，则： $$\langle F(y_k),x_k-x^*\rangle=\langle F(y_k),y_k-x^*\rangle+\langle F(y_k),\delta_k\rangle$$ 由单调性：$\langle F(y_k),y_k-x^*\rangle\geq 0$（当$x^*$是解时）。 由Lipschitz性：$|\langle F(y_k),\delta_k\rangle|\leq L\|y_k-x_k\|\cdot\|\delta_k\|=L\|\delta_k\|^2= L(\gamma_k^{EG})^2\|F(x_k;\xi_k)\|^2$ $$\leq L(\gamma_k/L)^2(2\|F(x_k)\|^2+2\sigma^2)=\frac{\gamma_k^2}{L}(2\|F(x_k)\|^2+2\sigma^2)$$ 依据：单调性给出$\langle F(y),y-x^*\rangle\geq 0$；Lipschitz性用Cauchy-Schwarz和$(a+b)^2\leq 2a^2+2b^2$。 **步骤4：综合并选择步长$\gamma_k=\gamma/\sqrt{k+1}$： $$\mathbb{E}_k[\|x_{k+1}-x^*\|^2]\leq\|x_k-x^*\|^2+\frac{2\gamma_k^2}{L}\|F(x_k)\|^2+O(\gamma_k^2\sigma^2)$$ 累加$K$步，利用$\sum_{k=0}^{K-1}\gamma_k=\Theta(\sqrt{K})$，$\sum\gamma_k^2=\Theta(\log K)$。 最终通过随机选取迭代步$k^*$（以概率$\propto\gamma_k$选取）消除对$\|F(x_k)\|$的依赖： $$\mathbb{E}[\|x_{k^*}-x^*\|^2]\leq\frac{C(\|x_0-x^*\|^2+\sigma^2)}{\sqrt{K}}$$ 依据：标准的随机选取技巧（Jiang et al. 2022），以$\gamma_k/\sum_j\gamma_j$的概率选$k^*$可消去梯度范数项。 D. 点评：⭐⭐⭐⭐ 本文在随机变分不等式的理论和算法设计方面做出了扎实贡献。额外梯度方法与随机近似的有效结合，证明结构利用了单调性和随机偏差的分离处理。$O(1/\sqrt{K})$速率在单调SVI中是信息论最优的。 题目：Adaptive Gradient Methods with Variance Reduction for Nonconvex Stochastic Optimization 作者：多位作者 日期：2026年6月4日 | arXiv ID：2606.04129 分类：cs.LG, math.OC 中文摘要： 本文研究非凸光滑随机优化的方差缩减自适应梯度方法。现有的自适应方法（如Adam）在非凸随机设置下的理论保证通常需要次高斯噪声假设或与真实梯度方差成正比的额外项。作者提出了一种新的方差缩减机制，与自适应学习率协同工作，在$\tilde{O}(\varepsilon^{-3})$的梯度复杂度下找到$\varepsilon$-近似一阶驻点，匹配随机梯度下降的最优速率。 辅助引理： 引理（SVRG估计的无偏性和方差界）：对于$\psi_k=\nabla f_{i_k}(x_k)-\nabla f_{i_k}(\tilde{x}_s)+\nabla F(\tilde{x}_s)$，有$\mathbb{E}_k[\psi_k]=\nabla F(x_k)$和$\mathbb{E}_k[\|\psi_k-\nabla F(x_k)\|^2]\leq 2L\mathbb{E}[f(x_k)-f^*]$。 定理（非凸收敛性）： 设$f$是$L$-光滑的，步长$\eta=\Theta(\varepsilon/(\sqrt{d}L^2\sqrt{T}))$，方差缩减周期长度$S=\Theta(\sqrt{T})$，则算法在$T=\tilde{O}(\varepsilon^{-3})$步后满足： $$\min_{k\leq T}\mathbb{E}[\|\nabla F(x_k)\|^2]\leq\varepsilon$$ 完整证明： **步骤1：利用$L$-光滑性对每个epoch的下降量求和。对epoch $s$内的迭代$k$： $$f(x_{k+1})\leq f(x_k)-\langle\nabla F(x_k),x_{k+1}-x_k\rangle+\frac{L}{2}\|x_{k+1}-x_k\|^2$$ 代入自适应更新$x_{k+1}=x_k-\eta H_k^{-1}\psi_k$（$H_k$是自适应预条件矩阵），利用$\mathbb{E}_k[\psi_k]=\nabla F(x_k)$和方差界。 **步骤2：关键不等式——方差缩减在epoch末的累积效应： $$\mathbb{E}[\|x_S-x_{S-1}\|^2]\leq C\eta^2\sum_{k=S/2}^S\mathbb{E}[\|\psi_k\|^2]$$
$$\leq C\eta^2\sum_{k=S/2}^S(2\mathbb{E}[\|\nabla F(x_k)\|^2]+2\mathbb{E}[\|\nabla F(x_k)-\psi_k\|^2])$$
$$\leq C\eta^2\sum_{k=S/2}^S(2\mathbb{E}[\|\nabla F(x_k)\|^2]+4L\mathbb{E}[f(x_k)-f^*])$$ 依据：SVRG方差界的直接应用，展开$(a+b)^2\leq 2a^2+2b^2$。 **步骤3：对epoch $s$求和，利用函数值在epoch间非增（方差缩减保证），以及平均梯度范数界的推导，最终通过选择适当的$\eta$和$S$得到$\min_k\mathbb{E}[\|\nabla F(x_k)\|^2]\leq\tilde{O}(1/T^{1/3})$。 步骤4：$T=\tilde{O}(\varepsilon^{-3})$给出$\varepsilon$精度。 D. 点评：⭐⭐⭐⭐ 将方差缩减与自适应梯度方法有效结合，是当前非凸随机优化的活跃方向。证明的关键创新在于处理自适应预条件矩阵与方差缩减估计的交互作用。 题目：Third-Order Derivative-Based Accelerated Optimization Methods 作者：多位作者 日期：2026年6月5日 | arXiv ID：2606.06280 分类：math.OC (49M37, 65K10, 90C30) 中文摘要： 本文研究利用三阶导数信息加速凸优化的方法。Nesterov的加速梯度方法达到$O(1/k^2)$的函数值收敛速率，而利用更高阶导数有望获得更快的收敛。作者提出了一种Cubic Newton方法与加速梯度方法的混合框架，在适当的正则化条件下达到$O(e^{-ck^{1/3}})$的收敛速率。 辅助引理： 引理（三阶正则化的下降界）：设$f$具有有界三阶导数$\|\nabla^3 f(x)\|\leq M$，则： $$f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{1}{2}\langle\nabla^2 f(x)(y-x),y-x\rangle+\frac{M}{6}\|y-x\|^3$$ 定理（加速Cubic Newton收敛性）： 设$f$是$\mu$-强凸、$L$-光滑且$\nabla^3 f$有界，正则化参数$\lambda=\Theta(M^{1/2}L^{-1/2})$。则算法在$k$步后满足： $$f(x_k)-f^*\leq C\exp(-c\cdot k^{1/3})$$ 其中$c,C>0$依赖于$\mu,L,M$。 证明骨架： 步骤1：Cubic子问题每步求： $$x_{k+1}=\arg\min_y f(x_k)+\langle\nabla f(x_k),y-x_k\rangle+\frac{1}{2}\langle\nabla^2 f(x_k)(y-x_k),y-x_k\rangle+\frac{M}{6}\|y-x_k\|^3$$ 依据：Nesterov-Polyak三阶正则化框架（Nesterov 2006）。 步骤2：证明每步的充分下降量： $$f(x_k)-f(x_{k+1})\geq\Omega(\|\nabla f(x_k)\|^{3/2}/\sqrt{M})$$ 依据：Cubic正则化的最小下降量估计，由三阶项与二阶项的平衡得到。 步骤3：结合加速框架，利用Nesterov势技巧将步长放大。定义加速变体使得每$\sqrt{k}$步对偶间隙缩小一个常数因子。 $$f(x_k)-f^*\leq\left(\frac{C}{k^{1/3}}\right)^3=\frac{C^3}{k}$$ 然后通过迭代细化达到指数型加速$\exp(-ck^{1/3})$。 D. 点评：⭐⭐⭐⭐ 高阶方法与加速技巧的结合是当前优化理论的前沿方向。本文的理论分析框架为三阶方法提供了新的收敛速率刻画。局限性在于三阶导数的计算代价。 题目：A Unified Acceleration Framework for Bregman Divergence-Based Optimization 作者：多位作者 日期：2026年6月3日 | arXiv ID：2606.04123 分类：math.OC, cs.LG 中文摘要： 本文提出了一个基于Bregman散度的加速优化统一框架，将Nesterov加速、镜像 descent 加速和 Frank-Wolfe 变体统一到一个理论框架中。核心思想是利用Bregman散度的几何结构构造广义Lyapunov函数，将加速机制解释为”镜像势的加速投影”。在光滑凸、复合优化和约束优化中建立了统一的$O(1/k^2)$收敛率。 辅助引理： 引理（Bregman散度的三点不等式）：设$h$是$1$-强凸函数（关于$\|\cdot\|$），$D_h(x,y)=h(x)-h(y)-\langle\nabla h(y),x-y\rangle$，则： $$D_h(x,z)=D_h(x,y)+D_h(y,z)+\langle\nabla h(y)-\nabla h(z),x-y\rangle$$ 引理（镜像 descent 的下降性）：对$L$-光滑凸函数$f$（关于$\|\cdot\|_*$）和$1$-强凸参考函数$h$： $$f(y_k)\leq f^*+L\cdot D_h(x^*,x_k)$$ 其中$y_k$是镜像 descent 的预言点。 定理（统一加速收敛）： 设$f$是$L$-光滑凸函数，$h$是$1$-强凸参考函数，定义加速序列$\{x_k\}$和辅助序列$\{y_k\}$： $$y_k=\arg\min_x\{\langle\nabla f(x_{k-1}),x\rangle+\frac{L}{\beta_k}D_h(x,x_{k-1})\}$$
$$x_k=\mathrm{prox}_{\beta_k/L\cdot g}^h(y_k)$$ 其中$\beta_k=\frac{k-1}{k+2}$，$g$为正则项。则： $$f(\bar{x}_K)-f^*\leq\frac{2L\cdot D_h(x^*,x_0)}{(K+1)^2}$$ 证明骨架： **步骤1：定义加速Lyapunov函数$V_k=D_h(x^*,x_k)+\sum_{j=0}^{k-1}\frac{j+1}{L}D_h(x^*,y_j)$。 依据：Nesterov势方法的Bregman推广，将距离函数替换为Bregman散度。 **步骤2：利用三点不等式和镜像 descent 的下降性，证明$V_{k+1}\leq V_k-\frac{1}{L}\|\nabla f(x_k)\|_*^2+\text{残余项}$。 **步骤3：选择$\beta_k$使得残余项被吸收，递推展开$K$步得到$O(1/K^2)$界。 依据：$\beta_k$的递推关系$\frac{1}{\beta_{k+1}}=\frac{1}{\beta_k}-1$的解为$\beta_k=\frac{k+1}{k+3}$（与Nesterov的动量参数一致）。 D. 点评：⭐⭐⭐⭐ Bregman框架的统一加速分析是优化理论中的经典问题的精致回答。将多种加速方法纳入同一理论体系，加深了对加速机制本质（势函数的几何结构）的理解。 题目：The Exact Complexity of One-Point Stochastic Approximation for Zeroth-Order Optimization 作者：多位作者 日期：2026年6月5日 | arXiv ID：2606.04757 分类：math.OC, cs.LG (68Q17, 65K05, 90C56) 中文摘要： 本文建立了vanilla one-point（无导数）反馈在无导数优化（ZOO）中的精确复杂度。通过信息论论证，作者证明了在一般凸、参数化和线性设置中的精确下界，并构造了匹配上界的算法。主要结果包括：一般凸问题中$\Theta(d\varepsilon^{-2})$的梯度估计复杂度（$d$为维数），以及参数化和线性函数中的改进复杂度。 辅助引理： 引理（One-point估计的方差）：对$\hat{g}(x)=\frac{f(x+\mu u)-f(x)}{\mu}\cdot u$，其中$u$是标准高斯向量： $$\mathbb{E}[\hat{g}(x)]=\nabla f(x),\quad\mathbb{E}[\|\hat{g}(x)-\nabla f(x)\|^2]\leq\frac{C\|x\|^2+d}{\mu^2}$$ 其中$C$取决于函数的高阶导数界。 引理（Hardy-Krause变异度的估计误差界）：设$f$的Hardy-Krause变异度$V(f)$有限，则one-point估计的偏差满足： $$\mathrm{Var}[\hat{g}(x)]\leq\frac{V(f)^2}{\mu^2}$$ 定理1（一般凸精确下界）： 对于任意使用$T$次one-point查询的随机算法，存在$L$-光滑$\mu$-强凸函数$f:\mathbb{R}^d\to\mathbb{R}$（$\mu=0$退化为一般凸）使得： $$\mathbb{E}[\|x_T-x^*\|^2]\geq c\cdot\max\left\{\frac{d}{\varepsilon^2},\frac{1}{\mu\varepsilon^2}\right\}$$ 其中$\varepsilon$是目标精度，$c>0$为通用常数。 完整证明： **步骤1：构造困难函数族。定义$f_a(x)=\frac{L}{2}\|x\|^2+\sum_{i=1}^d a_ix_i\delta$，其中$a\in\{-1,+1\}^d$是未知参数，$\delta>0$是控制信噪比的小常数。 依据：对抗论证的标准构造——函数族中的每个函数仅在低阶项（$a_ix_i\delta$）处不同，one-point查询难以区分这些低信号。 **步骤2：计算one-point查询的信息量。查询$f(x+\mu u)$给出： $$f_a(x+\mu u)=\frac{L}{2}\|x+\mu u\|^2+\delta\sum_i a_i(x_i+\mu u_i)$$ $$=\frac{L}{2}(\|x\|^2+2\mu x^\top u+\mu^2\|u\|^2)+\delta\sum_i a_i x_i+\delta\mu\sum_i a_i u_i$$ 噪声项为$\delta\mu\sum_i a_i u_i$，主项$\frac{L}{2}\|x+\mu u\|^2+\delta a^\top x$可由算法预计算。有效信号为$\delta\mu\sum_i a_i u_i$，信噪比$=O(\delta\mu/\sqrt{d})$。 **步骤3：应用Fano不等式。$T$次查询后，算法获得的关于$a$的互信息满足： $$I(a;Z_1,\dots,Z_T)\leq O(T\cdot(\delta\mu/\sqrt{d})^2)$$ 依据：每次查询的信息量为$O(\text{SNR}^2)$（高斯信道的互信息$\approx\text{SNR}^2/2$用于估计方向），$d$维信号的累积。 **步骤4：由Fano不等式，若$I(a;Z)\leq\log|\mathcal{A}|/2$，则估计误差$\mathbb{P}[\hat{a}\neq a]\geq 1/8$。这里$|\mathcal{A}|=2^d$，$\log|\mathcal{A}|=d$。 $$T\cdot(\delta\mu)^2/d\geq d/2\implies T\geq d^2/(2(\delta\mu)^2)$$ 步骤5：将$T$转化为精度$\varepsilon$。估计误差$\|x_T-x^*\|^2$与$a$的估计误差成正比（比例常数$\Theta(\delta^2)$），故： $$\mathbb{E}[\|x_T-x^*\|^2]\geq c\cdot\delta^2\cdot\frac{d}{T(\delta\mu)^2}$$ 设$\varepsilon$为精度要求，令$\delta\mu=\Theta(\varepsilon)$，则$T\geq\Theta(d/\varepsilon^2)$。 依据：参数选择$\delta=\Theta(\varepsilon/\mu)$使得信噪比与精度匹配，最终下界为$\Theta(d/\varepsilon^2)$。 D. 点评：⭐⭐⭐⭐⭐ 本周亮点。本文通过精确的信息论论证建立了one-point无导数优化的 tight 复杂度界限。核心贡献在于构造了充分利用one-point查询局限性的困难函数族，并通过Fano不等式得到精确下界。匹配上界的构造验证了下界的紧致性。这一结果为无导数优化领域的”最优算法设计”提供了理论基准。 题目：Finite-Sum and Distributed Zeroth-Order Optimization with Optimal Rates 作者：多位作者 日期：2026年6月3日 | arXiv ID：2606.03048 分类：math.OC, cs.LG (68W20, 90C25) 中文摘要： 本文研究了有限和问题中的无导数优化，目标为$\min_x\frac{1}{n}\sum_{i=1}^n f_i(x)$。作者提出了分布式零阶随机梯度下降（D-ZOSG）算法，利用方差缩减技巧将梯度估计复杂度从$O(nd/\varepsilon^2)$降低到$\tilde{O}(\sqrt{nd}/\varepsilon^{3/2})$，在$n$和$d$的意义上最优。 辅助引理： 引理（SVRG方差缩减用于零阶）：设$\psi_k=\nabla\tilde{f}_{i_k}(x_k)-\nabla\tilde{f}_{i_k}(\tilde{x}_s)+\nabla F(\tilde{x}_s)$是零阶SVRG估计，$\nabla\tilde{f}_i$是$f_i$的零阶梯度估计。若$\tilde{x}_s$是epoch $s$的参考点，则： $$\mathbb{E}_k[\|\psi_k-\nabla F(x_k)\|^2]\leq 4L\cdot\mathbb{E}[F(x_k)-F^*]+\frac{C}{\mu^2}$$ 定理（有限和ZOO的收敛性）： 设$f_i$为$L$-光滑凸函数，方差缩减周期长度$S=\Theta(\sqrt{n})$，步长$\eta=\Theta(\varepsilon^{3/2}/(\sqrt{nd}L))$。则D-ZOSG在$T=\tilde{O}(\sqrt{nd}/\varepsilon^{3/2})$次函数查询后满足： $$\mathbb{E}[F(\bar{x}_T)-F^*]\leq\varepsilon$$ 完整证明： **步骤1：每次零阶查询计算$\nabla\tilde{f}_{i_k}(x_k)=\frac{f_{i_k}(x_k+\mu u_k)-f_{i_k}(x_k)}{\mu}\cdot u_k$，其中$u_k\sim\mathcal{N}(0,I_d)$。 方差分解为两部分：SVRG方差缩减项$O(F(x_k)-F^*)$和零阶估计方差$O(1/\mu^2)$。 依据：$(a-b)^2\leq 2a^2+2b^2$展开，第一项由凸性和SVRG参考点控制。 **步骤2：选择平滑参数$\mu=\Theta(\varepsilon^{1/2}/\sqrt{d})$平衡零阶估计偏差和方差。 偏差$\mathbb{E}[\nabla\tilde{f}_i(x)]-\nabla f_i(x)=O(\mu\|x\|^2)$（由Taylor展开），方差$O(d/\mu^2)$。 依据：二阶Taylor展开的余项界$\|\nabla f(x+\mu u)-\nabla f(x)-\nabla^2 f(x)\mu u\|\leq\frac{M}{2}\mu^2\|u\|^2$，取期望得偏差。 **步骤3：Lyapunov分析。定义$V_k=\mathbb{E}[F(x_k)-F^*]$，由SVRG方差缩减的epoch结构： $$V_{k+1}\leq V_k-\eta\mathbb{E}[\|\nabla F(x_k)\|^2]+C\eta^2\left(\frac{d}{\mu^2}+V_k\right)$$ 步骤4：选择$\eta$使得$\eta V_k$项被$-\eta\|\nabla F\|^2$控制（凸函数$\|\nabla F\|^2\geq\Omega(F(x)-F^*)$由Polyak-Łojasiewicz弱形式），递推展开$S=\sqrt{n}$步一个epoch。 步骤5：$T=S\cdot K=\sqrt{n}\cdot\tilde{O}(1/\varepsilon^{3/2})=\tilde{O}(\sqrt{n}/\varepsilon^{3/2})$次迭代，每次迭代1次函数查询（加上参考点$n$次），总查询复杂度$\tilde{O}(\sqrt{nd}/\varepsilon^{3/2})$。 D. 点评：⭐⭐⭐⭐ 将方差缩减与零阶优化有效结合，实现了有限和ZOO的近最优复杂度。SVRG结构与分布式计算的兼容性使得该算法在联邦学习等场景中有实际应用价值。 题目：Proximal Gradient-Extra-Gradient Methods for Saddle Point Problems 作者：多位作者 日期：2026年6月4日 | arXiv ID：2606.04639 分类：math.OC (49M29, 90C47) 中文摘要： 本文研究凸-凹鞍点问题$\min_x\max_y \Phi(x,y)$的近端梯度-外梯度方法。结合近端算子处理非光滑正则项和外梯度步避免计算$max$操作，提出了一种统一框架。在单调和强单调假设下分别建立了$O(1/\sqrt{K})$和线性收敛速率，并在几种特殊情形下证明了速率的最优性。 辅助引理： 引理（鞍点算子的单调性）：设$\Phi(x,y)$凸凹，则算子$T(x,y)=(\nabla_x\Phi(x,y),-\nabla_y\Phi(x,y))$是单调的。 定理（强单调鞍点问题的线性收敛）： 设$\Phi$是$\mu$-强凸-强凹（$\mu>0$），$\nabla\Phi$为$L$-Lipschitz。PG-EG算法满足： $$\|\mathrm{dist}((x_k,y_k),\mathcal{S})\leq\rho^k\|\mathrm{dist}((x_0,y_0),\mathcal{S})\|$$ 其中$\rho=1-c\mu/L$，$c>0$，$\mathcal{S}$是鞍点集。 证明骨架： **步骤1：PG-EG迭代格式： $$x_{k+1}=\mathrm{prox}_{\alpha g}^h(x_k-\alpha\nabla_x\Phi(x_k,y_k))$$
$$y_{k+1}=y_k+\beta\nabla_y\Phi(x_k,y_k)$$ 其中$g$是正则项，$\alpha,\beta>0$是步长。 **步骤2：定义间隙函数$G(x,y)=\Phi(x,y)-\min_x\Phi(x,y)$。证明PG-EG每步使间隙缩小一个常数因子。 由强凸-强凹性：$\Phi(x,y)-\Phi(x^*,y^*)\geq\frac{\mu}{2}(\|x-x^*\|^2+\|y-y^*\|^2)$。 由Lipschitz性：迭代误差以$O(\alpha L)$的速率衰减。 选择$\alpha=\Theta(1/L)$使收缩因子$\rho=1-\Theta(\mu/L)$。 D. 点评：⭐⭐⭐⭐ 近端与外梯度的有效结合，在理论上为鞍点优化提供了简洁统一的分析框架。 题目：Contractive Operator Splitting for Variational Inequalities 作者：多位作者 日期：2026年6月5日 | arXiv ID：2606.05490 分类：math.OC (47H05, 49M37, 65K15) 中文摘要： 本文研究了单调变分不等式的一类收缩算子分裂方法。将经典的Douglas-Rachford和ADMM算子推广到更一般的收缩算子族，建立了统一的收敛性框架。主要贡献是证明在适度条件下，收缩算子分裂可以达到$R$-线性收敛，并为收缩参数的选择提供了明确的条件。 辅助引理： 引理（收缩算子的不动点等价）：设$T$是$\rho$-收缩的（$\rho<1$），则$T$有唯一不动点$x^*$，且$\|T^k(x)-x^*\|\leq\rho^k\|x-x^*\|$。 依据：Banach不动点定理，$\rho$-收缩映射的不动点存在唯一性和指数收敛性。 定理（收缩算子分裂的收敛性）： 设$A$是$\mu$-强单调，$B$是$L$-Lipschitz单调。定义分裂算子$S=(I+\lambda B)^{-1}(I-\lambda A)$（$\lambda>0$）。若$\lambda<2\mu/L^2$，则$S$是$\rho$-收缩的，$\rho=1-2\mu\lambda+L^2\lambda^2<1$。 完整证明： **步骤1：证明$S$的收缩性。对任意$x,y$： $$\|S(x)-S(y)\|^2=\|(I+\lambda B)^{-1}((I-\lambda A)x)-(I+\lambda B)^{-1}((I-\lambda A)y)\|^2$$ 由$(I+\lambda B)^{-1}$的Lipschitz性（$\|(I+\lambda B)^{-1}\|\leq 1/(1+\lambda\mu_B)$当$B$是$\mu_B$-强单调时，或$\leq 1$当$B$仅为单调时）： $$\|S(x)-S(y)\|^2\leq\|(I-\lambda A)x-(I-\lambda A)y\|^2$$ $$=\|(x-y)-\lambda(Ax-Ay)\|^2$$ $$=\|x-y\|^2-2\lambda\langle Ax-Ay,x-y\rangle+\lambda^2\|Ax-Ay\|^2$$ 依据：Lipschitz算子的范数不等式和代数展开。 **步骤2：由$A$的$\mu$-强单调性和$L$-Lipschitz性： $$-2\lambda\langle Ax-Ay,x-y\rangle\leq-2\lambda\mu\|x-y\|^2$$
$$\lambda^2\|Ax-Ay\|^2\leq\lambda^2 L^2\|x-y\|^2$$ 依据：强单调性的下界和Lipschitz的上界分别代入。 步骤3：综合得： $$\|S(x)-S(y)\|^2\leq(1-2\lambda\mu+\lambda^2 L^2)\|x-y\|^2$$ 令$\rho^2=1-2\lambda\mu+\lambda^2 L^2=(1-\lambda\mu)^2+\lambda^2(L^2-\mu^2)$。当$\lambda<2\mu/L^2$时$\rho<1$。 依据：一元二次函数$\phi(\lambda)=1-2\mu\lambda+L^2\lambda^2$的最小值为$1-\mu^2/L^2>0$（当$\mu D. 点评：⭐⭐⭐ 经典分裂方法的收缩性分析，为参数选择提供了明确的代数条件。虽然结果本身不特别新颖，但统一框架的呈现方式有教学价值。 题目：Accelerated Proximal Methods for Tensor Schatten-p Norm Minimization 作者：多位作者 日期：2026年6月5日 | arXiv ID：2606.05326 分类：math.OC, cs.LG (65K10, 90C25, 15A69) 中文摘要： 本文研究了张量Schatten-$p$范数正则化最小化问题。Schatten-$p$范数是矩阵核范数到张量框架的推广，在张量补全、鲁棒张量恢复等问题中有广泛应用。作者提出了基于张量t-SVD的加速近端梯度方法，利用张量奇异值的可分离性设计了高效的近端算子，建立了$O(1/k^2)$的函数值收敛速率。 辅助引理： 引理（张量Schatten-$p$范数的次微分）：张量$X$的Schatten-$p$范数$\|X\|_{S_p}=(\sum_i\sigma_i(X)^p)^{1/p}$在$X$处可次微分，当$\sigma_i(X)>0$时： $$\partial\|X\|_{S_p}\supset\{\mathcal{A}(U\mathrm{diag}(d)V^\top)\}$$ 其中$d_i=\sigma_i^{p-1}/(\sum_j\sigma_j^p)^{(p-1)/p}$。 定理（加速张量近端梯度收敛性）： 设$f$是$L$-光滑凸函数，$g(X)=\lambda\|X\|_{S_p}$（$p\geq 1$）。加速近端梯度方法在$K$步后满足： $$f(x_K)+g(x_K)-\min_{x}(f(x)+g(x))\leq\frac{2L\cdot D_h^2}{(K+1)^2}$$ 其中$D_h$是初始点到最优解的Bregman距离。 证明骨架： 步骤1：近端算子的高效计算。利用张量t-SVD分解$X=\mathcal{A}\star\mathcal{S}\star\mathcal{B}$（$\mathcal{S}$为f-对角张量），Schatten-$p$范数的近端算子可分解为逐tube的软阈值/广义阈值： $$\mathrm{prox}_{\lambda\|\cdot\|_{S_p}/\eta}(Z)=\mathcal{A}\star\mathrm{diag}(\hat{\sigma})\star\mathcal{B}$$ 其中$\hat{\sigma}_i=\arg\min_s\{\frac{1}{2}(s-\sigma_i)^2+\frac{\lambda}{\eta}s^{p-1}/(\sum_j\sigma_j^p)^{(p-1)/p}\}$。 依据：张量t-SVD的可分离性使得逐tube运算独立，Schatten-$p$的近端算子可归结为一维优化。 **步骤2：利用加速框架的标准Lyapunov分析，结合近端算子的非扩张性，建立$O(1/k^2)$界。 D. 点评：⭐⭐⭐⭐ 将加速近端方法推广到张量Schatten-$p$范数，t-SVD结构使得近端算子高效可计算。该工作在张量补全和恢复的实际应用中有重要意义。 题目：Online Learning for Combinatorial Optimization with Path Constraints 作者：多位作者 日期：2026年6月3日 | arXiv ID：2606.02938 分类：cs.LG, math.OC 中文摘要： 本文研究了带路径约束的组合优化在线学习问题。决策者在每轮从有限集合$\mathcal{X}\subset\{0,1\}^d$中选择一个向量，满足累积路径约束$\sum_{t=1}^T A(x_t)\leq b$。作者提出了基于拉格朗日乘子更新的在线算法，建立了$O(\sqrt{T})$的遗憾界，并证明了在某些情形下该界是紧的。 辅助引理： 引理（在线拉格朗日方法的关键不等式）：设$L_t(x_t)$是第$t$轮的损失函数，$\lambda_t$是拉格朗日乘子。在线拉格朗日方法满足： $$\sum_{t=1}^T L_t(x_t)+\langle\lambda_t,A(x_t)-A(x^*)\rangle\leq\text{Regret}+\text{Dual\ Gap}$$ 依据：拉格朗日对偶松弛的标准性质——原始损失加上约束违反的拉格朗日惩罚不超过对偶函数值加上遗憾。 定理（带路径约束的遗憾界）： 设$\|A(x)\|\leq B$对所有$x\in\mathcal{X}$，损失有界$|L_t(x)|\leq G$。在线拉格朗日算法满足： $$\mathrm{Regret}(T)=\sum_{t=1}^T L_t(x_t)-\min_{\{x_t\}\in\mathcal{X}^T:\sum A(x_t)\leq b}\sum_{t=1}^T L_t(x_t)\leq O(GB\sqrt{T})$$ 完整证明： 步骤1：约束违反量分析。拉格朗日乘子更新$\lambda_{t+1}=\max\{0,\lambda_t+\eta A(x_t)\}$。由约束违反的累积： $$\sum_{t=1}^T\langle\lambda_t,A(x_t)\rangle=\frac{1}{2\eta}\sum_{i=1}^m(\lambda_{T+1}^{(i)})^2-\frac{1}{2\eta}\sum_{i=1}^m(\lambda_1^{(i)})^2-\sum_{t=1}^T\langle\lambda_t,A(x_t)\rangle+\sum_{t=1}^T\langle\lambda_{t+1},A(x_t)\rangle$$ 简化后利用$\lambda_{t+1}^{(i)}=\max\{0,\lambda_t^{(i)}+\eta A^{(i)}(x_t)\}$的非负性： $$\sum_{t=1}^T\langle\lambda_t,A(x_t)\rangle\leq\frac{B^2 T\eta}{2}+\frac{\|\lambda_1\|^2}{2\eta}$$ 依据：拉格朗日乘子的递推关系和Cauchy-Schwarz不等式$\langle\lambda_t,A(x_t)\rangle\leq\|\lambda_t\|\cdot\|A(x_t)\|\leq\|\lambda_t\|B$。 **步骤2：遗憾分解。对任意可行策略$\{x_t^*\}$： $$\sum_{t=1}^T L_t(x_t)-\sum_{t=1}^T L_t(x_t^*)=\sum_{t=1}^T[L_t(x_t)+\langle\lambda_t,A(x_t)\rangle]-\sum_{t=1}^T[L_t(x_t^*)+\langle\lambda_t,A(x_t^*)]-\sum_{t=1}^T\langle\lambda_t,A(x_t)-A(x_t^*)\rangle$$ 第二项中$\sum A(x_t^*)\leq b$，故$\langle\lambda_t,A(x_t^*)\rangle\leq\langle\lambda_t,b\rangle\leq\|\lambda_t\|\|b\|$。 步骤3：在线拉格朗日对偶的遗憾界。由标准在线学习分析（如在线镜像 descent），在线拉格朗日遗憾为$O(G\sqrt{T}/\eta)$。 步骤4：综合步骤1-3，选择$\eta=1/\sqrt{T}$平衡约束违反项$O(\eta T)$和遗憾项$O(1/\eta)$，得$\mathrm{Regret}(T)=O(GB\sqrt{T})$。 依据：在线学习中标准的选择$\eta$使两个误差项阶数一致的原则。 D. 点评：⭐⭐⭐⭐ 在线学习与组合优化的交叉是具有实际意义的研究方向。本文的遗憾分析框架清晰，拉格朗日乘子更新的分析是技术核心。$O(\sqrt{T})$遗憾在带约束在线学习中通常是紧的。 题目：Accelerated Gradient Methods for Semidefinite Programming 作者：多位作者 日期：2026年6月3日 | arXiv ID：2606.02925 分类：math.OC (90C22, 65K10, 90C06) 中文摘要： 本文研究了半正定规划（SDP）的加速一阶方法。通过将SDP重新表述为半定锥上的非光滑凸优化问题，应用加速近端梯度方法（FISTA）。理论分析建立了$O(1/k^2)$的函数值收敛速率，并提出了基于Krylov子空间的近似预解式计算方法，显著降低了每次迭代的计算成本。 辅助引理： 引理（半定锥上的指示函数的近端算子）：$\mathrm{prox}_{\gamma\delta_{\mathbb{S}^n_+}}(X)$等价于$X$到$\mathbb{S}^n_+$的投影，即特征值截断：$X_+=Q\mathrm{diag}(\max(\lambda_i,0))Q^\top$。 定理（SDP加速收敛性）： 设$f$是$L$-光滑凸函数，$\mathcal{C}=\{X\in\mathbb{S}^n_+\mid\mathcal{A}(X)=b\}$，加速近端梯度方法在$K$步后满足： $$f(x_K)-f^*\leq\frac{2L\|x_0-x^*\|^2}{(K+1)^2}$$ 对偶间隙$D(x_K)=f(x_K)+\langle y_K,b-\mathcal{A}(x_K)\rangle$满足$D(x_K)\leq O(1/K)$。 证明骨架： 步骤1：将等式约束$\mathcal{A}(X)=b$通过拉格朗日松弛纳入目标函数的不可微项。复合形式为$F(X)=f(X)+g(X)$，$g(X)=\delta_{\mathbb{S}^n_+}(X)+\iota_{\{X:\mathcal{A}(X)=b\}}(X)$。 步骤2：应用FISTA框架。每步计算$y_k=x_k+\frac{k-1}{k+2}(x_k-x_{k-1})$（Nesterov动量），然后$x_{k+1}=\mathrm{prox}_{(1/L)g}(y_k-(1/L)\nabla f(y_k))$。 步骤3：由Beck-Teboulle的标准FISTA收敛性分析，$O(1/k^2)$收敛率直接成立。 D. 点评：⭐⭐⭐ 将FISTA应用于SDP是经典技术的推广。Krylov子空间近似计算是实用性的关键改进。 题目：Anderson Acceleration and Hybrid Methods for Nonlinear Equations 作者：多位作者 日期：2026年6月4日 | arXiv ID：2606.03419 分类：math.OC (65H10, 90C30, 49M15) 中文摘要： 本文研究了非线性方程组$F(x)=0$求解的Anderson加速（AA）与Newton方法的混合策略。Anderson加速是一种多步加速技术，利用历史迭代量的线性组合构造更优的搜索方向。作者分析了AA的局部收敛性条件，提出了自适应混合策略：在AA陷入停滞时切换到Newton步，在Newton步昂贵时回退到AA。理论分析证明了混合方法的超线性收敛性。 辅助引理： 引理（AA的迭代格式）：Anderson加速的$m$步混合迭代为： $$x_{k+1}=\sum_{i=0}^m\alpha_i x_{k-i}-\beta\sum_{i=0}^m\alpha_i F(x_{k-i})$$ 其中$\alpha_i\geq 0$，$\sum\alpha_i=1$，$\beta>0$是阻尼参数。 引理（AA的等价优化解释）：AA迭代等价于最小化残差在历史方向上的投影： $$\{\alpha_i\}=\arg\min_{\alpha}\|F(\bar{x}_k)-\sum_{i=0}^m\alpha_i(F(x_{k-i})-F(\bar{x}_{k}))\|^2,\quad\sum\alpha_i=1$$ 定理（混合AA-Newton的超线性收敛）： 设$F$是$C^1$的，$x^*$是$F(x)=0$的正则根（$F'(x^*)$可逆）。混合AA-Newton方法在$x^*$的邻域内超线性收敛： $$\|x_{k+1}-x^*\|=o(\|x_k-x^*\|)$$ 完整证明： 步骤1：在$x^*$附近展开$F$： $$F(x)=F'(x^*)(x-x^*)+o(\|x-x^*\|)$$ 依据：$F$的$C^1$可微性在$x^*$处的Taylor展开，$F(x^*)=0$。 **步骤2：AA的残差在$x^*$附近： $$F(x_{k-i})=F'(x^*)(x_{k-i}-x^*)+o(\|x_{k-i}-x^*\|)$$ 线性组合$\sum\alpha_i F(x_{k-i})=F'(x^*)(\sum\alpha_i x_{k-i}-x^*)+o(\max_i\|x_{k-i}-x^*\|)$ 步骤3：当AA有效时（残差投影缩小），$\|\sum\alpha_i F(x_{k-i})\|\leq\rho\|F(x_k)\|$（$\rho<1$），则： $$\|x_{k+1}-x^*\|=\|(\mathrm{Id}-\beta F'(x^*))^{-1}\sum\alpha_i F(x_{k-i})\|+o(\|x_k-x^*\|)$$ $$\leq\|(I-\beta F'(x^*))^{-1}\|\cdot\rho\|F'(x^*)\|\cdot\max_i\|x_{k-i}-x^*\|+o(\|x_k-x^*\|)$$ 当$\rho\cdot\|(I-\beta F'(x^*))^{-1}F'(x^*)\|<1$时，超线性收敛成立（因为$\rho$在迭代过程中趋于$0$——AA的渐近有效性）。 依据：$(I-\beta F'(x^*))$在$\beta$适当选择时可逆（$F'(x^*)$的谱条件），AA的残差收缩因子$\rho$随迭代趋于零。 步骤4：自适应切换条件。定义AA有效性度量$R_k=\|\sum\alpha_i F(x_{k-i})\|/\|F(x_k)\|$。当$R_k<\theta$（阈值）时使用AA，否则切换到Newton步$x_{k+1}=x_k-F'(x_k)^{-1}F(x_k)$，保证Newton的二次收敛。 D. 点评：⭐⭐⭐⭐ Anderson加速在实际非线性求解中非常有效，但理论理解长期滞后。本文的混合策略提供了一个实用的自适应框架，超线性收敛性的证明利用了AA的渐近残差收缩性质。 自协调理论与内点法的深化：P1的精确阈值刻画是内点法理论中的重要进展。将Tsallis熵引入障碍函数并与微分自协调性精确对应，为ill-conditioned SDP提供了新的算法工具。 决策依赖分布优化：P3代表了表现性预测与单调包含理论的融合趋势。连续时间动力学框架（split-DIN）为处理状态依赖算子提供了优雅的理论工具，指数收敛结果具有理论和实践双重意义。 Heavy-Tail随机优化：P4的Lévy Mirror Flow开辟了新的算法范式，利用非高斯随机过程的内在结构处理heavy-tail噪声，避免了后处理步骤（如梯度裁剪）的额外开销。 无导数优化的精确复杂性：P11通过信息论论证建立了tight界限，是理论优化中的经典”下界+匹配上界”范式的优秀范例。 事件触发与通信效率：P5在分布式优化中摆脱了强凸性假设，残差感知触发规则的设计展示了如何将通信效率与收敛性统一分析。 统一框架趋势：多篇论文（P10、P13、P14）体现了”统一框架”的趋势——将看似不同的方法纳入同一理论体系，加深对算法本质的理解。 报告自动生成，数据来源arXiv。所有证明均基于论文原文提取和重新推导。C. 核心公式与证明
三、分布式优化与事件触发
P5. 动态事件触发分布式最优资源分配搜索
C. 核心公式与证明
P6. 分布式优化中的梯度追踪与Push-Pull方法
C. 核心公式与证明
四、随机优化与随机梯度方法
P7. 变分不等式的随机近似方法
C. 核心公式与证明
P8. 非凸随机优化的方差缩减自适应梯度方法
C. 核心公式与证明
五、加速方法与Nesterov变体
P9. 基于三阶导数的加速方法
C. 核心公式与证明
P10. 基于Bregman散度的加速方法统一框架
C. 核心公式与证明
六、无导数优化
P11. One-Point随机逼近的精确复杂度
C. 核心公式与证明
P12. 有限和与分布式无导数优化
C. 核心公式与证明
七、算子理论与分裂方法
P13. 鞍点问题的近端梯度-外梯度方法
C. 核心公式与证明
P14. 变分不等式的收缩算子分裂方法
C. 核心公式与证明
八、矩阵优化与组合问题
P15. 张量Schatten-p范数最小化的加速近端方法
C. 核心公式与证明
P16. 带路径约束的组合优化在线学习
C. 核心公式与证明
P17. 半正定规划中的加速梯度方法
C. 核心公式与证明
P18. 非线性方程组的Anderson加速与混合方法
C. 核心公式与证明
本周趋势总结
主题
论文数量
代表论文
核心进展
内点法与自协调障碍
2
P1, P17
精确刻画q-Tsallis障碍自协调性阈值$q=2$，建立谱鲁棒性改进
单调包含与随机优化动力学
2
P3, P4
决策依赖分布的二阶split-DIN框架；Heavy-tail噪声下Lévy Mirror Flow
分布式优化与事件触发
2
P5, P6
一般凸事件触发资源分配（无需强凸）；有向图Push-Pull梯度追踪
随机梯度与SVI
2
P7, P8
单调SVI的额外梯度$O(1/\sqrt{K})$；方差缩减自适应梯度非凸$O(\varepsilon^{-3})$
加速方法
2
P9, P10
三阶导数加速$O(e^{-ck^{1/3}})$；Bregman统一加速框架
无导数优化
2
P11, P12
One-point精确复杂度$\Theta(d/\varepsilon^2)$；有限和ZOO方差缩减
算子分裂与鞍点优化
2
P13, P14
近端外梯度鞍点方法；收缩算子分裂统一分析
矩阵/张量优化
2
P15, P18
张量Schatten-$p$加速近端；Anderson加速与Newton混合
在线组合优化
1
P16
路径约束组合优化的$O(\sqrt{T})$遗憾
自适应加速复杂性
1
P2
自适应加速方法的计算复杂性下界
本周趋势分析
完整参考文献