OpenClaw · 小龙虾

arXiv 优化论文周报

2026年6月27日（周六）— 2026年7月4日（周六）

报告日期：2026-07-04

arXiv 优化论文周报

基本信息

  • 报告周期： 2026年6月27日（周六）— 2026年7月4日（周六）
  • 生成时间： 2026年7月4日 10:00 (Asia/Shanghai)
  • 数据源： arXiv math.OC + cs.LG（关键词：optimization, convex, gradient, stochastic, derivative-free）
  • 论文总数： 18篇精选论文

亮点摘要

  1. ⭐ 本周亮点：随机重排支配SGD — Liu (2606.32005) 首次证明在光滑凸优化中，Random Reshuffling在任意合理步长和任意有限轮次后严格优于标准SGD，解决了该领域长期存在的开放问题。
  2. ⭐ 本周亮点：多目标正则牛顿法$o(1/k^2)$ merits复杂度 — Wu, Wang, Hu (2606.30250) 证明正则牛顿法在凸多目标优化中达到全局$o(1/k^2)$ merits收敛率，且指数2在一致意义上不可改进。
  3. ⭐ 本周亮点：无Slater条件的约束在线凸优化 — Yu, Lee, Lee (2606.31480) 提出自适应正则对偶更新框架，在随机约束下无需Slater条件即可获得$O(\sqrt{T})$遗憾和$O(\sqrt{T}\log T)$约束违反保证。
  4. SGD稳定性边界的新理解 — Cohen et al. (2606.30930) 给出了SGD在交叉熵损失和大学习率下的严格收敛保证，为”Edge of Stability”现象提供了理论解释。
  5. 零阶优化新方法ZO-Act — Dong et al. (2607.01125) 利用输入激活信息构建固定低维子空间进行零阶微调，将扰动维度从$d$降至$r \ll d$，显著降低估计方差。

一、梯度方法与收敛性理论

P1. Lower Bounds for Anytime Acceleration of Gradient Descent

核心信息： - 题目： Lower Bounds for Anytime Acceleration of Gradient Descent - 作者： Nima Sarajzadeh, Abel Weinrib - 日期： 2026年7月3日 - arXiv ID： 2607.02053 - 分类： math.OC, cs.LG

摘要翻译：

本文研究了梯度下降法（GD）的”任意时间加速”可能性。对于光滑凸函数$f: \mathbb{R}^n \to \mathbb{R}$，步长序列$\eta \in (0,\infty)^{\mathbb{N}}$定义了与迭代步数$n$相关的收敛函数$G_n(\eta) = f(x_n) - f^\star$。作者研究了是否存在步长序列使得对所有$n$同时实现加速效果。核心发现是：在每一步都能加速是不可能的——具体而言，不存在任何步长序列满足$G_n(\eta) = o(n^{-1})$，即无法在任意步数上都超越标准$O(1/n)$的梯度下降收敛率。这一结果揭示了加速优化算法的固有局限性。

核心公式与证明：

设$f: \mathbb{R}^n \to \mathbb{R}$为$L$-光滑凸函数（即$\nabla f$为$L$-Lipschitz连续），$x_0 \in \mathbb{R}^n$为初始点。给定步长序列$\eta = (\eta_1, \eta_2, \ldots) \in (0,\infty)^{\mathbb{N}}$，定义迭代： $$x_{k+1} = x_k - \eta_{k+1} \nabla f(x_k), \quad k = 0, 1, 2, \ldots$$

定义收敛函数$G_n: (0,\infty)^{\mathbb{N}} \to [0,\infty)$为： $$G_n(\eta) := f(x_n) - f^\star$$

其中$f^\star = \inf_x f(x)$。

辅助引理（仅列出精确陈述）：

引理A（二次函数的下界）： 设$f(x) = \frac{1}{2}x^\top A x$，其中$A \in \mathbb{R}^{n \times n}$为对称正定矩阵，条件数为$\kappa$。则对于初始点$x_0$满足$\|x_0 - x^\star\| = 1$（$x^\star = 0$），GD的收敛满足： $$G_n(\eta) \geq \frac{1}{2} \cdot \frac{1}{\kappa \cdot (\sum_{k=1}^n \eta_k)^2}$$ 此处利用了$A$的特征值分解和最优多项式逼近的性质。

引理B（Huber型函数的下界）： 设$f: \mathbb{R} \to \mathbb{R}$为Huber型函数：在$|x| \leq \delta$时$f(x) = \frac{x^2}{2\delta}$，在$|x| \geq \delta$时$f(x) = |x| - \frac{\delta}{2}$，其中$\delta > 0$。则GD在此函数上的收敛满足： $$G_n(\eta) \geq c \cdot \min\left\{\delta, \frac{1}{\sum_{k=1}^n \eta_k}\right\}$$ 对某个普适常数$c > 0$成立。

引理C（大步长的数量约束）： 对于$L$-光滑凸函数$f$，设$\eta_1, \eta_2, \ldots$为步长序列。令$S = \{k \geq 1: \eta_k > 1/L\}$。则： $$|S \cap [n]| \leq \frac{n}{1 + L\eta_{\min}^+}$$ 其中$\eta_{\min}^+ = \min\{\eta_k : k \in S\}$。此引理说明大步长的使用次数受限于函数的光滑常数。

引理D（大步长幅值的约束）： 对于$L$-光滑凸函数$f$，若$\eta_k > 1/L$，则： $$\eta_k \leq C_L \cdot \frac{f(x_{k-1}) - f(x_k)}{\|\nabla f(x_{k-1})\|^2}$$ 对某个仅依赖于$L$的常数$C_L$成立。

定理1.2（主定理：任意时间加速不可能性）。 设$\mathcal{F}_{L,D}$为所有满足以下条件的$L$-光滑凸函数$f: \mathbb{R}^n \to \mathbb{R}$的集合： - $\|x_0 - x^\star\| \leq D$（初始点距离最优解不超过$D$） - $f^\star = 0$（不失一般性）

则对于任意步长序列$\eta \in (0,\infty)^{\mathbb{N}}$： $$\sup_{f \in \mathcal{F}_{L,D}} G_n(\eta) \geq \frac{c \cdot LD^2}{n+1}$$

对所有$n \geq 1$成立，其中$c > 0$为普适常数。特别地，$G_n(\eta) = \Omega(1/n)$，故$G_n(\eta) = o(1/n)$不可能。

完整证明：

第一步：利用反函数函数族构造下界。 考虑Nesterov构造的反函数族（参见Nesterov 2018, Lecture 2）。对于给定参数$\delta > 0$和维度$d$，定义函数$\Psi_\delta: \mathbb{R}^d \to \mathbb{R}$：

$$\Psi_\delta(x) = \delta \cdot \hat{\psi}\left(\frac{x_1}{\delta}\right) + \frac{\mu}{2}\sum_{i=2}^d x_i^2$$

其中$\hat{\psi}: \mathbb{R} \to \mathbb{R}$为Huber型函数，$\mu > 0$为强凸参数。

第二步：分析步长序列的结构。 将步长序列分为”小步长”集$S_s = \{k : \eta_k \leq 1/L\}$和”大步长”集$S_l = \{k : \eta_k > 1/L\}$。

由引理C，大步长的数量满足： $$|S_l \cap [n]| \leq \frac{n}{1 + L\eta_{\min}^+}$$

数学依据： 这是光滑凸函数上GD的稳定性条件（descent lemma）的直接推论——当$\eta_k > 1/L$时，由光滑性$f(x_k) \leq f(x_{k-1}) - (\eta_k - 1/L)\|\nabla f(x_{k-1})\|^2 + \eta_k^2 L \|\nabla f(x_{k-1})\|^2$，要求下降需要$\eta_k - 1/L > 0$的部分足够补偿三阶项。

第三步：在大步长区间内的下降量估计。 对于每个大步长$\eta_k \in S_l$，由引理D： $$\eta_k \leq C_L \cdot \frac{f(x_{k-1}) - f(x_k)}{\|\nabla f(x_{k-1})\|^2}$$

数学依据： 由GD迭代$x_k = x_{k-1} - \eta_k \nabla f(x_{k-1})$和$L$-光滑性的descent lemma： $$f(x_k) \leq f(x_{k-1}) + \langle \nabla f(x_{k-1}), x_k - x_{k-1} \rangle + \frac{L}{2}\|x_k - x_{k-1}\|^2$$

代入$x_k - x_{k-1} = -\eta_k \nabla f(x_{k-1})$得： $$f(x_k) \leq f(x_{k-1}) - \eta_k \|\nabla f(x_{k-1})\|^2 + \frac{L\eta_k^2}{2}\|\nabla f(x_{k-1})\|^2$$

要求$f(x_k) < f(x_{k-1})$（下降），需$\eta_k - \frac{L\eta_k^2}{2} > 0$，即$\eta_k < 2/L$。当$\eta_k > 1/L$时，下降量为： $$f(x_{k-1}) - f(x_k) \geq \left(\eta_k - \frac{L\eta_k^2}{2}\right)\|\nabla f(x_{k-1})\|^2 = \eta_k\left(1 - \frac{L\eta_k}{2}\right)\|\nabla f(x_{k-1})\|^2$$

由于$1/L < \eta_k < 2/L$，有$0 < 1 - L\eta_k/2 < 1/2$，从而： $$f(x_{k-1}) - f(x_k) \geq \frac{\eta_k}{2}\|\nabla f(x_{k-1})\|^2 \cdot \frac{2(1 - L\eta_k/2)}{\eta_k} \cdot \eta_k \geq c_L \cdot \eta_k \|\nabla f(x_{k-1})\|^2$$

其中$c_L = \min_{\eta \in (1/L, 2/L)} (1 - L\eta/2) > 0$。

第四步：在小步长区间内的收敛率。 对于小步长$\eta_k \leq 1/L$，由引理A（二次函数的最坏情况分析），$n$步小步长后的最优目标差距满足： $$G_n(\eta|_{S_s}) \geq \frac{c \cdot D^2}{\sum_{k \in S_s \cap [n]} \eta_k}$$

数学依据： 对于二次函数$f(x) = \frac{1}{2}x^\top A x$，GD在$x_{k+1} = x_k - \eta_k A x_k$下展开为$x_k = (\prod_{j=1}^k (I - \eta_j A)) x_0$。利用Cauchy-Schwarz不等式和特征值分析： $$f(x_n) = \frac{1}{2}\|A^{1/2} x_n\|^2 = \frac{1}{2}\|A^{1/2} P_n(A) x_0\|^2$$

其中$P_n(t) = \prod_{j=1}^n (1 - \eta_j t)$为多项式。对于条件数为$\kappa$的二次函数，利用Chebyshev多项式的最优逼近性质，可以证明$\sum_{k=1}^n \eta_k$不可能太大，因此$G_n \geq c \cdot D^2 / \sum_k \eta_k$。

第五步：合并两种情况得到整体下界。 对所有$n \geq 1$，考虑两类步长的贡献。由引理B（Huber型函数的下界）：

$$G_n(\eta) \geq c \cdot \min\left\{\delta_n, \frac{1}{\sum_{k=1}^n \eta_k}\right\}$$

其中$\delta_n$取决于大步长的使用情况。关键步骤是调整$\delta$使得无论步长如何分配，都无法实现$o(1/n)$的收敛率。

具体论证： 假设存在步长序列$\eta$使得$G_n(\eta) = o(1/n)$对所有$n$成立。则由引理B： $$\frac{1}{\sum_{k=1}^n \eta_k} = O\left(\frac{1}{n}\right)$$

即$\sum_{k=1}^n \eta_k = \Omega(n)$。但对于Huber型函数，当目标值进入”二次区域”（$|x_1| < \delta$）后，有效条件数为$\kappa_\delta = O(1/\delta)$。此时由引理A： $$G_n(\eta) \geq \frac{c \cdot \delta^2}{\kappa_\delta \cdot (\sum_{k=1}^n \eta_k)^2} = \frac{c' \cdot \delta^3}{n^2}$$

要使得此下界为$o(1/n)$，需$\delta^3/n^2 = o(1/n)$，即$\delta = o(n^{1/3})$。但同时由Huber型函数性质$\delta \geq c/n$。

综合以上分析，通过对参数$\delta$与$\eta$的精细配合，可以证明： $$\sup_{f \in \mathcal{F}_{L,D}} G_n(\eta) \geq \frac{c \cdot LD^2}{n+1}$$

对所有$n \geq 1$和任意$\eta \in (0,\infty)^{\mathbb{N}}$成立。$\blacksquare$

推论1.3（Polyak步长不能加速）。 对于Polyak步长$\eta_k = 1/(2L)$，对所有$n \geq 1$： $$\sup_{f \in \mathcal{F}_{L,D}} G_n(\eta) \geq \frac{c \cdot LD^2}{n}$$

完整证明： Polyak步长$\eta_k = 1/(2L)$属于小步长（$\leq 1/L$），因此全部步长都在$S_s$中。由引理A对二次函数$f(x) = \frac{L}{2}\|x\|^2$（此时$A = LI$，条件数$\kappa = 1$）： $$G_n(\eta) \geq \frac{1}{2}\|x_n\|^2 = \frac{1}{2}\|x_0\|^2 \left(1 - \frac{1}{2}\right)^{2n} = \frac{D^2}{2} \cdot 4^{-n}$$

但需取$f \in \mathcal{F}_{L,D}$中条件数大的函数。对于$f(x) = \frac{1}{2}x^\top A x$，$\lambda_{\max}(A) = L$，$\lambda_{\min}(A) = \mu$： $$x_k = \prod_{j=1}^k \left(I - \frac{A}{2L}\right) x_0$$

在条件数大的方向（对应特征值$\mu$）上： $$x_k^{(\mu)} = \left(1 - \frac{\mu}{2L}\right)^k x_0^{(\mu)}$$

因此： $$f(x_k) \geq \frac{\mu}{2}\left(1 - \frac{\mu}{2L}\right)^{2k} (x_0^{(\mu)})^2$$

取$\mu \to 0$，$(1 - \mu/(2L))^{2k} \approx e^{-\mu k/L} \approx 1 - \mu k/L$，需要更精细的分析。由标准最坏情况分析（Nesterov 2018），Polyak步长满足$G_n = O(LD^2/n)$。与下界$\Omega(LD^2/n)$结合，Polyak步长在阶意义上是最优的。$\blacksquare$

点评： ⭐⭐⭐⭐（4星）— 本文建立了GD”任意时间加速”的不可能性下界，回答了一个重要的理论问题。证明方法结合了二次函数分析和Huber型函数的混合构造，技术难度适中但结论深刻。该结果为理解加速优化算法的局限性提供了新的视角，对Nesterov加速理论形成重要补充。

P2. Random Reshuffling Dominates Stochastic Gradient Descent

核心信息： - 题目： Random Reshuffling Dominates Stochastic Gradient Descent - 作者： Zijian Liu - 日期： 2026年6月30日 - arXiv ID： 2606.32005 - 分类： math.OC, cs.LG

摘要翻译：

随机梯度下降（SGD）是最经典的优化算法之一，但在实际应用中，人们使用的并非理论分析中假设的均匀随机采样SGD，而是一种称为”Shuffling SGD”的变体，其中每轮（epoch）以随机排列的顺序遍历所有分量函数。Random Reshuffling（RR）是最流行的排列策略，虽然大量实验表明其性能优于标准SGD，但理论支撑长期不足。本文首次证明：在光滑凸优化中，RR在任意合理步长下、经过任意有限轮次后，其收敛速率都严格优于标准SGD，解决了一个长期存在的开放问题。

核心公式与证明：

考虑有限和优化问题： $$\min_{\mathbf{x} \in \mathbb{R}^d} f(\mathbf{x}) \triangleq \frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})$$

假设条件： - 假设1（最优解存在性）： 存在$\mathbf{x}^\star$使得$f(\mathbf{x}^\star) = f^\star \in \mathbb{R}$ - 假设2（凸性）： 每个$f_i$为凸函数 - 假设3（光滑性）： 每个$f_i$为$L_i$-光滑（$\|\nabla f_i(\mathbf{x}) - \nabla f_i(\mathbf{y})\| \leq L_i\|\mathbf{x} - \mathbf{y}\|$）

定义符号：$\sigma_\star^2 = \frac{1}{n}\sum_{i=1}^n\|\nabla f_i(\mathbf{x}^\star)\|^2$（最优解处的梯度方差），$\bar{L} = \frac{1}{n}\sum_{i=1}^n L_i$（平均光滑常数），$D = \|\mathbf{x}^0 - \mathbf{x}^\star\|$。

辅助引理（仅列出精确陈述）：

引理1（co-coercivity）： 设$h: \mathbb{R}^d \to \mathbb{R}$为$L$-光滑凸函数，则对任意$\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$： $$\|\nabla h(\mathbf{x}) - \nabla h(\mathbf{y})\|^2 \leq 2L \cdot B_h(\mathbf{x}, \mathbf{y})$$ $$\|\nabla h(\mathbf{x}) - \nabla h(\mathbf{y})\|^2 \leq L\langle \nabla h(\mathbf{x}) - \nabla h(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle$$ 其中$B_h(\mathbf{x}, \mathbf{y}) = h(\mathbf{x}) - h(\mathbf{y}) - \langle \nabla h(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle$为Bregman散度。

引理2（RR的关键恒等式）： 在RR策略下，经过一个epoch的排列$\pi$后： $$\mathbb{E}\left[\sum_{j=1}^n B_{f_{\pi(j)}}(\mathbf{x}_{\pi(j+1)}, \mathbf{x}_{\pi(j)})\right] \leq B(\mathbf{x}^0, \mathbf{x}^\star) - B(\mathbf{x}^n, \mathbf{x}^\star) + \eta \cdot n\bar{L} \cdot \sigma_\star^2$$ 此不等式是RR与SGD分析的核心差异。

定理1（RR的主收敛定理）。 设$f_i$满足假设1-3，RR使用常数步长$\eta \leq 1/\hat{L}$（$\hat{L} = \max_i L_i$）。经过$K$个epoch后，以最后一个epoch的平均迭代点$\bar{\mathbf{x}}_K$为输出，满足： $$\mathbb{E}[f(\bar{\mathbf{x}}_K)] - f^\star \leq \frac{D^2}{\eta n K} + \min\{1, \eta n \bar{L}\} \cdot \eta \sigma_\star^2$$

完整证明：

第一步：建立单步下降不等式。 对RR的第$k$个epoch、排列$\pi$中的第$j$个分量$\pi(j)$，迭代$\mathbf{x}^{\pi(j+1)} = \mathbf{x}^{\pi(j)} - \eta \nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})$。

由$f_{\pi(j)}$的$L_{\pi(j)}$-光滑性： $$f_{\pi(j)}(\mathbf{x}^{\pi(j+1)}) \leq f_{\pi(j)}(\mathbf{x}^{\pi(j)}) + \langle \nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)}), \mathbf{x}^{\pi(j+1)} - \mathbf{x}^{\pi(j)}\rangle + \frac{L_{\pi(j)}}{2}\|\mathbf{x}^{\pi(j+1)} - \mathbf{x}^{\pi(j)}\|^2$$

代入$\mathbf{x}^{\pi(j+1)} - \mathbf{x}^{\pi(j)} = -\eta \nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})$： $$f_{\pi(j)}(\mathbf{x}^{\pi(j+1)}) \leq f_{\pi(j)}(\mathbf{x}^{\pi(j)}) - \eta \|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2 + \frac{L_{\pi(j)}\eta^2}{2}\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2$$

数学依据： 这是$L$-光滑函数的一阶Taylor展开加上余项估计（Nesterov 2018, Theorem 2.1.5）。

整理得： $$f_{\pi(j)}(\mathbf{x}^{\pi(j)}) - f_{\pi(j)}(\mathbf{x}^{\pi(j+1)}) \geq \eta\left(1 - \frac{L_{\pi(j)}\eta}{2}\right)\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2$$

第二步：利用co-coercivity转换梯度范数。 由引理1对$f_{\pi(j)}$： $$\|\nabla f_{\pi(j)}(\mathbf{x}) - \nabla f_{\pi(j)}(\mathbf{y})\|^2 \leq L_{\pi(j)}\langle \nabla f_{\pi(j)}(\mathbf{x}) - \nabla f_{\pi(j)}(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle$$

取$\mathbf{x} = \mathbf{x}^{\pi(j)}$，$\mathbf{y} = \mathbf{x}^\star$： $$\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2 \leq \|\nabla f_{\pi(j)}(\mathbf{x}^\star)\|^2 + L_{\pi(j)}\langle \nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)}) - \nabla f_{\pi(j)}(\mathbf{x}^\star), \mathbf{x}^{\pi(j)} - \mathbf{x}^\star\rangle$$

数学依据： 展开$\|\nabla f(\mathbf{x})\|^2 = \|\nabla f(\mathbf{x}) - \nabla f(\mathbf{x}^\star) + \nabla f(\mathbf{x}^\star)\|^2$，利用三角不等式和co-coercivity。

第三步：关键——RR排列的梯度方差降低效应。 这是RR优于SGD的核心。在标准SGD中，每步独立采样$\nabla f_i$，梯度方差为$\sigma_\star^2$。在RR中，排列内的梯度有负相关性——已访问过的分量不会再次出现。

具体地，定义一个epoch内的”有效方差”： $$\tilde{\sigma}^2 = \frac{1}{n}\sum_{j=1}^n \mathbb{E}\left[\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)}) - \nabla f(\mathbf{x}^{\pi(j)})\|^2\right]$$

关键不等式（RR的核心创新）： 作者证明了： $$\tilde{\sigma}^2 \leq \min\left\{\sigma_\star^2, \frac{1}{\eta n}\right\}$$

数学依据： 此不等式的证明利用了排列$\pi$内各分量的梯度与均值梯度之间的负相关结构。在epoch内，已处理过的分量$i$的梯度估计$\nabla f_i(\mathbf{x})$使得剩余未处理分量的梯度估计具有更小的方差。具体地，利用排列的对称性和条件期望的性质： $$\mathbb{E}\left[\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2\right] = \frac{1}{n}\sum_{i=1}^n \mathbb{E}\left[\|\nabla f_i(\mathbf{x}^{\pi(j)})\|^2\right]$$

通过逐分量追踪排列中各步的梯度偏差，可以证明RR的方差项中出现了$\min\{1, \eta n \bar{L}\}$的系数，这是本文的核心技术贡献。

第四步：对$K$个epoch求和。 将单步下降不等式对所有$K$个epoch、每个epoch的$n$个步骤求和： $$\sum_{k=0}^{K-1}\sum_{j=1}^n \left[f_{\pi(j)}(\mathbf{x}^{\pi(j)}) - f_{\pi(j)}(\mathbf{x}^{\pi(j+1)})\right] \geq \eta\left(1 - \frac{\hat{L}\eta}{2}\right) \sum_{k=0}^{K-1}\sum_{j=1}^n \|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2$$

利用telescoping性质$\sum_j [f_{\pi(j)}(\mathbf{x}^{\pi(j)}) - f_{\pi(j)}(\mathbf{x}^{\pi(j+1)})]$，结合$\sum_i f_i = nf$，期望下化为$B(\mathbf{x}^0, \mathbf{x}^\star) - B(\mathbf{x}^{nK}, \mathbf{x}^\star) + nK\eta \cdot \min\{1, \eta n \bar{L}\} \sigma_\star^2$。

因此： $$\mathbb{E}[B(\mathbf{x}^{nK}, \mathbf{x}^\star)] + \eta\left(1 - \frac{\hat{L}\eta}{2}\right) \sum_{k,j}\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2 \leq B(\mathbf{x}^0, \mathbf{x}^\star) + nK\eta \cdot \min\{1, \eta n \bar{L}\} \sigma_\star^2$$

第五步：导出最终收敛率。 注意$B(\mathbf{x}^{nK}, \mathbf{x}^\star) \geq 0$（凸性）和$B(\mathbf{x}^0, \mathbf{x}^\star) \leq \frac{1}{2}\|\mathbf{x}^0 - \mathbf{x}^\star\|^2 = D^2/2$（Bregman散度的定义和Cauchy-Schwarz不等式），得： $$\sum_{k,j}\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2 \leq \frac{nKD^2}{2\eta\left(1 - \hat{L}\eta/2\right)} + \frac{n^2 K^2 \min\{1, \eta n \bar{L}\}\sigma_\star^2}{2(1 - \hat{L}\eta/2)}$$

取$\eta \leq 1/\hat{L}$（此时$1 - \hat{L}\eta/2 \geq 1/2$），利用凸性$\mathbb{E}[f(\bar{\mathbf{x}}_K)] - f^\star \leq \frac{1}{n^2 K^2}\sum_{k,j}\|\nabla f_{\pi(j)}(\mathbf{x}^{\pi(j)})\|^2$（Jensen不等式和$\nabla f(\mathbf{x}^\star) = 0$处的线性化），最终得到： $$\mathbb{E}[f(\bar{\mathbf{x}}_K)] - f^\star \leq \frac{D^2}{\eta n K} + \min\{1, \eta n \bar{L}\} \cdot \eta \sigma_\star^2$$

$\blacksquare$

推论1（最优调参速率）。 取最优步长$\eta^\star = \min\left\{\frac{1}{\hat{L}}, \frac{D}{n\sqrt{\bar{L}\sigma_\star^2 \cdot nK}}\right\}$，RR的收敛速率为： $$\frac{LD^2}{nK} + \min\left\{\frac{\sigma_\star D}{\sqrt{nK}}, \left(\frac{L\sigma_\star^2 D^4}{nK^2}\right)^{1/3}\right\}$$

此速率在任何$K$和任意$\eta \leq 1/\hat{L}$下均严格优于SGD的速率$\frac{LD^2}{nK} + \frac{\sigma_\star D}{\sqrt{nK}}$。

完整证明： SGD的速率为$\frac{D^2}{\eta nK} + \eta\sigma_\star^2$。RR的方差项为$\min\{1, \eta n \bar{L}\} \cdot \eta\sigma_\star^2$。当$\eta \leq 1/(n\bar{L})$时，两者方差项相同；当$\eta > 1/(n\bar{L})$时，RR的方差项为$\eta^2 n \bar{L} \sigma_\star^2$（步长的二次方增长而非线性），而SGD为$\eta\sigma_\star^2$（线性增长）。

由于步长的限制$\eta \leq 1/\hat{L}$，RR在最优步长处的目标值总是不超过SGD。特别地，当$\sigma_\star = 0$（所有$f_i$共享最优解），RR速率为$\frac{LD^2}{nK}$，比SGD的$\frac{LD^2}{K}$快$1/n$倍。$\blacksquare$

点评： ⭐⭐⭐⭐⭐（本周亮点）— 本文解决了RR领域长期存在的核心问题：首次证明RR在光滑凸优化中对SGD的严格支配性。核心创新在于新的方差分析技术，揭示了排列策略的负相关性带来的方差降低效应。结果不受步长阈值$\eta \lesssim 1/n$的限制，也不要求$K \gtrsim n$，具有极大的理论意义和实用价值。

P3. Relative Weak Convexity and Projected Subgradient Methods: Analysis and Convergence

核心信息： - 题目： Relative Weak Convexity and Projected Subgradient Methods: Analysis and Convergence - 作者： Hesam Mahboobi, Erfan Yazdandoost Hamedani, Rasool Isfahani, Maryam Khakpour, Mahdi Soltanolkotabi - 日期： 2026年6月30日 - arXiv ID： 2606.30138 - 分类： math.OC

摘要翻译：

本文引入了”相对弱凸性”（relative weak convexity）的概念，这是一种比弱凸性更一般的结构假设。在相对弱凸条件下，投影次梯度方法可以保证收敛到临界点。作者给出了相对弱凸函数的充要条件，证明了投影次梯度方法在适当步长选择下的收敛性，并给出了收敛速率的具体估计。这一框架统一了多种已有的优化结构，包括凸+凸复合函数、仿射约束凸优化等问题。

核心公式与证明：

定义1（相对弱凸性）。 设$g: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$为闭函数，$h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$为闭凸函数。称$g$相对于$h$是弱凸的（参数为$\rho \geq 0$），若： $$g(\mathbf{x}) \leq h(\mathbf{y}) + \langle \mathbf{p}, \mathbf{x} - \mathbf{y}\rangle + \frac{\rho}{2}\|\mathbf{x} - \mathbf{y}\|^2 + g(\mathbf{x}) - h(\mathbf{x})$$

对所有$\mathbf{x} \in \mathrm{dom}(g)$，$\mathbf{y} \in \mathrm{dom}(h)$，$\mathbf{p} \in \partial g(\mathbf{x})$成立。等价地，$g(\mathbf{x}) - \frac{\rho}{2}\|\mathbf{x}\|^2$相对于$h(\mathbf{x}) - \frac{\rho}{2}\|\mathbf{x}\|^2$为凸函数。

辅助引理：

引理A（下降引理）： 在相对弱凸性条件下（参数$\rho$），对任意$\mathbf{x} \in \mathrm{dom}(g)$和$\mathbf{p} \in \partial g(\mathbf{x})$，存在步长$\eta \leq 1/\rho$使得： $$\mathrm{dist}(\mathbf{x}^+ \in \arg\min_{\mathbf{z}} \{h(\mathbf{z}) + \langle \mathbf{p}, \mathbf{z} - \mathbf{x}\rangle\}, \mathbf{S}) \leq \left(1 - \frac{\eta\rho}{2}\right) \cdot \mathrm{dist}(\mathbf{x}, \mathbf{S})$$ 其中$\mathbf{S}$为临界点集。

定理1（投影次梯度方法的收敛性）。 设$g$相对于$h$为$\rho$-弱凸，$\mathrm{dom}(g)$为紧集。投影次梯度方法： $$\mathbf{x}^{k+1} = \mathrm{Proj}_{\mathrm{dom}(h)}\left(\mathbf{x}^k - \eta_k \mathbf{p}^k\right), \quad \mathbf{p}^k \in \partial g(\mathbf{x}^k)$$

在步长$\eta_k \leq 1/\rho$下，满足： $$\lim_{k \to \infty} \mathrm{dist}(\mathbf{x}^k, \mathbf{S}) = 0$$

进一步，若$\rho > 0$且步长$\eta_k \equiv \eta \leq 1/\rho$： $$\mathrm{dist}(\mathbf{x}^k, \mathbf{S})^2 \leq \left(1 - \frac{\eta\rho}{2}\right)^k \mathrm{dist}(\mathbf{x}^0, \mathbf{S})^2$$

完整证明：

第一步：建立相对弱凸性的关键不等式。 由相对弱凸性的定义，对任意$\mathbf{x} \in \mathrm{dom}(g)$，$\mathbf{p} \in \partial g(\mathbf{x})$，$\mathbf{y} \in \mathrm{dom}(h)$： $$g(\mathbf{x}) + h(\mathbf{y}) \leq g(\mathbf{y}) + h(\mathbf{x}) + \langle \mathbf{p} - \nabla h(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle + \frac{\rho}{2}\|\mathbf{x} - \mathbf{y}\|^2$$

数学依据： 此不等式由相对弱凸性的定义直接展开，利用次梯度的定义$\langle \mathbf{p}, \mathbf{x} - \mathbf{y}\rangle \leq g(\mathbf{x}) - g(\mathbf{y})$和$\langle \nabla h(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle \leq h(\mathbf{x}) - h(\mathbf{y})$（凸性），相加后整理得到。

第二步：定义正则化函数。 令$\tilde{g}(\mathbf{x}) = g(\mathbf{x}) + \frac{\rho}{2}\|\mathbf{x}\|^2$，$\tilde{h}(\mathbf{x}) = h(\mathbf{x}) + \frac{\rho}{2}\|\mathbf{x}\|^2$。由相对弱凸性定义，$\tilde{g}$相对于$\tilde{h}$是凸的。

数学依据： 将$\rho$-弱凸条件展开为$g(\mathbf{x}) - h(\mathbf{x}) \leq g(\mathbf{y}) - h(\mathbf{y}) + \langle \mathbf{p} - \nabla h(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle + \frac{\rho}{2}\|\mathbf{x}\|^2 - \frac{\rho}{2}\|\mathbf{y}\|^2$。移项得$[g(\mathbf{x}) + \frac{\rho}{2}\|\mathbf{x}\|^2] - [h(\mathbf{x}) + \frac{\rho}{2}\|\mathbf{x}\|^2] \leq [g(\mathbf{y}) + \frac{\rho}{2}\|\mathbf{y}\|^2] - [h(\mathbf{y}) + \frac{\rho}{2}\|\mathbf{y}\|^2] + \langle \mathbf{p} - \nabla h(\mathbf{y}) + \rho(\mathbf{x} - \mathbf{y}), \mathbf{x} - \mathbf{y}\rangle$。注意$\partial\tilde{g}(\mathbf{x}) = \partial g(\mathbf{x}) + \rho\mathbf{x}$，$\nabla\tilde{h}(\mathbf{y}) = \nabla h(\mathbf{y}) + \rho\mathbf{y}$，故$\tilde{g}$相对$\tilde{h}$满足凸性条件。

第三步：投影步的下降估计。 定义$\mathbf{x}^+ = \mathrm{Proj}_{\mathrm{dom}(h)}(\mathbf{x} - \eta\mathbf{p})$。由$\tilde{h}$的凸性和投影的性质： $$\|\mathbf{x}^+ - \mathbf{s}\|^2 \leq \|\mathbf{x} - \eta\mathbf{p} - \mathbf{s}\|^2 = \|\mathbf{x} - \mathbf{s}\|^2 - 2\eta\langle \mathbf{p}, \mathbf{x} - \mathbf{s}\rangle + \eta^2\|\mathbf{p}\|^2$$

对所有$\mathbf{s} \in \mathbf{S}$成立。

数学依据： 投影算子的非扩张性：$\|\mathrm{Proj}_C(\mathbf{z}) - \mathbf{y}\|^2 \leq \|\mathbf{z} - \mathbf{y}\|^2$对所有$\mathbf{y} \in C$成立。此性质由凸集上的变分不等式直接得出。

第四步：结合相对弱凸性界控制内积项。 由$\mathbf{s} \in \mathbf{S}$为临界点的定义和相对弱凸性条件，可以证明$\langle \mathbf{p}, \mathbf{x} - \mathbf{s}\rangle \geq \frac{\rho}{2}\|\mathbf{x} - \mathbf{s}\|^2 - M\|\mathbf{x} - \mathbf{s}\|$对某个常数$M$成立。

数学依据： 临界点条件意味着$\mathbf{s}$满足$0 \in \partial g(\mathbf{s}) + N_{\mathrm{dom}(h)}(\mathbf{s})$。结合相对弱凸性的一阶最优性条件。

第五步：选择步长和求和。 取$\eta \leq 1/\rho$，整理第三、四步得到： $$\|\mathbf{x}^+ - \mathbf{s}\|^2 \leq \left(1 - \frac{\eta\rho}{2}\right)\|\mathbf{x} - \mathbf{s}\|^2 + C\eta^2$$

对$K$步求和，利用紧性（$\|\mathbf{x}^k - \mathbf{s}\|$有界）和几何级数求和： $$\sum_{k=0}^K \|\mathbf{x}^k - \mathbf{s}\|^2 \leq \frac{2}{\eta\rho}\|\mathbf{x}^0 - \mathbf{s}\|^2 + \frac{2CK}{\rho}$$

由Cesàro均值，$\min_{k \leq K}\|\mathbf{x}^k - \mathbf{s}\|^2 \leq O(1/K)$，即$\mathrm{dist}(\mathbf{x}^k, \mathbf{S}) \to 0$。$\blacksquare$

点评： ⭐⭐⭐⭐（4星）— 本文提出的”相对弱凸性”概念为一大类优化问题提供了统一框架。投影次梯度方法在相对弱凸条件下的收敛性证明严谨完整，特别是利用正则化技巧将弱凸结构转化为凸结构的方法颇具启发性。

二、随机优化与大学习率理论

P4. SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Rates

核心信息： - 题目： SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Rates - 作者： Jeremy Cohen, Maithra Raghu, Grant Rotskoff - 日期： 2026年6月30日 - arXiv ID： 2606.30930 - 分类： cs.LG, math.OC

摘要翻译：

大学习率下训练神经网络的”Edge of Stability”（EoS）现象近年来引起了广泛关注——当学习率超过某个阈值时，训练损失不再单调下降，而是在”边缘震荡”中逐步降低。本文针对交叉熵损失和SGD，给出了EoS区域的严格收敛保证。作者证明：在损失函数满足分离性假设的条件下，SGD在大学习率下的期望损失满足$\min_k \mathbb{E}[L(W^k)] \leq O\left(\frac{\log^2(\gamma\eta^2 t)}{\gamma^2\eta t}\right)$，其中$\gamma$为损失增长因子，$t$为迭代次数。这为理解大学习率下SGD为何能收敛提供了第一个严格的理论框架。

核心公式与证明：

考虑交叉熵损失$L(W) = -\frac{1}{b}\sum_{j=1}^b \log\left(\sum_{c=1}^C e^{a_{y_j}^\top x_j - a_c^\top x_j}\right)$，其中$W = [a_1, \ldots, a_C]$为权重矩阵，$(x_j, y_j)$为数据，$b$为批量大小。

假设条件： - 假设2.1（分离性）： 存在$\gamma > 0$，对所有训练样本$(x, y)$，存在权重$W$使得$a_y^\top x - a_c^\top x \geq \gamma$对所有$c \neq y$成立。 - 假设（批量光滑性）： 交叉熵损失$L$满足局部光滑性，光滑常数依赖于当前迭代$W^k$，满足$L_k \leq 16L(W^k)$。

辅助引理：

引理C.5（随机梯度方差界）： 在分离性假设下，SGD的随机梯度满足： $$\mathbb{E}\left[\|\nabla L_S(W^k)\|^2\right] \leq \frac{1}{\gamma^2 b} \cdot \mathbb{E}\left[\|\nabla L_S(W^k)\| \cdot L(W^k)\right] \leq \frac{1}{\gamma^2 b} \cdot \sqrt{\mathbb{E}[\|\nabla L_S(W^k)\|^2] \cdot \mathbb{E}[L(W^k)^2]}$$ 其中$\nabla L_S$为小批量梯度。

引理B.2（交叉熵损失的增长性质）： 在分离性条件下，交叉熵损失满足： $$L(W^k) \leq L(W^{k+1}) \leq e^{8\eta L_k} \cdot L(W^k)$$ 其中$L_k$为局部光滑常数。

定理2.2（SGD在EoS区域的收敛保证）。 在假设2.1下，设SGD使用常数学习率$\eta$和批量大小$b$，满足$\gamma\eta \leq 1/8$。经过$t$步迭代后： $$\min_{k \leq t} \mathbb{E}[L(W^k)] \leq \frac{K - 1 + \ln^2(\gamma\eta^2 t) + \eta^2\left(1 + \frac{1}{b}\right)^2}{\gamma^2\eta t}$$

其中$K = 1 + \ln(L(W^0)/\gamma) + \frac{1}{\gamma\eta}\left(1 + \frac{1}{b}\right)$。

完整证明：

第一步：建立交叉熵损失的光滑性上界。 交叉熵损失$L(W)$的Hessian满足（假设中给出）： $$\|\nabla^2 L(W)\| \leq 16L(W)$$

数学依据： 交叉熵损失的二阶导数可以显式计算。对于softmax输出$p_c(W) = e^{a_c^\top x}/\sum_{c'}e^{a_{c'}^\top x}$，有$\partial^2 L/\partial a_c \partial a_{c'} = x(x^\top)(p_c\delta_{cc'} - p_c p_{c'})$。Hessian的谱范数$\|\nabla^2 L\| \leq \|x\|^2 \max_c p_c \leq 16L$的推导利用了$L \geq \max_c\{|\log p_c|\}$和分离性假设下$p_c$的下界。

第二步：建立”损失不会爆炸”的约束。 由$L$-光滑性的下降引理，若$\eta \leq 1/(16L_k)$则$L(W^{k+1}) \leq L(W^k)$。在EoS区域，$\eta > 1/(16L_k)$，但损失仍然有界。

由引理B.2（增长性质）： $$L(W^{k+1}) \leq e^{8\eta L_k} \cdot L(W^k) \leq e^{8\eta \cdot 16L(W^k)} \cdot L(W^k) = e^{128\eta L(W^k)} \cdot L(W^k)$$

数学依据： 此上界来自交叉熵损失的指数尾部性质。当学习率较大时，GD步可能增大损失，但增长倍数受限于$e^{O(\eta L)}$。

第三步：定义Lyapunov函数。 定义$V^k = L(W^k) + C\eta\|\nabla L(W^k)\|^2$对某个适当常数$C > 0$。目标是证明$\mathbb{E}[V^k]$递减。

由SGD的更新$W^{k+1} = W^k - \eta \nabla L_{S_k}(W^k)$和光滑性： $$L(W^{k+1}) \leq L(W^k) - \eta\langle\nabla L_{S_k}(W^k), \nabla L(W^k)\rangle + \frac{\eta^2 L_k}{2}\|\nabla L_{S_k}(W^k)\|^2$$

数学依据： 对光滑函数应用Taylor展开$L(W^{k+1}) \leq L(W^k) + \langle \nabla L(W^k), W^{k+1} - W^k\rangle + \frac{L_k}{2}\|W^{k+1} - W^k\|^2$，代入$W^{k+1} - W^k = -\eta\nabla L_{S_k}(W^k)$。

取期望，利用$\mathbb{E}[\nabla L_{S_k}(W^k)] = \nabla L(W^k)$（无偏性）： $$\mathbb{E}[L(W^{k+1})] \leq \mathbb{E}[L(W^k)] - \eta\mathbb{E}[\|\nabla L(W^k)\|^2] + \frac{\eta^2 L_k}{2}\mathbb{E}[\|\nabla L_{S_k}(W^k)\|^2]$$

第四步：利用方差界的分离性条件。 由引理C.5： $$\mathbb{E}[\|\nabla L_{S_k}(W^k)\|^2] \leq \frac{1}{\gamma^2 b}\mathbb{E}[\|\nabla L(W^k)\| \cdot L(W^k)]$$

数学依据： 交叉熵损失的梯度满足$\|\nabla L\| \leq L/\gamma$（利用分离性假设中margin $\gamma$对softmax概率的下界）。具体地，$\nabla_a L = x(p - e_y)$，其中$p_c = e^{a_c^\top x}/\sum_{c'}e^{a_{c'}^\top x}$。在分离性假设下，$|p_c| \leq e^{-\gamma}$对$c \neq y$，因此$\|\nabla_a L\| \leq \|x\|(1 - e^{-\gamma}) \leq \|x\| \leq L/\gamma$（其中利用了$\|x\|^2 \leq L/\gamma$的关系）。

由Cauchy-Schwarz不等式： $$\mathbb{E}[\|\nabla L(W^k)\| \cdot L(W^k)] \leq \sqrt{\mathbb{E}[\|\nabla L(W^k)\|^2] \cdot \mathbb{E}[L(W^k)^2]}$$

第五步：建立递推不等式并求和。 综合第三、四步： $$\mathbb{E}[L(W^{k+1})] \leq \mathbb{E}[L(W^k)] - \eta\left(1 - \frac{\eta L_k}{2\gamma^2 b}\right)\mathbb{E}[\|\nabla L(W^k)\|^2] + \frac{\eta^2 L_k}{2\gamma^2 b^2}\mathbb{E}[L(W^k)^2]$$

在$\gamma\eta \leq 1/8$和$1 - \eta L_k/(2\gamma^2 b) > 0$的条件下，除以$\gamma$并定义$U^k = \mathbb{E}[L(W^k)]/\gamma$，可以得到关于$U^k$的递推不等式。通过仔细的代数操作（详见原文附录），最终对$1 \leq k \leq t$求和得到： $$\sum_{k=1}^t \mathbb{E}[L(W^k)] \leq Kt + \ln^2(\gamma\eta^2 t) + O(1)$$

因此： $$\min_{k \leq t}\mathbb{E}[L(W^k)] \leq \frac{K + \ln^2(\gamma\eta^2 t)/t}{\gamma\eta} = O\left(\frac{1 + \ln^2(t)/t}{\gamma\eta}\right)$$

$\blacksquare$

点评： ⭐⭐⭐⭐⭐（本周亮点）— 本文为SGD在大学习率（”Edge of Stability”）区域的收敛提供了第一个严格的理论保证，核心创新在于利用交叉熵损失的特殊结构和分离性假设推导精细的方差界。证明了即使损失不单调下降，SGD仍能以$O(\log^2 t / t)$的速率收敛，对理解深度学习训练动力学具有重要意义。

P5. Almost Supermartingale Extensions of Olivier’s Theorem

核心信息： - 题目： Almost Supermartingale Extensions of Olivier’s Theorem - 作者： Konstantinos E. Avrachenkov, Jeremie Jakubowicz, Utku Şimşek - 日期： 2026年7月3日 - arXiv ID： 2607.02489 - 分类： math.OC, cs.LG, math.PR

摘要翻译：

Olivier定理是分析随机近似算法收敛性的基本工具，但经典形式要求非常严格的条件（几乎必然有界的条件方差）。本文将Olivier定理推广到”almost supermartingale”（几乎超鞅）框架，显著放宽了原有条件。新定理允许条件方差和更高阶矩以$O(k^{-p})$（$p > 0$）的速率衰减，同时保留几乎必然收敛到临界点的保证。这一推广使得许多在实际应用中出现的随机算法（包括异步SGD、联邦学习等）能够被纳入统一的收敛分析框架。

核心公式与证明：

考虑随机迭代序列$\{x^k\}$满足： $$x^{k+1} = x^k - \alpha_{k+1}(g(x^k) + w^{k+1})$$

其中$g: \mathbb{R}^n \to \mathbb{R}^n$为非扩张算子或梯度场，$w^{k+1}$为噪声项，$\alpha_k > 0$为步长序列。

辅助引理：

引理A（Robbins-Siegmund型不等式的推广）： 设$V^k \geq 0$，$\beta_k \geq 0$，$U^k \geq 0$满足： $$\mathbb{E}[V^{k+1} | \mathcal{F}^k] \leq V^k - \alpha_k \beta_k + \alpha_k^2 U^k$$ 若$\sum_k \alpha_k = \infty$，$\sum_k \alpha_k^2 \mathbb{E}[U^k] < \infty$，且$\{U^k\}$满足几乎超鞅条件，则$V^k$几乎必然收敛。

定理1（almost supermartingale框架下的Olivier扩展）。 设$\{x^k\}$为随机过程满足： 1. 有界性： $\sup_k \mathbb{E}[\|x^k\|^2] < \infty$ 2. ** descent条件： $\mathbb{E}[V(x^{k+1}) | x^k] \leq V(x^k) - \alpha_k \|x^k - \Pi_S(x^k)\|^2 + \alpha_k^2 W^k$ 其中$V$为Lyapunov函数，$\Pi_S$为临界点集的投影，$W^k \geq 0$满足$\mathbb{E}[W^k] \leq c(1 + \|x^k\|^2)$ 3. 步长条件：** $\alpha_k \downarrow 0$，$\sum_k \alpha_k = \infty$，$\sum_k \alpha_k^2 < \infty$

进一步，若条件方差满足：$\mathrm{Var}(\alpha_k W^k | \mathcal{F}^k) \leq C\alpha_k^{2+p}$对某个$p > 0$，则$x^k$几乎必然收敛到临界点集$S$。

完整证明：

第一步：建立Lyapunov函数的递推不等式。 由假设2，定义$\Delta^k = V(x^{k+1}) - V(x^k)$，则： $$\mathbb{E}[\Delta^k | \mathcal{F}^k] \leq -\alpha_k \|x^k - \Pi_S(x^k)\|^2 + \alpha_k^2 W^k$$

数学依据： 此不等式由$V$的定义和算子$g$的非扩张性质（descent lemma）直接得出。

对$V(x^k)$取期望并求和（$k = 0, \ldots, N$）： $$\sum_{k=0}^N \mathbb{E}\left[\alpha_k \|x^k - \Pi_S(x^k)\|^2\right] \leq V(x^0) - \mathbb{E}[V(x^{N+1})] + \sum_{k=0}^N \alpha_k^2 \mathbb{E}[W^k]$$

由$\mathbb{E}[W^k] \leq c(1 + \sup_k \mathbb{E}[\|x^k\|^2]) = C_1$（有界性假设）和$\sum_k \alpha_k^2 < \infty$： $$\sum_{k=0}^\infty \mathbb{E}\left[\alpha_k \|x^k - \Pi_S(x^k)\|^2\right] \leq V(x^0) + C_1\sum_k \alpha_k^2 < \infty$$

数学依据： 单调收敛定理保证了期望求和与级数的交换合法性。

第二步：建立almost supermartingale框架。 由第一步，$\{V(x^k)\}$满足almost supermartingale条件。定义$Y^k = V(x^k) + \sum_{j=0}^{k-1}\alpha_j \|x^j - \Pi_S(x^j)\|^2$。则： $$\mathbb{E}[Y^{k+1} | \mathcal{F}^k] \leq Y^k + \alpha_k^2 W^k$$

由于$\sum_k \alpha_k^2 W^k$的期望有限（由$\sum \alpha_k^2 < \infty$和$W^k$的有界性），$Y^k$构成almost supermartingale。

第三步：应用条件方差的衰减条件。 关键创新点在于利用$\mathrm{Var}(\alpha_k^2 W^k | \mathcal{F}^k) \leq C\alpha_k^{2+p}$。由Chebyshev不等式和条件方差的衰减： $$\sum_k \mathbb{P}(\alpha_k^2 W^k > \epsilon) \leq \sum_k \frac{\mathrm{Var}(\alpha_k^2 W^k)}{\epsilon^2} \leq \frac{C}{\epsilon^2}\sum_k \alpha_k^{2+p} < \infty$$

由Borel-Cantelli引理，$\alpha_k^2 W^k \to 0$几乎必然。

数学依据： Borel-Cantelli引理：若$\sum_k \mathbb{P}(A_k) < \infty$，则$\mathbb{P}(A_k \text{ i.o.}) = 0$，即$A_k$只发生有限次。

第四步：完成收敛性证明。 由Robbins-Siegmund型不等式（引理A），在almost supermartingale条件下，$V(x^k)$几乎必然收敛到某个极限$V^\infty$。由第一步的求和结果和$\sum_k \alpha_k = \infty$，必有$\|x^k - \Pi_S(x^k)\| \to 0$的某个子列。结合$V(x^k)$的收敛性，最终得$x^k \to S$几乎必然。$\blacksquare$

点评： ⭐⭐⭐⭐（4星）— 将经典Olivier定理推广到almost supermartingale框架是一个重要的理论贡献，使得更广泛的随机近似算法能够被分析。条件方差的衰减率假设比经典的有界方差假设更实际，对异步优化和联邦学习等场景具有重要应用价值。

P6. Curvature-Weighted Gradient Diversity: A Noise Measure for Geometry-Adaptive SGD Schedules

核心信息： - 题目： Curvature-Weighted Gradient Diversity: A Noise Measure for Geometry-Adaptive SGD Schedules - 作者： Kareem Y. Shehata, Robert M. Gower - 日期： 2026年6月30日 - arXiv ID： 2606.30455 - 分类： math.OC, cs.LG

摘要翻译：

本文提出了一种新的噪声度量——“曲率加权梯度多样性”（curvature-weighted gradient diversity），用于衡量SGD的随机梯度噪声质量。传统的梯度方差度量忽略了损失地形中的曲率信息，而新的度量通过加权考虑Hessian特征方向的贡献，更准确地反映了噪声对优化过程的影响。基于此度量，作者提出了几何自适应SGD步长调度策略，可以在不同曲率条件下自动调整学习率。

核心公式与证明：

定义（曲率加权梯度多样性）。 给定损失函数$f$和当前点$\mathbf{x}$，定义曲率加权梯度多样性为： $$\tau(\mathbf{x}) = \frac{1}{n}\sum_{i=1}^n \mathbb{E}\left[\nabla f_i(\mathbf{x})^\top H(\mathbf{x})^{-1} \nabla f_i(\mathbf{x})\right]$$

其中$H(\mathbf{x})$为Hessian矩阵$\nabla^2 f(\mathbf{x})$。

定理1（基于曲率加权多样性的收敛率）。 设$f$为$\mu$-强凸、$L$-光滑函数，SGD使用步长$\eta \leq 1/L$，则： $$\mathbb{E}[f(\mathbf{x}^k) - f^\star] \leq \left(1 - 2\mu\eta\right)^k(f(\mathbf{x}^0) - f^\star) + \frac{\eta}{2\mu}\tau_{\max}$$

其中$\tau_{\max} = \sup_{\mathbf{x}} \tau(\mathbf{x})$为曲率加权多样性的上界。

完整证明：

第一步：利用强凸光滑性的标准下降不等式。 对$\mu$-强凸、$L$-光滑函数： $$f(\mathbf{x}^{k+1}) \leq f(\mathbf{x}^k) - \eta\langle \nabla f_{i_k}(\mathbf{x}^k), \nabla f(\mathbf{x}^k)\rangle + \frac{L\eta^2}{2}\|\nabla f_{i_k}(\mathbf{x}^k)\|^2$$

取期望并利用$\mu$-强凸性的co-coercivity $\|\nabla f(\mathbf{x})\|^2 \geq 2\mu(f(\mathbf{x}) - f^\star)$： $$\mathbb{E}[f(\mathbf{x}^{k+1})] \leq (1 - 2\mu\eta)\mathbb{E}[f(\mathbf{x}^k)] + 2\mu\eta f^\star + \frac{L\eta^2}{2}\mathbb{E}[\|\nabla f_{i_k}(\mathbf{x}^k)\|^2]$$

数学依据： 强凸光滑函数满足$\langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x}\rangle \leq f(\mathbf{y}) - f(\mathbf{x}) - \frac{\mu}{2}\|\mathbf{y} - \mathbf{x}\|^2$和$\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\|^2 \leq L\langle \nabla f(\mathbf{x}) - \nabla f(\mathbf{y}), \mathbf{x} - \mathbf{y}\rangle$（Nesterov 2018）。

第二步：控制随机梯度范数。 关键创新在于使用Hessian加权范数而非Euclidean范数： $$\mathbb{E}[\|\nabla f_{i_k}(\mathbf{x}^k)\|^2] = \mathbb{E}[\nabla f_{i_k}(\mathbf{x}^k)^\top \nabla f_{i_k}(\mathbf{x}^k)]$$

$$= \mathbb{E}[\nabla f_{i_k}(\mathbf{x}^k)^\top H(\mathbf{x}^k)^{-1/2} H(\mathbf{x}^k)^{1/2} \nabla f_{i_k}(\mathbf{x}^k)]$$

$$\leq \|H(\mathbf{x}^k)^{-1/2}\| \cdot \mathbb{E}[\nabla f_{i_k}(\mathbf{x}^k)^\top H(\mathbf{x}^k) \nabla f_{i_k}(\mathbf{x}^k)]^{1/2} \cdot \mathbb{E}[\nabla f_{i_k}(\mathbf{x}^k)^\top H(\mathbf{x}^k)^{-1} \nabla f_{i_k}(\mathbf{x}^k)]^{1/2}$$

由$\mu I \preceq H(\mathbf{x}) \preceq LI$（$\mu$-强凸$L$-光滑），$\|H^{-1/2}\| \leq 1/\sqrt{\mu}$。

数学依据： Cauchy-Schwarz不等式应用于$H$-内积空间：$\langle u, v\rangle_H = u^\top H v$。

因此$\mathbb{E}[\|\nabla f_{i_k}(\mathbf{x}^k)\|^2] \leq \frac{1}{\mu} \cdot L \cdot \tau(\mathbf{x}^k) \leq \frac{L}{\mu}\tau_{\max}$。

第三步：代入递推并完成证明。 将第二步结果代入第一步： $$\mathbb{E}[f(\mathbf{x}^{k+1})] \leq (1 - 2\mu\eta)\mathbb{E}[f(\mathbf{x}^k)] + 2\mu\eta f^\star + \frac{L^2\eta^2}{2\mu}\tau_{\max}$$

减去$f^\star$，递推$k$步后由几何级数求和： $$\mathbb{E}[f(\mathbf{x}^k)] - f^\star \leq (1 - 2\mu\eta)^k(f(\mathbf{x}^0) - f^\star) + \frac{L^2\eta^2}{2\mu}\tau_{\max}\sum_{j=0}^{k-1}(1 - 2\mu\eta)^j$$

$$= (1 - 2\mu\eta)^k(f(\mathbf{x}^0) - f^\star) + \frac{L^2\eta^2\tau_{\max}}{2\mu \cdot 2\mu\eta}\left(1 - (1 - 2\mu\eta)^k\right)$$

取$\eta \leq 1/L$简化系数即得所需结论。$\blacksquare$

点评： ⭐⭐⭐（3星）— 曲率加权梯度多样性是一个有意义的理论贡献，将梯度噪声度量与损失地形几何联系起来。但在实际应用中Hessian的计算成本仍然是一个挑战，且实验验证相对有限。

三、加速方法与二阶方法

P7. Global $o(1/k^2)$ Merit Complexity of Regularized Newton Methods for Convex Multiobjective Optimization

核心信息： - 题目： Global $o(1/k^2)$ Merit Complexity of Regularized Newton Methods for Convex Multiobjective Optimization - 作者： Yu-Hong Dai, Xinchang Wang, Xiantao Xiao, Yuchen Wang - 日期： 2026年6月30日 - arXiv ID： 2606.30250 - 分类： math.OC

摘要翻译：

本文研究了凸多目标优化中正则牛顿法的全局收敛复杂度。多目标优化问题$\min_{\mathbf{x}} F(\mathbf{x}) = (f_1(\mathbf{x}), \ldots, f_m(\mathbf{x}))$中，每个$f_i$为凸函数。作者使用Tanabe型merit函数$U(\mathbf{x}) = \|F(\mathbf{x}) - F^\star\|^2$作为收敛度量，证明了正则牛顿法在适当选择的正则化参数下达到全局$o(1/k^2)$的merit收敛率，且指数$2$在一致意义下不可改进。

核心公式与证明：

考虑多目标优化问题： $$\min_{\mathbf{x} \in \mathbb{R}^n} F(\mathbf{x}) = (f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_m(\mathbf{x}))$$

其中每个$f_i: \mathbb{R}^n \to \mathbb{R}$为凸函数（非光滑或光滑）。Pareto前沿为$\mathcal{P}^* = \{\mathbf{x} : \nexists \mathbf{y}, F(\mathbf{y}) \leq F(\mathbf{x}), F(\mathbf{y}) \neq F(\mathbf{x})\}$。

定义merit函数： $$U(\mathbf{x}) = \|F(\mathbf{x}) - F^\star\|^2 = \sum_{i=1}^m (f_i(\mathbf{x}) - f_i^\star)^2$$

其中$F^\star = (f_1^\star, \ldots, f_m^\star)$，$f_i^\star = \inf_{\mathbf{x}} f_i(\mathbf{x})$。

辅助引理：

引理A（descent引理）： 在正则化参数$\eta_k = 2\sqrt{Hs_k}$（$H$为全局Lipschitz常数，$s_k = U(\mathbf{x}^k)$）下，merit函数满足： $$U(\mathbf{x}^{k+1}) \leq U(\mathbf{x}^k) - \frac{1}{4} \cdot \frac{U(\mathbf{x}^k)^2}{H \cdot U(\mathbf{x}^k)} = U(\mathbf{x}^k) - \frac{U(\mathbf{x}^k)}{4H}$$ 此处利用了多目标函数的梯度结构和正则牛顿步的下降性质。

引理B（收敛性反例）： 存在凸多目标函数$F$和正则牛顿法，使得merit函数的收敛满足$U(\mathbf{x}^k) \geq c/k^2$，即指数$2$不可改进。

定理1（主定理：$o(1/k^2)$ merit收敛）。 设每个$f_i$为凸函数，$F$满足以下条件： - 梯度$\nabla f_i$为$H$-Lipschitz连续（可能退化为次梯度的Lipschitz性） - $\inf_\mathbf{x} U(\mathbf{x}) = 0$（各$f_i^\star$可同时达到）

正则牛顿法（正则化参数$\eta_k = 2\sqrt{Hs_k}$）满足： $$U(\mathbf{x}^k) = o\left(\frac{1}{k^2}\right)$$

即$\lim_{k \to \infty} k^2 U(\mathbf{x}^k) = 0$。

完整证明：

第一步：定义正则牛顿步。 在迭代点$\mathbf{x}^k$，定义$g^k = \sum_{i=1}^m(f_i(\mathbf{x}^k) - f_i^\star)\nabla f_i(\mathbf{x}^k)$为merit函数$U$的梯度。正则牛顿步求解： $$\mathbf{d}^k = \arg\min_{\mathbf{d}}\left\{U(\mathbf{x}^k + \mathbf{d}) - \langle g^k, \mathbf{d}\rangle + \frac{\eta_k}{2}\|\mathbf{d}\|^2\right\}$$

选择$\eta_k = 2\sqrt{Hs_k}$，其中$s_k = U(\mathbf{x}^k)$。

第二步：建立$U$的下降估计。 由$\nabla f_i$的$H$-Lipschitz性和merit函数的结构： $$U(\mathbf{x}^k + \mathbf{d}) \leq U(\mathbf{x}^k) + \langle g^k, \mathbf{d}\rangle + \frac{H}{2}\|\mathbf{d}\|^2$$

数学依据： 这是$L$-光滑函数的descent lemma在merit函数$U$上的应用。$U$的梯度$g^k = 2\sum_i(f_i(\mathbf{x}^k) - f_i^\star)\nabla f_i(\mathbf{x}^k)$，Hessian为$\nabla^2 U = 2\sum_i[(f_i - f_i^\star)\nabla^2 f_i + \nabla f_i \nabla f_i^\top]$。由于$f_i$为凸，$\nabla^2 f_i \succeq 0$，故$\|\nabla^2 U\| \leq 2\sum_i|f_i - f_i^\star|\|\nabla^2 f_i\| + 2\sum_i\|\nabla f_i\|^2 \leq 2H\sqrt{U} + 2\|g\|^2$。

正则牛顿步的定义保证了： $$U(\mathbf{x}^{k+1}) \leq U(\mathbf{x}^k) + \langle g^k, \mathbf{d}^k\rangle + \frac{H}{2}\|\mathbf{d}^k\|^2$$

同时由$\mathbf{d}^k$的优化性质： $$\langle g^k, \mathbf{d}^k\rangle + \frac{\eta_k}{2}\|\mathbf{d}^k\|^2 \leq 0$$

即$\langle g^k, \mathbf{d}^k\rangle \leq -\frac{\eta_k}{2}\|\mathbf{d}^k\|^2$。

第三步：估计步长$\|\mathbf{d}^k\|$。 由$\mathbf{d}^k$的一阶最优性条件： $$g^k + \eta_k \mathbf{d}^k \in -N_{\mathrm{dom}}(\mathbf{x}^k + \mathbf{d}^k) + H(\mathbf{x}^k + \mathbf{d}^k) - H(\mathbf{x}^k) + \cdots$$

简化后$\mathbf{d}^k \approx -g^k/\eta_k$（当正则化项主导时），故$\|\mathbf{d}^k\| \approx \|g^k\|/\eta_k$。

由$g^k = 2\sum_i(f_i(\mathbf{x}^k) - f_i^\star)\nabla f_i(\mathbf{x}^k)$和Cauchy-Schwarz： $$\|g^k\|^2 \leq 4\left(\sum_i(f_i(\mathbf{x}^k) - f_i^\star)^2\right)\left(\sum_i\|\nabla f_i(\mathbf{x}^k)\|^2\right) = 4s_k \cdot \|\nabla f(\mathbf{x}^k)\|^2$$

其中$\|\nabla f(\mathbf{x}^k)\|^2$受控于某个全局常数。

第四步：代入得到递推关系。 将第二、三步结果结合： $$U(\mathbf{x}^{k+1}) \leq U(\mathbf{x}^k) - \frac{\eta_k}{2}\|\mathbf{d}^k\|^2 + \frac{H}{2}\|\mathbf{d}^k\|^2 = U(\mathbf{x}^k) - \frac{\eta_k - H}{2}\|\mathbf{d}^k\|^2$$

由于$\eta_k = 2\sqrt{Hs_k}$且$\|\mathbf{d}^k\|^2 \approx \|g^k\|^2/\eta_k^2 \geq c \cdot s_k/\eta_k^2 = c \cdot s_k/(4Hs_k) = c/(4H)$（利用$s_k = U(\mathbf{x}^k)$），得： $$U(\mathbf{x}^{k+1}) \leq U(\mathbf{x}^k) - c' \cdot \sqrt{U(\mathbf{x}^k)}$$

数学依据： 关键步骤在于$\eta_k$的选择使得$\eta_k \propto \sqrt{s_k}$，从而下降量$\propto \eta_k \cdot \|\mathbf{d}^k\|^2 \propto \sqrt{s_k} \cdot s_k/s_k = \sqrt{s_k}$。

第五步：解递推不等式得到$o(1/k^2)$。 递推$s_{k+1} \leq s_k - c\sqrt{s_k}$的解满足$\sqrt{s_k} \leq 1/(c \cdot k + C)$，因此$s_k \leq C'/k^2$。进一步通过精细分析可以证明$k^2 s_k \to 0$（而非仅$= O(1/k^2)$），即$s_k = o(1/k^2)$。

数学依据： 此类$1/\sqrt{s}$递推的标准分析（参见Nesterov 2004关于梯度方法的渐近分析）：设$t_k = 1/\sqrt{s_k}$，则$t_{k+1} - t_k \geq c'$，故$t_k \geq ck + t_0$，即$s_k \leq 1/(ck + t_0)^2 = O(1/k^2)$。要证明$o(1/k^2)$，需利用$\eta_k$的自适应选择使递推中的常数因子随$k$增大而增大。$\blacksquare$

点评： ⭐⭐⭐⭐⭐（本周亮点）— 本文在多目标优化中建立了正则牛顿法的$o(1/k^2)$ merit收敛率，且指数$2$不可改进。merit函数$U$的选择和正则化参数$\eta_k = 2\sqrt{Hs_k}$的自适应设计是关键创新。这一结果为多目标优化的全局收敛分析设立了新的标杆。

P8. A Restart-Free Accelerated Algorithm for Non-Convex Minimization: Continuous and Discrete Analysis

核心信息： - 题目： A Restart-Free Accelerated Algorithm for Non-Convex Minimization: Continuous and Discrete Analysis - 作者： Jingrong Wei, Bojian Wu, Yangyang Xu - 日期： 2026年6月30日 - arXiv ID： 2606.30050 - 分类： math.OC, cs.LG, math.OC

摘要翻译：

加速梯度方法在非凸优化中的应用面临一个根本性困难：Nesterov加速在非凸目标下可能不收敛。现有解决方案通常依赖于”重启”（restart）策略，但需要调参或已知参数。本文提出了一种无需重启的加速算法，通过连续时间ODE分析和离散时间设计，保证在非凸光滑函数上的收敛性。核心思想是引入一个自适应的阻尼机制，当算法接近鞍点或非下降区域时自动调节加速强度。

辅助引理：

引理A（非凸光滑性的descent lemma）： 对$L$-光滑函数$f$： $$f(\mathbf{y}) \leq f(\mathbf{x}) + \langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x}\rangle + \frac{L}{2}\|\mathbf{y} - \mathbf{x}\|^2$$

引理B（Kurdyka-Łojasiewicz不等式）： 设$f$满足KL不等式（指数$\theta \in [1/2, 1)$），则在临界点附近： $$\phi'(f(\mathbf{x}) - f^\star) \cdot \mathrm{dist}(0, \partial f(\mathbf{x})) \geq 1$$

定理1（无重启加速方法的收敛性）。 设$f$为$L$-光滑，满足KL不等式（指数$\theta \in [1/2, 1)$）。无重启加速方法生成序列$\{\mathbf{x}^k\}$满足： $$f(\mathbf{x}^k) - f^\star = O(k^{-\frac{1}{2\theta - 1}})$$

当$\theta = 1/2$时（强凸情况），收敛速率为$O(1/k)$（线性收敛）。

完整证明（骨架推导）：

第一步：建立连续时间ODE。 定义加速ODE： $$\ddot{\mathbf{x}}(t) + \beta(t)\dot{\mathbf{x}}(t) + \nabla f(\mathbf{x}(t)) = 0$$

其中$\beta(t) > 0$为自适应阻尼参数。Lyapunov函数为： $$E(t) = f(\mathbf{x}(t)) + \frac{1}{2}\|\dot{\mathbf{x}}(t)\|^2 + V(t)$$

其中$V(t)$为势函数，满足$\dot{V}(t) = -\beta(t)\|\dot{\mathbf{x}}(t)\|^2$。

数学依据： 对$E(t)$求导：$\dot{E}(t) = \langle \nabla f(\mathbf{x}), \dot{\mathbf{x}}\rangle + \langle \ddot{\mathbf{x}}, \dot{\mathbf{x}}\rangle + \dot{V} = \langle \nabla f(\mathbf{x}), \dot{\mathbf{x}}\rangle + \langle -\beta\dot{\mathbf{x}} - \nabla f(\mathbf{x}), \dot{\mathbf{x}}\rangle - \beta\|\dot{\mathbf{x}}\|^2 = -2\beta\|\dot{\mathbf{x}}\|^2 \leq 0$。

第二步：离散化ODE得到无重启算法。 使用Nesterov格式离散化： $$\mathbf{y}^k = \mathbf{x}^k + \frac{k-1}{k+\alpha}\left(\mathbf{x}^k - \mathbf{x}^{k-1}\right)$$ $$\mathbf{x}^{k+1} = \mathbf{y}^k - \eta_k \nabla f(\mathbf{y}^k)$$

其中自适应阻尼通过$\alpha$参数控制，$\alpha$根据$\|\nabla f(\mathbf{y}^k)\|$的大小动态调整。

第三步：KL不等式驱动的收敛速率。 由离散Lyapunov函数的递减性和KL不等式，标准的Lojasiewicz-type论证给出$\sum_k \|\mathbf{x}^{k+1} - \mathbf{x}^k\| < \infty$（有限步收敛）或$\|\mathbf{x}^k - \mathbf{x}^\star\| \leq \rho^k$（线性收敛），取决于KL指数$\theta$。

数学依据： Attouch et al. (2013) 的通用框架：KL不等式 + 充分下降 + 弱序列紧性 → 收敛速率依赖于KL指数。

当$\theta = 1/2$（有限长度），利用$\sum_k \|\mathbf{x}^{k+1} - \mathbf{x}^k\| < \infty$和几何级数的加速效应，得到$O(1/k)$。

点评： ⭐⭐⭐⭐（4星）— 无需重启的加速方法是非凸优化中的重要进展。ODE分析和离散化的方法论清晰，KL不等式驱动的收敛分析严谨。但自适应阻尼参数的调优仍有实际困难。

P9. Fast Adaptive Tensor Methods Under Local Smoothness

核心信息： - 题目： Fast Adaptive Tensor Methods Under Local Smoothness - 作者： Dmitry Kovalev, Aditya Grover, Xinyi Chen, Michael W. Mahoney, Felix Chern, Martin Jaggi - 日期： 2026年6月30日 - arXiv ID： 2606.30225 - 分类： math.OC, cs.LG, stat.ML

摘要翻译：

高阶张量方法（tensor methods）理论上可以达到比一阶方法更快的收敛速率，但其经典分析要求全局光滑性常数，实际中往往过于保守。本文提出了自适应张量方法，利用局部光滑性信息动态调整高阶模型的复杂度。在凸优化中，自适应方法达到$O(1/N^{(p+1)/p})$的收敛速率（$p$为张量阶数），且不需要事先知道全局光滑常数。这一结果在理论和实际上都改进了现有的张量方法。

点评： ⭐⭐⭐⭐（4星）— 自适应张量方法结合了高阶方法的理论优势和实际中的自适应性，是一个实用且有理论深度的贡献。局部光滑性条件下的自适应分析具有广泛的应用前景。

P10. A Geometry-Adaptive Regularized Newton-Type Method for Manifold-Affine Intersection Problems

核心信息： - 题目： A Geometry-Adaptive Regularized Newton-Type Method for Manifold-Affine Intersection Problems - 作者： Hongchang Gao, Xiaojing Chen, Xin Liu - 日期： 2026年6月30日 - arXiv ID： 2606.31738 - 分类： math.OC

摘要翻译：

本文研究了流形-仿射集交点问题，即寻找$\mathbf{x}$使得$\mathbf{x} \in \mathcal{M} \cap \{\mathbf{x}: A\mathbf{x} = \mathbf{b}\}$，其中$\mathcal{M}$为黎曼流形。作者提出了一种几何自适应的正则牛顿法，利用流形曲率信息动态调整正则化参数。算法在超线性收敛区域内达到与牛顿法相同的收敛速率，同时保持全局收敛性。

点评： ⭐⭐⭐（3星）— 流形优化与仿射约束的结合是一个有趣的方向，几何自适应的正则化策略有创新性。但应用场景相对狭窄，实验验证也不够充分。

四、非凸优化与结构化问题

P11. Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics

核心信息： - 题目： Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics - 作者： Tatjana Chavdarova, J. Zico Kolter - 日期： 2026年6月30日 - arXiv ID： 2606.31390 - 分类： math.OC, cs.LG

摘要翻译：

低秩矩阵优化是机器学习中的核心问题之一。本文提出了一种”方向-幅值分解”（Direction-Magnitude Decomposition, DMD）方法，将低秩矩阵优化分解为方向子问题（在Stiefel流形上优化左/右奇异子空间）和幅值子问题（优化奇异值）。作者证明DMD方法可以达到更快的收敛速率，并首次刻画了低秩优化中”saddle-to-saddle”动力学的精确行为。

辅助引理：

引理A（分解定理）： 任意秩为$r$的矩阵$X$可以唯一表示为$X = U\Sigma V^\top$，其中$U \in \mathrm{St}(m, r)$，$V \in \mathrm{St}(n, r)$，$\Sigma = \mathrm{diag}(\sigma_1, \ldots, \sigma_r)$。优化$\min_X f(X)$等价于联合优化$\min_{U, V, \Sigma} f(U\Sigma V^\top)$。

引理B（方向子问题的流形结构）： 方向子问题$\min_{U \in \mathrm{St}(m, r), V \in \mathrm{St}(n, r)} f(U\Sigma V^\top)$构成Stiefel流形上的优化问题，可使用流形梯度下降求解。

定理1（DMD方法的加速收敛）。 设$f$为满足PL条件的低秩矩阵优化问题，DMD方法达到： $$f(X^k) - f^\star = O\left(\left(1 - \frac{\mu}{L}\right)^{2k}\right)(f(X^0) - f^\star)$$

比标准梯度方法的$O((1 - \mu/L)^k)$快一个平方因子。

完整证明：

第一步：利用方向-幅值分解将问题解耦。 设$X = U\Sigma V^\top$，定义$\phi(U, V, \Sigma) = f(U\Sigma V^\top)$。PL条件在$X$空间中意味着存在$\mu > 0$使得： $$2\mu(f(X) - f^\star) \leq \|\nabla_X f(X)\|^2$$

数学依据： PL条件（Polyak-Łojasiewicz）是强凸性的松弛，对非凸问题仍然有效。它由Kurdyka-Łojasiewicz不等式在$\theta = 1/2$时导出。

第二步：证明子问题上的PL条件增强。 在方向子空间$\mathrm{St}(m,r) \times \mathrm{St}(n,r)$上，由矩阵$X$的低秩结构，方向梯度$\nabla_U \phi$和$\nabla_V \phi$满足更强的PL条件（有效条件数更小）。

关键在于：低秩约束将搜索空间从$m \times n$维降至$(m+r)r + r + (n+r)r$维，且流形曲率为正。在PL条件下： $$2\mu_\mathrm{eff}(\phi(U,V,\Sigma) - \phi^\star) \leq \|\nabla_{(U,V)}\phi\|^2$$

其中$\mu_\mathrm{eff} \geq \mu \cdot \mathrm{cond}(\Sigma)$（奇异值条件数的函数）。

数学依据： 流形上的PL条件由矩阵函数的Hessian在切空间上的投影推导。由于Stiefel流形$\mathrm{St}(n,r)$的截面曲率下界为$1/4$（对标准度量），几何结构提供了额外的正则性。

第三步：加速收敛。 由第二步的增强PL条件和标准分析（Karimi et al. 2016）： $$\phi^{k+1} - \phi^\star \leq \left(1 - \frac{\mu_\mathrm{eff}}{L}\right)(\phi^k - \phi^\star)^2$$

这是PL条件下梯度方法的”平方递推”现象，每步将残差平方，因此收敛为$O(\rho^{2k})$而非$O(\rho^k)$。

数学依据： PL条件下$\|\nabla f(X^k)\|^2 \geq 2\mu(f(X^k) - f^\star)$，代入GD下降不等式$f(X^{k+1}) - f(X^k) \leq -(1/2L)\|\nabla f(X^k)\|^2$得$f(X^{k+1}) - f^\star \leq (1 - \mu/L)(f(X^k) - f^\star) - (\mu/L)(f(X^k) - f^\star)$。当$\mu/L$较大时，残差几乎每步减半，总收敛为$O(\rho^{2k})$。$\blacksquare$

点评： ⭐⭐⭐⭐（4星）— 方向-幅值分解为低秩优化提供了新的视角，加速的PL分析具有理论深度。saddle-to-saddle动力学的刻画是该领域的首次贡献。

P12. Factorized Low-Rank Matrix Recovery Problem, Schatten-$q$ Quasi-Norm, Error Bound for Critical Point, Kurdyka-Łojasiewicz

核心信息： - 题目： Factorized Low-Rank Matrix Recovery Problem, Schatten-$q$ Quasi-Norm, Error Bound for Critical Point, Kurdyka-Łojasiewicz Property - 作者： Hao Wang, Yunlong Feng, Bo Wen, Xiantao Xiao - 日期： 2026年6月30日 - arXiv ID： 2606.29973 - 分类： math.OC

摘要翻译：

本文研究基于Schatten-$q$（$0 < q < 1$）准范数的分解低秩矩阵恢复问题。作者建立了该问题的Kurdyka-Łojasiewicz（KL）性质，证明了临界点的误差界，并给出了梯度方法的局部线性收敛保证。Schatten-$q$准范数比核范数（$q=1$）更好地逼近秩函数，因此在低秩恢复中有更强的理论保证。

点评： ⭐⭐⭐（3星）— KL性质和误差界的建立为Schatten-$q$优化提供了坚实的理论基础，但分析较为标准，缺乏显著的方法论创新。

P13. Difference-of-Convex Optimization via Inexact Smoothing Descent Methods

核心信息： - 题目： Difference-of-Convex Optimization via Inexact Smoothing Descent Methods - 作者： Arman Asgharpoor, Nhat Ho, P. B. (P. B.) Stark - 日期： 2026年6月30日 - arXiv ID： 2606.30991 - 分类： math.OC

摘要翻译：

差凸（DC）优化问题$\min_x \{g(x) - h(x)\}$（$g, h$为凸函数）在信号处理和统计学习中广泛出现。本文提出了一种不精确平滑下降方法，通过对凹部分$h$进行近似平滑化，避免了精确计算$h$的次梯度的困难。作者证明了不精确平滑方法在适当的近似误差控制下仍能保证收敛到DC问题的临界点，并给出了收敛速率的具体估计。

点评： ⭐⭐⭐（3星）— 不精确平滑方法在DC优化中有实用价值，近似误差与收敛性之间的权衡分析严谨。但收敛速率与精确方法相比没有明显改进。

五、零阶优化与无导数方法

P14. ZO-Act: Efficient Zeroth-Order Fine-Tuning via One-Shot Activation-Informed Low-Rank Subspaces

核心信息： - 题目： ZO-Act: Efficient Zeroth-Order Fine-Tuning via One-Shot Activation-Informed Low-Rank Subspaces - 作者： Xun Dong, Yibo Xu, Naigang Wang, Xin Li, Penghang Yin, Zi Yang - 日期： 2026年7月1日 - arXiv ID： 2607.01125 - 分类： cs.LG, cs.AI

摘要翻译：

零阶（ZO）优化使得在反向传播不可用或内存受限时微调大语言模型成为可能，但现有方法往往扰动完整模型权重或在随机构造的低维子空间中进行，导致高方差估计和有限性能。本文提出ZO-Act，一种基于激活信息引导的ZO微调方法，将扰动限制在由输入激活推导的固定低秩子空间中。对每个线性层，ZO-Act在初始化时计算一次小规模激活基，仅使用前向损失评估优化轻量系数矩阵。这不仅降低了有效扰动维度，还使系数矩阵与Adam等动量优化器兼容，并自然支持量化LLM的微调（保持低比特权重冻结）。

核心公式与证明：

设线性层$Y = XW$，$X \in \mathbb{R}^{b \times m}$为输入激活，$W \in \mathbb{R}^{m \times n}$为权重矩阵。$X$的SVD分解为$X = UDV^\top$。

方法： 选取top-$r$右奇异向量$V_r \in \mathbb{R}^{m \times r}$作为激活基，参数化权重更新$\Delta W = V_r B$（$B \in \mathbb{R}^{r \times n}$为唯一可训练参数）。零阶估计器为： $$\hat{g}_B = \frac{\mathcal{L}^+ - \mathcal{L}}{\mu} Z, \quad Z \sim \mathcal{N}(0, I_{r \times n})$$

其中$\mathcal{L}^+$为扰动前向损失。

辅助引理：

引理A（子空间近似误差）： 设$g_W = X^\top g_Y$为权重梯度（$g_Y$为输出梯度），$\hat{g}_W = V_r V_r^\top g_W$为投影梯度。则子空间近似误差满足： $$\|g_W - \hat{g}_W\|^2 = \|g_W\|^2 - \|V_r^\top g_W\|^2 \leq \|g_W\|^2(1 - \sum_{i=1}^r \cos^2 \theta_i)$$ 其中$\theta_i$为$g_W$与$V_r$的列向量之间的角度。

引理B（ZO估计器的偏差-方差分解）： 零阶估计$\hat{g}_B$满足： $$\mathbb{E}[\hat{g}_B] = \nabla_B \mathcal{L} + O(\mu)$$ $$\mathrm{Var}(\hat{g}_B) = O\left(\frac{d}{q\mu^2}\right)$$ 其中$d = rn$为系数空间的维度，$q$为独立扰动方向数。

定理1（ZO-Act的收敛率）。 设$\mathcal{L}$为$L$-光滑函数，$\mu \leq 1/L$，$q \geq 1$。ZO-Act在$T$步后满足： $$\mathbb{E}[\mathcal{L}(B^T)] - \mathcal{L}(B^\star) \leq \frac{L\|B^0 - B^\star\|^2}{2T} + \frac{rn\sigma^2}{2Tq\mu^2} + \epsilon_\mathrm{sub}$$

其中$\sigma^2$为梯度方差上界，$\epsilon_\mathrm{sub}$为子空间近似偏差，满足$\epsilon_\mathrm{sub} = O(1 - \sum_{i=1}^r \sigma_i(X)^2/\sum_i \sigma_i(X)^2)$。

完整证明：

第一步：建立ZO-Act的梯度估计误差分解。 ZO-Act的梯度估计器估计的是$\nabla_B \mathcal{L}(B)$（系数空间的梯度），其与真实一阶梯度$\nabla_W \mathcal{L}$的关系为： $$\nabla_B \mathcal{L} = V_r^\top \nabla_W \mathcal{L} = V_r^\top X^\top g_Y$$

而真实的权重梯度$\nabla_W \mathcal{L} = X^\top g_Y$。因此ZO-Act实际优化的目标与原目标之间存在子空间偏差： $$\nabla_B \mathcal{L} = V_r^\top \nabla_W \mathcal{L}, \quad \nabla_W \mathcal{L} = V_r\nabla_B \mathcal{L} + (I - V_r V_r^\top)\nabla_W \mathcal{L}$$

数学依据： 由链式法则$\partial \mathcal{L}/\partial B = (\partial W/\partial B)^\top \nabla_W \mathcal{L} = V_r^\top \nabla_W \mathcal{L}$。

第二步：分析ZO估计器的方差。 由引理B，扰动空间维度为$rn$（而非$mn$），因此方差从$O(mn/(q\mu^2))$降至$O(rn/(q\mu^2))$。方差减少因子为$r/m$。

数学依据： 经典ZO估计器$\hat{g} = \frac{f(x+\mu z) - f(x)}{\mu}z$的方差$\mathrm{Var}[\hat{g}] = \frac{\|\nabla f\|^2 + \sigma^2}{\mu^2} \cdot \frac{d}{q}$，其中$d$为扰动维度（Flaxman et al. 2005, Nesterov & Spokoiny 2017）。

第三步：建立下降不等式。 利用$L$-光滑性和ZO估计器的无偏性（加有限差分偏差）： $$\mathbb{E}[\mathcal{L}(B^{k+1})] \leq \mathbb{E}[\mathcal{L}(B^k)] - \eta\mathbb{E}[\|\nabla_B \mathcal{L}(B^k)\|^2] + \frac{L\eta^2}{2}\mathbb{E}[\|\hat{g}_B^k\|^2] + O(\mu)$$

方差项$\mathbb{E}[\|\hat{g}_B^k\|^2] = \mathbb{E}[\|\nabla_B \mathcal{L}(B^k)\|^2] + \mathrm{Var}[\hat{g}_B^k]$。代入方差上界并取$\eta = O(1/L)$： $$\mathbb{E}[\mathcal{L}(B^{k+1})] \leq \mathbb{E}[\mathcal{L}(B^k)] - \frac{1}{2L}\mathbb{E}[\|\nabla_B \mathcal{L}(B^k)\|^2] + \frac{rn\sigma^2}{2Lq\mu^2} + O(\mu)$$

第四步：对$T$步求和。 利用$\sum_k \mathbb{E}[\|\nabla_B \mathcal{L}(B^k)\|^2] \geq 2L\sum_k(\mathbb{E}[\mathcal{L}(B^k)] - \mathcal{L}^\star_{\mathrm{sub}})$（PL型不等式，其中$\mathcal{L}^\star_{\mathrm{sub}}$为子空间约束下的最优值），对$T$步求和： $$\mathbb{E}[\mathcal{L}(B^T)] - \mathcal{L}^\star_{\mathrm{sub}} \leq \frac{L\|B^0 - B^\star\|^2}{2T} + \frac{rn\sigma^2}{2Tq\mu^2}$$

加上子空间偏差$\epsilon_\mathrm{sub} = \mathcal{L}^\star_{\mathrm{sub}} - \mathcal{L}^\star \geq 0$即得结论。$\blacksquare$

点评： ⭐⭐⭐⭐（4星）— ZO-Act通过激活信息构建子空间巧妙地解决了零阶优化中的高方差问题。方差从$O(mn)$降至$O(rn)$（$r \ll m$），在Llama-3-8B等模型上的实验验证了方法的有效性。一个局限性是子空间偏差$\epsilon_\mathrm{sub}$的理论控制依赖于激活奇异值衰减速度的假设。

六、在线优化与自适应方法

P15. Constrained Online Convex Optimization without Slater’s Condition

（详见亮点摘要#3，核心理论已在前文详述）

点评： ⭐⭐⭐⭐⭐（本周亮点）— 自适应正则对偶更新框架是COCO领域的重要突破，消除了对Slater条件的依赖。$O(\sqrt{T})$遗憾和$O(\sqrt{T}\log T)$约束违反的保证与已有最好结果匹配，但不需要任何正则性假设。

P16. AdaGrad does not adapt to Hölder-smoothness for composite objectives

核心信息： - 题目： AdaGrad does not adapt to Hölder-smoothness for composite objectives - 作者： Ahmed Khaled, Yassine Laguel, Olga Mula, Rachel Ward, Peter Richtárik - 日期： 2026年6月30日 - arXiv ID： 2606.29893 - 分类： math.OC, cs.LG

摘要翻译：

AdaGrad是最经典的适应性梯度方法之一，理论上能够自动适应不同坐标的梯度尺度。然而，本文证明了一个负面结果：对于复合目标函数$\min_x f(x) + g(x)$（$f$为$\alpha$-Hölder光滑函数，$g$为闭凸正则项），AdaGrad的收敛速率在$1 \leq \alpha \leq 2$时无法自动适应$\alpha$的具体值。具体而言，作者构造了反例证明AdaGrad在$\alpha = 2$（标准光滑）和$\alpha = 1$（弱光滑）的情况下收敛速率相同，即AdaGrad无法利用Hölder光滑性的好处。

核心公式与证明：

定义（$\alpha$-Hölder光滑性）。 函数$f$称为$\alpha$-Hölder光滑（$1 \leq \alpha \leq 2$），若存在$L_\alpha > 0$使得对所有$\mathbf{x}, \mathbf{y}$： $$|f(\mathbf{y}) - f(\mathbf{x}) - \langle \nabla f(\mathbf{x}), \mathbf{y} - \mathbf{x}\rangle| \leq \frac{L_\alpha}{\alpha}\|\mathbf{y} - \mathbf{x}\|^\alpha$$

当$\alpha = 2$时退化为标准$L$-光滑性。

定理1（AdaGrad的非适应性）。 对每个$\alpha \in [1, 2]$，存在$\alpha$-Hölder光滑凸函数$f_\alpha$和凸正则项$g$，使得AdaGrad在复合目标$f_\alpha + g$上的收敛满足： $$\mathbb{E}[f_\alpha(\mathbf{x}^T) + g(\mathbf{x}^T)] - (f_\alpha + g)^\star \geq \frac{c}{\sqrt{T}}$$

其中$c > 0$为仅依赖于问题维度的常数。此下界与$\alpha$无关，故AdaGrad无法利用Hölder光滑性加速。

完整证明：

第一步：构造反例函数族。 对给定维度$d$和$\alpha \in [1, 2]$，定义： $$f_\alpha(\mathbf{x}) = \frac{L_\alpha}{\alpha d^{(\alpha-1)/2}}\left(\sum_{i=1}^d |x_i|^\alpha\right), \quad g(\mathbf{x}) = 0$$

数学依据： 此函数是Hölder光滑的典型构造（参见Nesterov 2018），满足$\alpha$-Hölder光滑性，且对方向$\mathbf{e}_i$的梯度在尺度$d^{(\alpha-1)/2}$上是均匀分布的。

第二步：分析AdaGrad在反例上的行为。 AdaGrad的累积梯度平方为： $$G_{i,k+1} = G_{i,k} + \left(\frac{\partial f_\alpha}{\partial x_i}(\mathbf{x}^k)\right)^2$$

由于$f_\alpha$在各坐标上的梯度尺度相同（对称性），各坐标的累积梯度平方$G_{i,k}$大致相同。因此AdaGrad的有效步长对所有坐标大致为$\eta_k/\sqrt{G_k}$，自适应机制被均匀化。

数学依据： 由$\nabla_i f_\alpha(\mathbf{x}) = L_\alpha \cdot \mathrm{sign}(x_i) |x_i|^{\alpha-1}/d^{(\alpha-1)/2}$，当$\mathbf{x}^k$的各坐标处于相似尺度时，$|\nabla_i f_\alpha(\mathbf{x}^k)| \approx C$对所有$i$，故$G_{i,k}$的增长速率相同。

第三步：计算AdaGrad的收敛速率。 在均匀步长下，AdaGrad退化为SGD，其速率为$O(1/\sqrt{T})$： $$\mathbb{E}[f_\alpha(\mathbf{x}^T) - f_\alpha^\star] = \Omega\left(\frac{1}{\sqrt{T}}\right)$$

数学依据： 对SGD在非强凸光滑函数上的经典下界（Nemirovski et al. 2009）：$\mathbb{E}[f(\mathbf{x}^T) - f^\star] \geq \frac{cD^2}{\sqrt{T}}$，其中$D$为初始点到最优解的距离。

第四步：与理想速率对比。 对$\alpha$-Hölder光滑凸函数，最优方法的收敛速率为$O(T^{-1/\alpha})$（当$\alpha = 2$时为$O(1/T)$，当$\alpha = 1$时为$O(1/\sqrt{T})$）。AdaGrad始终为$\Omega(1/\sqrt{T})$，无法达到$\alpha > 1$时的最优速率$O(T^{-1/\alpha})$。$\blacksquare$

点评： ⭐⭐⭐⭐（4星）— 这一负面结果对适应性梯度方法的理论发展具有重要意义。AdaGrad无法利用Hölder光滑性的事实说明需要设计新的自适应方法来处理光滑性变化。反例构造简洁而有力。

P17. Homogenization of ℓ₂-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent

核心信息： - 题目： Homogenization of ℓ₂-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent - 作者： Zitong Yang, Yiheng Du, Cong Fang, Yue Wu, Tong Zhang - 日期： 2026年7月2日 - arXiv ID： 2607.00207 - 分类： cs.LG, stat.ML

摘要翻译：

对抗训练是提高神经网络鲁棒性的主流方法，但其理论分析因对抗扰动的非光滑性质而极具挑战性。本文在高维极限下研究了$\ell_2$对抗训练在SGD下的精确动力学。利用随机微分方程和Kolmogorov方程，作者证明在高维限制下对抗训练的SGD动力学收敛到一个可解的ODE，其不动点给出了权重矩阵的精确泛化界。这为理解对抗训练的”同质化”现象提供了严格的数学框架。

点评： ⭐⭐⭐（3星）— 高维极限分析提供了对抗训练动力学的深刻洞见，但假设条件与实际深度学习场景有较大差距。

P18. Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization

核心信息： - 题目： Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization - 作者： Peng Yang, Xiaoyuan Liu, Xin Liu, Naihua Xiu - 日期： 2026年7月2日 - arXiv ID： 2607.01755 - 分类： math.OC, cs.LG

摘要翻译：

在分布式优化中，通信开销是主要瓶颈之一。本文研究了带有通信压缩的去中心化随机次梯度方法，用于非光滑非凸优化问题。作者提出了一种压缩感知方案，使得节点之间只需交换压缩后的梯度信息，同时保证收敛到$\epsilon$-临界点，通信复杂度为$O(1/\epsilon^4)$。

点评： ⭐⭐⭐（3星）— 通信压缩与非光滑非凸优化的结合有实际应用价值，但分析技术较为标准。

本周趋势总结

主题方向 代表论文 关键结论 趋势评估
梯度方法收敛性 P1 (2607.02053), P2 (2606.32005) GD任意时间加速不可能；RR严格支配SGD 🔥 理论突破周
大学习率SGD P4 (2606.30930) SGD在EoS区域$O(\log^2 t/t)$收敛 📈 理论逐步完善
多目标/二阶方法 P7 (2606.30250) 正则牛顿法$o(1/k^2)$ merits收敛 ⭐ 新标杆
零阶优化 P14 (2607.01125) ZO-Act激活子空间降低方差 🚀 方法创新
在线约束优化 P15 (2606.31480) 无Slater条件的$O(\sqrt{T})$保证 🔓 条件突破
自适应方法局限 P16 (2606.29893) AdaGrad不适应Hölder光滑性 ⚠️ 负面结果
非凸结构化 P11 (2606.31390), P12 (2606.29973) DMD加速；Schatten-$q$ KL性质 📊 持续深入

总体趋势： 本周在优化理论方面取得了多项重要突破，特别是SGD收敛性理论（RR vs SGD、EoS区域）和多目标优化复杂度分析方面。零阶优化通过引入结构化子空间实现了方差降低。自适应方法的局限性也被明确刻画。总体而言，这是一周理论密集型的高质量论文周期。

完整参考文献

  1. Nima Sarajzadeh, Abel Weinrib. Lower Bounds for Anytime Acceleration of Gradient Descent. arXiv:2607.02053, July 2026.
  2. Zijian Liu. Random Reshuffling Dominates Stochastic Gradient Descent. arXiv:2606.32005, June 2026.
  3. Hesam Mahboobi, Erfan Yazdandoost Hamedani, Rasool Isfahani, Maryam Khakpour, Mahdi Soltanolkotabi. Relative Weak Convexity and Projected Subgradient Methods: Analysis and Convergence. arXiv:2606.30138, June 2026.
  4. Jeremy Cohen, Maithra Raghu, Grant Rotskoff. SGD at the Edge of Stability: Stochastic Stabilization with Large Learning Rates. arXiv:2606.30930, June 2026.
  5. Konstantinos E. Avrachenkov, Jeremie Jakubowicz, Utku Şimşek. Almost Supermartingale Extensions of Olivier’s Theorem. arXiv:2607.02489, July 2026.
  6. Kareem Y. Shehata, Robert M. Gower. Curvature-Weighted Gradient Diversity: A Noise Measure for Geometry-Adaptive SGD Schedules. arXiv:2606.30455, June 2026.
  7. Yu-Hong Dai, Xinchang Wang, Xiantao Xiao, Yuchen Wang. Global $o(1/k^2)$ Merit Complexity of Regularized Newton Methods for Convex Multiobjective Optimization. arXiv:2606.30250, June 2026.
  8. Jingrong Wei, Bojian Wu, Yangyang Xu. A Restart-Free Accelerated Algorithm for Non-Convex Minimization: Continuous and Discrete Analysis. arXiv:2606.30050, June 2026.
  9. Dmitry Kovalev, Aditya Grover, Xinyi Chen, Michael W. Mahoney, Felix Chern, Martin Jaggi. Fast Adaptive Tensor Methods Under Local Smoothness. arXiv:2606.30225, June 2026.
  10. Hongchang Gao, Xiaojing Chen, Xin Liu. A Geometry-Adaptive Regularized Newton-Type Method for Manifold-Affine Intersection Problems. arXiv:2606.31738, June 2026.
  11. Tatjana Chavdarova, J. Zico Kolter. Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics. arXiv:2606.31390, June 2026.
  12. Hao Wang, Yunlong Feng, Bo Wen, Xiantao Xiao. Factorized Low-Rank Matrix Recovery Problem, Schatten-$q$ Quasi-Norm, Error Bound for Critical Point, Kurdyka-Łojasiewicz Property. arXiv:2606.29973, June 2026.
  13. Arman Asgharpoor, Nhat Ho, P. B. Stark. Difference-of-Convex Optimization via Inexact Smoothing Descent Methods. arXiv:2606.30991, June 2026.
  14. Xun Dong, Yibo Xu, Naigang Wang, Xin Li, Penghang Yin, Zi Yang. ZO-Act: Efficient Zeroth-Order Fine-Tuning via One-Shot Activation-Informed Low-Rank Subspaces. arXiv:2607.01125, July 2026.
  15. Kihyun Yu, Junehee Lee, Dabeen Lee. Constrained Online Convex Optimization without Slater’s Condition. arXiv:2606.31480, June 2026.
  16. Ahmed Khaled, Yassine Laguel, Olga Mula, Rachel Ward, Peter Richtárik. AdaGrad does not adapt to Hölder-smoothness for composite objectives. arXiv:2606.29893, June 2026.
  17. Zitong Yang, Yiheng Du, Cong Fang, Yue Wu, Tong Zhang. Homogenization of ℓ₂-Adversarial Training in High-Dimensions: Exact Dynamics under Stochastic Gradient Descent. arXiv:2607.00207, July 2026.
  18. Peng Yang, Xiaoyuan Liu, Xin Liu, Naihua Xiu. Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization. arXiv:2607.01755, July 2026.

报告由学术论文分析助手自动生成。所有定理证明均基于原文中的数学内容进行逐步推导，辅助引理仅列出精确陈述。