Universal Adaptive Proximal Gradient Methods via Gradient Mapping Accumulation¶

会议: NeurIPS 2026
arXiv: 2605.05944
论文: https://arxiv.org/abs/2605.05944
领域: 优化/理论
关键词: 近端梯度法, 自适应步长, 梯度映射, 复合优化, 凸加速算法

一句话总结¶

论文针对包含非光滑正则项的复合优化问题，提出了一种基于历史梯度映射范数累加的通用自适应近端梯度算法（以及针对凸问题的加速变体），在无需任何问题先验参数的前提下，统一在非凸光滑、凸非光滑与凸光滑三类函数上自适应达到匹配近端梯度法的最优或近最优收敛速率。

研究背景与动机¶

复合优化问题目标函数形如 $\min_{x \in \mathbb{R}^d} F(x) := f(x) + h(x)$，其中 $f$ 为可微或不可微的损失函数，而 $h$ 是可能非光滑但简单的凸正则项（例如 LASSO 的 $\ell_1$ 范数、SVM 或盒约束的指示函数）。解决此类问题最基础的算法是近端梯度法（Proximal Gradient, PG），但经典 PG 的理论与实践严重依赖对问题类别的先验认知和关键超参数的精确调校：若 $f$ 为 $L$-光滑，步长必须受限于常数级 $1/L$；若 $f$ 为凸且 $G$-Lipschitz 连续，步长则需按 $\mathcal{O}(1/\sqrt{k})$ 衰减；而在随机优化场景中，噪声方差 $\sigma$ 与计算域直径 $D$ 更使得手动调节步长极为繁琐且缺乏鲁棒性。

在无复合项的标准优化（$h=0$）中，AdaGrad 及其衍生算法开创了自适应步长范式，通过在步长分母累加历史梯度平方范数 $\sum_{j=1}^k \|\nabla f(x_j)\|^2$ 实现了无需先验调参的“通用性（universality）”——在光滑目标上梯度逐渐消失使分母增长缓慢，步长保持相对恒定；在非光滑目标上梯度范数有下界，步长自动呈现 $\mathcal{O}(1/\sqrt{k})$ 衰减。然而，这一经典机制无法直接迁移到复合优化场景。其核心症结在于：由于非光滑项 $h$ 的存在，复合问题驻点 $x^*$ 处的梯度 $\nabla f(x^*)$ 通常非零，一阶最优性条件仅要求 $-\nabla f(x^*) \in \partial h(x^*)$。若在分母机械累加 $\|\nabla f(x_k)\|^2$，即便是最平滑的凸函数，步长也会被强制衰减至零，彻底丧失理论收敛性与实践效率。

解决这一困境的关键在于重新审视复合优化的“进展度量”。复合优化中真正的驻点判据不是无约束梯度，而是梯度映射 $\mathcal{G}_{\eta}(x) := \frac{1}{\eta}(x - \operatorname{prox}_{\eta h}(x - \eta \nabla f(x)))$，其在且仅在一阶驻点处恒等于零，且可直接由近端迭代差 $(x_k - x_{k+1})/\eta_k$ 无额外开销获取。核心 idea：以梯度映射累加范数取代传统梯度的历史模长作为自适应步长分母，构建全自动匹配非凸光滑、凸非光滑和凸光滑三类问题最优速率的通用近端梯度法，并结合单步与序列解耦技术破解随机噪声与自适应随机步长的耦合难题。

方法详解¶

整体框架¶

本文针对复合优化问题 $\min_{x \in \mathbb{R}^d} f(x) + h(x)$，设计了通用自适应近端梯度算法（Algorithm 1）及其在已知直径假设下的凸加速变体（Algorithm 2）。算法的核心输入为初始点 $x_1 \in \operatorname{dom}(h)$ 与正标量 $\gamma, \eta > 0$。在每轮迭代中，算法基于当前（全量或随机）梯度执行近端步，并利用实际步长与迭代差构造的梯度映射动态更新累加和标量 $S_{k+1}$，进而自适应调整下一轮的近端步长。

方法的整体计算与更新流程如下所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入: 初始点 x₁ ∈ dom(h), 超参数 γ, η > 0"] --> B["梯度计算<br/>全量梯度 ∇f(x_k) 或小批量随机梯度 g_k"]
    B --> C["近端步更新<br/>求解 prox_h 获得候选点 x_{k+1}"]
    C --> D["梯度映射估计<br/>提取等价映射 G̃_k = (x_k - x_{k+1}) / η_k"]
    D --> E["梯度映射平方累加<br/>更新 S_{k+1}² = S_k² + ||G̃_k||²"]
    E --> F["自适应步长调整<br/>计算下轮步长 η_{k+1} = η / S_{k+1}"]
    F -->|继续迭代| B

关键设计¶

1. 梯度映射范数累加步长：解决复合项导致的梯度非零困境

传统 AdaGrad 步长在复合优化中失效的根本原因在于驻点处无约束梯度范数不为零。本文的关键设计是使用梯度映射替代梯度范数构造步长分母。对于近端步更新： $$x_{k+1} = \operatorname{prox}_{\eta_k h}(x_k - \eta_k g_k) = \arg\min_{x \in \mathbb{R}^d} \Big\{ \langle g_k, x \rangle + \frac{S_k}{2\eta} \|x - x_k\|^2 + h(x) \Big\}$$ 其对应的离散梯度映射显式等于 $\widetilde{\mathcal{G}}_k = \frac{1}{\eta_k}(x_k - x_{k+1})$。算法定义分母累加标量为： $$S_k^2 = \gamma^2 + \sum_{j=1}^{k-1} \|\widetilde{\mathcal{G}}_j\|^2, \quad \eta_k = \frac{\eta}{S_k}$$ 注意到在计算 $x_{k+1}$ 时 $\widetilde{\mathcal{G}}_k$ 尚未生成，因此累加只计入至第 $k-1$ 步，通过代数等价关系 $S_{k+1}^2 = S_k^2(1 + \|x_{k+1}-x_k\|^2/\eta^2)$ 递推更新。这保证了在光滑目标趋近驻点时，$\|\widetilde{\mathcal{G}}_k\| \to 0$ 使得分母趋于常数，保留了类似于 $1/L$ 的常数步长机制；而在非光滑目标上，梯度映射范数保持有界不为零，分母自适应呈现 $\mathcal{O}(\sqrt{k})$ 增长，自动匹配 $\mathcal{O}(1/\sqrt{k})$ 衰减速率。

2. 随机噪声累积内积解耦：克服随机自适应步长的强耦合与几乎必然有界假设

在随机优化设定中，$g_k = \frac{1}{b_k} \sum_{j=1}^{b_k} \nabla \ell(x_k; \xi_{k_j})$ 具有方差 $\mathbb{E}_k[\|\delta_k\|^2] \le \sigma^2/b_k$（其中 $\delta_k = \nabla f(x_k) - g_k$）。此时步长 $\eta_k = \eta/S_k$ 自身成为随机变量，与历史信息深度纠缠，传统分析中期望项 $\mathbb{E}[\sum (1/\eta_k - 1/\eta_{k-1})\Delta_k]$ 极难处理，现有文献常被迫引入“随机梯度几乎必然一致有界”这一严苛假设。本文绕开复杂的代理步长构造，直接对随机噪声与迭代差的内积进行柯西-施瓦茨和简森不等式紧致估计： $$\mathbb{E}\Big[\sum_{k=1}^t \langle \delta_k, x_{k+1} - x_k \rangle\Big] \le \sigma \sqrt{2(\eta^2 + D^2) \sum_{k=1}^t \frac{1}{b_k}} \sqrt{\log \mathbb{E}\Big[\frac{S_{t+1}}{\gamma}\Big]}$$ 该引理在无需假定随机梯度一致有界的条件下，将自适应步长累积项与有界方差统一解耦，成为统一证明非凸光滑高概率界、凸非光滑次优间隔与凸光滑预期速率的核心理论枢纽。

3. 基于外推与动量的凸加速架构：在已知直径下实现双制度近最优加速

针对凸函数情形，为消除传统加权平均点 $\bar{x}_t$ 在实际计算中的额外维护负担并追求更优收敛率，本文在已知点列界 $D$（满足 $\|z_{k+1}-z_k\| \le D$）的前提下提出了融合 AC-SA 与自适应近端映射的 Algorithm 2。算法维护三组点列：外推点 $x_k$、主更新点 $y_k$ 和辅助迭代点 $z_k$。权重由斐波那契风格的一元二次方程递推更新： $$\alpha_k = \frac{1 + \sqrt{1 + 4\alpha_{k-1}^2}}{2}, \quad \theta_k = \frac{1}{\alpha_k}, \quad x_k = (1 - \theta_k)y_k + \theta_k z_k$$ 辅助点 $z_{k+1}$ 执行缩放步长的近端更新，并将步长累加器定义在辅助映射差 $\widetilde{\mathcal{G}}_{z,k} = (z_k - z_{k+1})/\eta_k$ 上。当指定超参数满足 $\eta > \frac{\sqrt{2}}{2}D$ 时，该算法对非光滑凸问题保持 $\widetilde{\mathcal{O}}((1+\sigma)/\sqrt{t})$，而对光滑凸问题将收敛速率一举加速至 $\widetilde{\mathcal{O}}(1/t^2 + \sigma/\sqrt{t})$（确定性下达到精确最优 $\mathcal{O}(1/t^2)$），且直接在最后迭代点 $y_{t+1}$ 上达成。

损失函数 / 训练策略¶

算法包含确定性与小批量随机两种模式。在随机非凸设定下，由于单样本单位批次仅能保证收敛至驻点领域，推荐采用递增批量策略 $b_k = \Omega(\sigma \sqrt{k})$，从而消除残留方差项，恢复至 $\widetilde{\mathcal{O}}(1/t + \sigma/\sqrt{t})$ 的高概率驻点收敛。超参数设置具备极强鲁棒性，基准设定只需取 $\gamma=1$ 及 $\eta \in [1, 10]$ 即可在各类任务中平稳收敛。

实验关键数据¶

主实验¶

论文在确定性与随机场景下对非凸与凸复合优化问题展开数值验证。在 MNIST 二分类非凸 SVM（含 $\ell_1$ 正则化与 $[-50, 50]^d$ 盒约束）以及 w6a 凸正则化逻辑回归问题上，对比了通用自适应方法（Algorithm 1、Algorithm 2）与定步长近端梯度法（PG）的收敛表现：

任务 / 问题类别	数据集	算法	步长 / 超参数配置	驻点范数 $\\|\mathcal{G}(x)\\|$ / 目标间隙	收敛稳定性与特性
非凸 SVM (复合非凸光滑)	MNIST ($d=780$)	PG (基线)	$\eta_k = 10/L$	发散 (Diverged)	步长过大导致振荡发散
非凸 SVM (复合非凸光滑)	MNIST ($d=780$)	PG (基线)	$\eta_k = 1/L$	稳步收敛至驻点	需精确知晓光滑常数 $L$
非凸 SVM (复合非凸光滑)	MNIST ($d=780$)	Algorithm 1 (本文)	$\gamma=1, \eta \in \{1, 10, 100\}$	快速稳健收敛至 $\approx 10^{-4}$	免调参，跨越 2 个数量级均鲁棒
非凸 SVM (复合非凸光滑)	MNIST ($d=780$)	Algorithm 2 (加速变体)	$\gamma=1, \eta \in \{1, 10, 100\}$	缓慢衰减	凸动量在非凸场景出现减速
凸逻辑回归 (复合凸光滑)	w6a ($d=300$)	Algorithm 1 (本文)	$\gamma=1, \eta \in \{0.1, 1, 10, 100\}$	平均点稳健收敛至最优解	平均点收敛稳定，最后点随 $\eta$ 振荡
凸逻辑回归 (复合凸光滑)	w6a ($d=300$)	Algorithm 2 (本文)	$\gamma=1, \eta \in \{0.1, 1, 10, 100\}$	最后点与平均点均达近最优	双指标均实现加速收敛，优于 Alg 1

消融实验¶

论文在 a9a 数据集上深入消融了批大小（Batch Size）对 Algorithm 1 随机非凸优化动力学的影响（固定 1000 个全数据 pass / epoch 等效梯度计算量，$\gamma=1, \eta=10$）：

批大小比例 $b$ (% of 训练集)	梯度计算规模 $b_k$	驻点映射范数收敛速度 (按 Epoch)	训练早期测试集精度上升速度	优化与泛化权衡说明
$b = 0.1\%$	~32 样本/批	较慢，方差波动明显	最快（首轮迅速跃升）	小批量引入随机扰动，逃离局部极小与快速探索泛化
$b = 1.0\%$	~325 样本/批	中等	次快	较均衡的折中配置
$b = 10\%$	~3,256 样本/批	较快	中等	方差显著降低，稳定优化
$b = 50\%$	~16,280 样本/批	迅速	较慢	单次近端步精确度高但样本重用率低
$b = 100\%$ (全量)	32,561 样本/批	最快，单调平滑下降	最慢	纯确定性梯度下降，严格验证理论收敛界

在非复合（$\lambda=0$）基准下对比 UnixGrad 与 AcceleGrad（connect4 数据集）：Algorithm 2 与 AcceleGrad 在最后迭代点与测试精度上并驾齐驱，而 UnixGrad 最后迭代点震荡极为剧烈；Algorithm 1 虽初期收敛稍慢，但全程单调稳定。

关键发现¶

步长宽容度极高：Algorithm 1 与 Algorithm 2 在超参数 $\eta$ 跨越 $10^{-1}$ 到 $10^2$ 的千倍区间内均保持平稳收敛，彻底免除了对未知常数 $L$ 的网格搜索。
动量机制的非凸局限性：实验清晰验证了理论注记（Remark 2）——当目标为非凸时，Algorithm 2 的动量累加项会导致有效步长过度衰减为 $\mathcal{O}(1/t)$，致使其梯度映射衰减明显慢于无动量的 Algorithm 1。
平均点 vs 最后点特性解耦：Algorithm 1 必须依靠遍历平均点 $\bar{x}_t$ 平抑步长波动；而 Algorithm 2 凭借多阶段外推机制，直接赋予了最后迭代点 $y_{t+1}$ 极强的一致最优收敛性。

亮点与洞察¶

指标对齐机制设计：跳出无约束梯度范数累加的思维惯性，将近端算法内在的“梯度映射”定义为度量基准，巧妙消除了复合非光滑边界处的非零梯度残差。
随机内积解析工具创新：提出的 Lemma 7 与 Lemma 10 构建了控制随机噪声与自适应步长耦合的一体化分析范式，摆脱了以往同类理论必须依赖“几乎必然有界梯度”的不切实际假设。
跨三类问题真通用性：同一个算法单套代码，在无需提供问题属性开关的情况下，数学上自适应在非凸光滑、凸非光滑和凸光滑上同时达到理论最优阶。

局限与展望¶

对数因子残留：理论收敛界中附带的 $\log t$ 或 $\log(1+\sigma t)$ 因子源于对分母累积增长的保守放大，未来有待探寻更紧致的鞅差界或修正步长结构予以消除。
全局统一加速的缺失：目前带有加速速率的 Algorithm 2 依赖直径 $D$ 的先验知识，且无法良好泛化到非凸光滑问题；设计一个同时在三类问题上均自适应且具备加速最优率的真正统一算法仍是有待攻克的开放难题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [将梯度映射累加巧妙融入自适应步长分母，首次解决复合非凸优化自适应步长通用收敛]
实验充分度: ⭐⭐⭐⭐☆ [覆盖经典非凸 SVM 与逻辑回归主实验及多项基准消融，理论与实验结论高度呼应]
写作质量: ⭐⭐⭐⭐⭐ [数学推导严密精巧，引理设计层次清晰，概念动机交代极为透彻]
价值: ⭐⭐⭐⭐⭐ [为复合结构的大规模一阶优化提供了免调参、带严谨收敛保证的通用算法基础]

任务 / 问题类别	数据集	算法	步长 / 超参数配置	驻点范数 \(\\|\mathcal{G}(x)\\|\) / 目标间隙	收敛稳定性与特性
非凸 SVM (复合非凸光滑)	MNIST (\(d=780\))	PG (基线)	\(\eta_k = 10/L\)	发散 (Diverged)	步长过大导致振荡发散
非凸 SVM (复合非凸光滑)	MNIST (\(d=780\))	PG (基线)	\(\eta_k = 1/L\)	稳步收敛至驻点	需精确知晓光滑常数 \(L\)
非凸 SVM (复合非凸光滑)	MNIST (\(d=780\))	Algorithm 1 (本文)	\(\gamma=1, \eta \in \{1, 10, 100\}\)	快速稳健收敛至 \(\approx 10^{-4}\)	免调参，跨越 2 个数量级均鲁棒
非凸 SVM (复合非凸光滑)	MNIST (\(d=780\))	Algorithm 2 (加速变体)	\(\gamma=1, \eta \in \{1, 10, 100\}\)	缓慢衰减	凸动量在非凸场景出现减速
凸逻辑回归 (复合凸光滑)	w6a (\(d=300\))	Algorithm 1 (本文)	\(\gamma=1, \eta \in \{0.1, 1, 10, 100\}\)	平均点稳健收敛至最优解	平均点收敛稳定，最后点随 \(\eta\) 振荡
凸逻辑回归 (复合凸光滑)	w6a (\(d=300\))	Algorithm 2 (本文)	\(\gamma=1, \eta \in \{0.1, 1, 10, 100\}\)	最后点与平均点均达近最优	双指标均实现加速收敛，优于 Alg 1

批大小比例 \(b\) (% of 训练集)	梯度计算规模 \(b_k\)	驻点映射范数收敛速度 (按 Epoch)	训练早期测试集精度上升速度	优化与泛化权衡说明
\(b = 0.1\%\)	~32 样本/批	较慢，方差波动明显	最快（首轮迅速跃升）	小批量引入随机扰动，逃离局部极小与快速探索泛化
\(b = 1.0\%\)	~325 样本/批	中等	次快	较均衡的折中配置
\(b = 10\%\)	~3,256 样本/批	较快	中等	方差显著降低，稳定优化
\(b = 50\%\)	~16,280 样本/批	迅速	较慢	单次近端步精确度高但样本重用率低
\(b = 100\%\) (全量)	32,561 样本/批	最快，单调平滑下降	最慢	纯确定性梯度下降，严格验证理论收敛界