Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities¶

会议: NeurIPS 2026
arXiv: 2603.29128
OpenReview: https://openreview.net/forum?id=jIJ566xVDK
代码: https://github.com/Yee-Millennium/ADUCA
领域: 优化/理论
关键词: 循环块坐标法, 变分不等式, 自适应步长, 延迟更新, 无参数优化

一句话总结¶

针对单调 Lipschitz 算子的广义 Minty 变分不等式，本文提出了首个无需全量或块 Lipschitz 常数且无逐轮线搜索的自适应循环块坐标算法 ADUCA，利用整轮延迟算子信息解除块间严格同步约束，并达到最优 $\mathcal{O}(1/\epsilon)$ 或强单调下 $\mathcal{O}(\log^2(1/\epsilon))$ 的预言机复杂度。

研究背景与动机¶

循环块坐标方法（Cyclic block coordinate methods）在数值分析和大规模优化中历史悠久，因其结构简单、缓存局部性优异而在矩阵平衡、广义线性模型求解等工业级软件包中被广泛采用。然而，循环更新在理论分析上极具挑战性：与随机坐标下降或全向量更新相比，循环方法依赖于确定性的扫描顺序，步长选取极其严苛。在凸最小化之外的极小化极大博弈（min-max optimization）与一般单调变分不等式（Variational Inequalities, VI）中，经典的确切循环下降不仅可能无法收敛，且必须依赖精确的全局 Lipschitz 模数或高开销的逐轮回溯线搜索（backtracking line search）。

这种限制的核心矛盾在于：变分不等式中的坐标块更新会导致跨块误差的非对称累积，为了保证收敛，现有方法（如 CODER）要么要求预先获知基于马氏半范数的全局块 Lipschitz 常数矩阵，要么在每一轮外层循环中执行多次昂贵的算子全量回溯求值；而现有的免线搜索自适应算法（如 GRAAL 或 AdaGrad 变体）仅支持全向量更新或仅支持单调递减步长，无法在局部平坦区域放大步长，更无法适应块坐标的串行结构与弱同步并行需求。

本文的切入角度是：将外推算子信息解耦并引入一整轮的延迟（Delayed-Update），结合跨步与块内两套局部曲率感知代理量，构造出纯显式的自适应步长准则。核心 idea：设计一种延迟一整轮算子更新的外推循环块坐标算法 ADUCA，通过局部双重 Lipschitz 变动比自适应调控循环步长，彻底摆脱线搜索与全局参数依赖，并在弱同步与并行环境下达到近最优的预言机收敛界。

方法详解¶

整体框架¶

ADUCA 针对广义 Minty 变分不等式 $\langle \bm{F}(\mathbf{u}), \mathbf{u} - \mathbf{u}^*\rangle + g(\mathbf{u}) - g(\mathbf{u}^*) \geq 0$ 设计，其中单调算子 $\bm{F}$ 满足局部块 Lipschitz 连续性，正则项 $g(\mathbf{u}) = \sum_{i=1}^m g^i(\mathbf{u}^i)$ 为块可分离的近端友好凸函数。算法在每一大轮 $k$ 开始时，先根据前序轮次落盘的局部变动自适应计算该大轮的标量步长 $a_k$；随后在轮内对各个坐标块 $i \in [m]$ 依次执行外推延迟算子构造、近端中心插值以及近端算子更新；最后在各块更新完成后，收集延迟算子分量作为下一轮的历史信息。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：初始点 u0、对角缩放矩阵 Λ、超参数 β, γ, ρ"] --> B["一次性回溯初始化<br/>确定初始步长 a0 ≤ 1/(√2 L1)"]
    B --> C["双重局部 Lipschitz 估计与步长更新<br/>计算 Lk 与 L^k，显式确定大轮步长 ak"]
    C --> D["循环延迟算子外推<br/>结合前一轮延迟算子差分更新 F̄k^i"]
    D --> E["近端中心几何外推<br/>对坐标块构造 vk^i = (1-β) uk^i + β vk-1^i"]
    E --> F["块近端最小化更新<br/>求解坐标块 uk+1^i 并收集延迟算子分量 F̃k+1^i"]
    F -->|满足终止条件| G["加权遍历输出 ûK 或末点 vK+1"]
    F -->|继续下一轮迭代| C

关键设计¶

1. 双重局部 Lipschitz 估计与步长更新：免线搜索的局部几何感知 传统单调变分不等式自适应方法往往只监控整步迭代前后的算子变化，无法捕捉循环更新中各坐标块相继改变所引入的阶段性偏差。ADUCA 在每个周期 $k$ 构造两个相互补充的局部 Lipschitz 代理量 $L_k$ 与 $\hat{L}_k$： $$L_k := \frac{\|\bm{F}(\mathbf{u}_k) - \bm{F}(\mathbf{u}_{k-1})\|_{\bm{\Lambda}^{-1}}}{\|\mathbf{u}_k - \mathbf{u}_{k-1}\|_{\bm{\Lambda}}}, \quad \hat{L}_k := \frac{\|\bm{F}(\mathbf{u}_k) - \tilde{\bm{F}}_k\|_{\bm{\Lambda}^{-1}}}{\|\mathbf{u}_k - \mathbf{u}_{k-1}\|_{\bm{\Lambda}}}$$ 其中 $L_k$ 刻画全量算子在相邻迭代点之间的标准局部变动，而 $\hat{L}_k$ 刻画全算子与循环延迟算子 $\tilde{\bm{F}}_k$ 之间的偏差，在理论上精确对应于块马氏半范数累积矩阵 $\hat{L} := \|\bm{\Lambda}^{-1/2} (\sum_{i=1}^m \widehat{\bm{Q}}_\mathcal{C}^i) \bm{\Lambda}^{-1/2}\|^{1/2}$ 的局部下界。步长选取准则通过约束 $a_k \leq \min\{\rho_0 a_{k-1}, \frac{\eta}{2\sqrt{\beta}} \min\{\frac{\sqrt{\tau}\rho\beta}{\sqrt{3}L_k\sqrt{1+\rho\beta}}, \frac{\sqrt{(1-\tau)\rho\beta}}{\sqrt{2}\hat{L}_k}\} \sqrt{a_{k-1}/a_{k-2}}\}$，使步长能够随局部曲率平缓自适应增大，同时严格制约四个连续周期内差分能量的累积，消除了逐轮线搜索的需求。

2. 循环延迟算子外推：解耦坐标依赖与支持弱同步并行 在常规的高斯-赛德尔（Gauss-Seidel）循环更新中，计算当前块需要的算子必须依赖本轮最新更新的其他块，造成强烈的时序同步依赖。ADUCA 巧妙地在第 $k$ 轮的第 $i$ 个块中采用滞后整整一个循环周期的算子值 $\tilde{\bm{F}}_k^i := \bm{F}^i(\mathbf{u}_k^1, \dots, \mathbf{u}_k^{i-1}, \mathbf{u}_{k-1}^i, \dots, \mathbf{u}_{k-1}^m)$，并构造外推算子： $$\bar{\bm{F}}_k^i = \tilde{\bm{F}}_k^i + \frac{a_{k-1}\omega_{k-1}}{a_k} \big(\bm{F}^i(\mathbf{u}_{k-1}) - \tilde{\bm{F}}_{k-1}^i\big)$$ 这一机制的深层妙处在于：计算外推量所依赖的全部历史算子在第 $k$ 周期开始时已经完全就绪，步长 $a_k$ 在周期之初即可一次性解析解出，无需在块更新循环内部反悔或试探。在分布式与多线程实现中，延迟机制允许通信与本地计算高度重叠，弱化了分布式节点之间的硬性屏障同步（barrier synchronization）。

3. 近端中心几何外推：吸收四阶历史差分误差 在目标值更新层面，为了抵消算子延迟和循环异步带来的负面动量，算法维护了由参数 $\beta \in (\frac{\sqrt{5}-1}{2}, 1)$ 驱动的近端中心序列 $\mathbf{v}_k^i = (1-\beta)\mathbf{u}_k^i + \beta \mathbf{v}_{k-1}^i$。新迭代块的近端更新目标由以下子问题给出： $$\mathbf{u}_{k+1}^i = \arg\min_{\mathbf{u}^i} \Big\{ a_k \langle \bar{\bm{F}}_k^i, \mathbf{u}^i \rangle + a_k g^i(\mathbf{u}^i) + \frac{1}{2}\|\mathbf{u}^i - \mathbf{v}_k^i\|_{\bm{\Lambda}_i}^2 \Big\}$$ 与经典单步近端不同，该几何外推项在势能函数中提供了带负权重的位移阻尼，使得理论分析中由 $\bar{\bm{F}}_k$ 引起的跨轮内积误差能够被分解为跨越连续四个迭代点 $\|\mathbf{u}_{k+1} - \mathbf{u}_k\|_{\bm{\Lambda}}^2$ 至 $\|\mathbf{u}_{k-2} - \mathbf{u}_{k-3}\|_{\bm{\Lambda}}^2$ 的递推差分形式，并通过配凑系数实现完全伸缩相消（telescoping），从而确立全局收敛性。

损失函数 / 训练策略¶

算法初始阶段调用一次性回溯初始化子程序（算法 5.1）：从试探步长 $a_{\text{start}} = \min\{C/L_1, \hat{C}/\hat{L}_1\}$ 开始以折半方式回溯，直至满足 $a_0 \leq \frac{1}{\sqrt{2}L_1}$。该初始化在对数开销 $\mathcal{O}(\log(s_{\text{pr}}/s_\infty))$ 次算子调用内必然终止。对于强凸模数 $\mu \geq 0$，算法通过衰减因子 $\omega_k = \frac{1+\rho\beta\mu a_k}{1+\mu a_k}$ 动态维护遍历权重 $\theta_k = \theta_{k-1}/\omega_{k-1}$。在消融分析与实践中，直接保守设定 $\mu = 0$（即 $\omega_k \equiv 1$）亦能保持算法收敛特性且运行表现几乎无损。

实验关键数据¶

主实验¶

论文在 LibSVM 标准数据集（a9a、gisette、SUSY-test）上评测了带有弹性网络正则项的非光滑支撑向量机 Min-Max 对偶问题（公式 SVM，其中 $g$ 包含 $\ell_1$、$\ell_2^2$ 正则及盒约束指示函数）。对比方法包括：基线近端循环坐标法（PCCM）、首个具理论保障的循环双对偶外推法（CODER）、逐轮带线搜索的无参数变体（CODER-LineSearch）以及全向量局部自适应金分割算法（GRAAL）。

数据集	维度 $(d \times n)$	PCCM 状态	CODER / CODER-LineSearch 表现	GRAAL 收敛特性	ADUCA（本文）表现
a9a	$123 \times 32,561$	收敛振荡缓慢	稳步下降但受线搜索额外算子开销拖累	较快达到平稳	全程最优，在相同数据扫描遍数下原始间隙 $f(\mathbf{x})-f^*$ 最快降至 $10^{-6}$ 以下
gisette	$5,000 \times 6,000$	进展缓慢	随数据遍数缓慢收敛	在重新对角缩放后性能显著退化	收敛速度显著优于其他所有方法，算子估计紧凑稳定
SUSY-test	$18 \times 5,000,000$	易停滞	线性稳定下降	达到一定精度后收敛放缓	始终保持最陡峭的下降曲线，显著节省有效算子评估次数

在图 1 的局部 Lipschitz 估计对比中，全局 Lipschitz 常数 $L$ 与 CODER 的马氏范数常数 $\hat{L}$ 往往高达 $10^1 \sim 10^3$，而 ADUCA 估算的 $L_k$ 与 $\hat{L}_k$ 紧贴局部几何曲率（通常在 $10^{-2} \sim 10^{-1}$ 量级），从根本上解释了其能够采用更大有效步长快速推进的原因。

消融实验¶

论文在三种超参数组合与三类数据集上系统研究了强单调先验参数 $\mu$ 对 ADUCA 收敛行为的影响（图 3）：

超参数配置 $(\beta, \rho, \gamma)$	测试数据集	选取的 $\mu$ 范围	原始目标次优性收敛轨迹差异	核心结论
$\beta=0.7, \rho=1.3, \gamma=0.05$	a9a / gisette / SUSY	$\mu \in [0, 10^{-2}]$	多条 $\mu$ 曲线完全重叠，肉眼不可分	对 $\mu$ 的取值高度鲁棒
$\beta=0.8, \rho=1.2, \gamma=0.2$	a9a / gisette / SUSY	$\mu \in [0, 10^{-2}]$	下降斜率在 $\mu=0$ 与 $\mu>0$ 时严格一致	实践中可直接安全置 $\mu=0$
$\beta=0.9, \rho=1.1, \gamma=0.3$	a9a / gisette / SUSY	$\mu \in [0, 10^{-2}]$	各数据集上收敛历程曲线重合度 $>99\%$	强凸模数仅作为理论分析工具，不构成实际算法超参敏感点

关键发现¶

局部自适应步长相比全局保守常数的巨大红利：ADUCA 构造的双重估计量 $L_k$ 与 $\hat{L}_k$ 远小于全局最差情况 Lipschitz 常数，使算法可以在平坦区域采取高达全局容许步长 10 倍以上的步长更新。
避免逐轮线搜索带来的计算节省：CODER-LineSearch 虽也是无参数设计，但每轮需要反复回溯求值算子，其实际计算开销远超 ADUCA 的纯显式计算。
对偶坐标重缩放的稳定性：在第二组使用对角重缩放矩阵 $\bm{\Lambda}$ 的实验中，其他算法在某些数据集（如 gisette）上出现了收敛退化，而 ADUCA 能稳健兼容任意正对角重缩放，表现极度稳定。

亮点与洞察¶

一整轮算子延迟却维持全局近最优界：巧妙利用前一轮算子外推代替实时算子，成功打破循环方法难以并行的传统认知，且理论预言机复杂度依然严格达到 $\mathcal{O}(1/\epsilon)$ 与 $\mathcal{O}(\log^2(1/\epsilon))$。
四阶差分相消的精巧李雅普诺夫分析：首次在循环算法中建立跨越连续四个周期的内积与位移能量折叠关系，通过细致分配加权参数 $\delta_1 \sim \delta_4$ 完成伸缩相消，为块坐标自适应算法提供了极具启发性的证明模板。
真正意义上的开箱即用（Parameter-Free）：除了初始化时进行至多对数步的回溯以外，全生命周期无超参调节、无需先验知识、无需逐轮试探，直接提供显式公式（如公式 3.10）。

局限与展望¶

强单调理论界存在对数因子冗余：目前强单调条件下的预言机复杂度为 $\mathcal{O}(\log^2(1/\epsilon))$，相比经典下界 $\mathcal{O}(\log(1/\epsilon))$ 额外多出一个对数项。
算子单调性限制：目前理论仅覆盖单调算子与 Minty 变分不等式，尚未拓展到非单调、弱单调或 Minty 条件不成立的复杂强化学习博弈场景。
大规模真机分布式验证有待补齐：论文虽在理论上论证了延迟更新对弱同步和并行的友好性，但数值实验主要在单机多线程/基准数据集上模拟完成，缺乏真实千卡分布式集群上的网络通信重叠评测。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出免线搜索、无参数且带延迟更新机制的自适应循环变分不等式算法。
实验充分度: ⭐⭐⭐⭐ 在典型凸凹 Min-Max 支撑向量机问题上提供了细致的几何估计对比与超参消融。
写作质量: ⭐⭐⭐⭐⭐ 数学推导严丝合缝，动机到算法设计的逻辑链条极为清晰。
价值: ⭐⭐⭐⭐⭐ 为高阶变分不等式与大规模分布式并行块坐标优化提供了重要的理论基石与实用模板。

超参数配置 \((\beta, \rho, \gamma)\)	测试数据集	选取的 \(\mu\) 范围	原始目标次优性收敛轨迹差异	核心结论
\(\beta=0.7, \rho=1.3, \gamma=0.05\)	a9a / gisette / SUSY	\(\mu \in [0, 10^{-2}]\)	多条 \(\mu\) 曲线完全重叠，肉眼不可分	对 \(\mu\) 的取值高度鲁棒
\(\beta=0.8, \rho=1.2, \gamma=0.2\)	a9a / gisette / SUSY	\(\mu \in [0, 10^{-2}]\)	下降斜率在 \(\mu=0\) 与 \(\mu>0\) 时严格一致	实践中可直接安全置 \(\mu=0\)
\(\beta=0.9, \rho=1.1, \gamma=0.3\)	a9a / gisette / SUSY	\(\mu \in [0, 10^{-2}]\)	各数据集上收敛历程曲线重合度 \(>99\%\)	强凸模数仅作为理论分析工具，不构成实际算法超参敏感点

数据集	维度 \((d \times n)\)	PCCM 状态	CODER / CODER-LineSearch 表现	GRAAL 收敛特性	ADUCA（本文）表现
a9a	\(123 \times 32,561\)	收敛振荡缓慢	稳步下降但受线搜索额外算子开销拖累	较快达到平稳	全程最优，在相同数据扫描遍数下原始间隙 \(f(\mathbf{x})-f^*\) 最快降至 \(10^{-6}\) 以下
gisette	\(5,000 \times 6,000\)	进展缓慢	随数据遍数缓慢收敛	在重新对角缩放后性能显著退化	收敛速度显著优于其他所有方法，算子估计紧凑稳定
SUSY-test	\(18 \times 5,000,000\)	易停滞	线性稳定下降	达到一定精度后收敛放缓	始终保持最陡峭的下降曲线，显著节省有效算子评估次数