Adaptive Conditional Gradient Sliding: Projection-Free and Line-Search-Free Acceleration¶

会议: NeurIPS 2026
arXiv: 2601.20443
OpenReview: https://openreview.net/forum?id=u4sFmbwanR
代码: https://github.com/ZIB-IOL/FrankWolfe.jl
领域: 优化/理论
关键词: 无投影优化, 条件梯度滑动, 自适应步长, 无线搜索加速, 局部Lipschitz估计

一句话总结¶

针对约束集投影开销昂贵的大规模凸优化问题，本文提出自适应条件梯度滑动算法（AdCGS），在仅依赖线性最小化预言机（LMO）且无需线搜索与全局光滑常数的条件下，首次实现了匹配基于投影方法的 Nesterov $\mathcal{O}(1/k^2)$ 加速收敛率与强凸线性收敛率。

研究背景与动机¶

在大规模带约束凸优化问题中，当可行域结构复杂（如核范数球、截断多面体或复杂矩阵流形约束）时，正交投影往往需要高维奇异值分解或二次规划求解，计算开销极其昂贵。条件梯度法（CG / Frank-Wolfe）及其加速变体条件梯度滑动（Conditional Gradient Sliding, CGS）仅依赖线性最小化预言机（LMO），通过将外层加速梯度与内层 CG 循环解耦，允许单次梯度评估在多次 LMO 迭代中复用，从而大幅削减了一阶梯度预言机（FOO）的调用次数。然而，经典 CGS 算法严重依赖未知的全局光滑常数 $L$；若采用传统的回溯线搜索，则每步试探都需额外计算目标函数值或梯度，不仅破坏了梯度滑动的解耦收益，还会显著增加实际运行时间。

现有自适应步长加速方法（如基于局部曲率或局部 Lipschitz 估计的 AC-FGM）虽然摆脱了线搜索，但本质上建立在精确欧氏投影的基础之上，无法直接移植到投影受限的场景。核心矛盾在于：基于局部 Lipschitz 估计的自适应步长往往会动态激进放大步长，这使得外层加速序列对内层子问题的非精确解极为敏感；若内层求解精度控制过松，累积误差会彻底摧毁加速性质；若精度要求过紧，又会导致内层 LMO 迭代次数爆炸，失去无投影优化的效率优势。

本文的切入角度是精确刻画自适应动态步长与内层 Frank-Wolfe 对偶间隙（FW gap）误差累积的理论交互边界，通过设计与自适应步长耦合的外层加速外推和递减内层容差调度，在纯 LMO 框架下兼顾自适应步长与加速率。核心 idea：将局部 Lipschitz 估计驱动的自适应步长机制深度融入条件梯度滑动框架，通过严格理论边界设计内层对偶间隙收敛容差调度，在无投影且无线搜索的前提下同时实现凸函数的 $\mathcal{O}(1/k^2)$ 加速和局部强凸函数的线性收敛。

方法详解¶

整体框架¶

AdCGS 采用加速外层迭代与条件梯度内层子问题求解的双层架构。在外层迭代中，算法维护三个序列：外推锚点序列 $\{x_k\}$、滑动聚合序列 $\{y_k\}$ 以及内层子问题近似解序列 $\{z_k\}$。在第 $k$ 轮外层迭代，算法首先在历史梯度点处构建强凸二次辅助子问题，调用仅依赖 LMO 的内层 Frank-Wolfe 循环求解至预设容差 $\delta_k$，随后通过非线性加权更新外层变量，并根据当前位移差与梯度差动态估计局部 Lipschitz 常数 $L_k$，用以确定下一轮外层步长 $\eta_{k+1}$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入与初始化<br/>x₀=y₀=z₀ ∈ P, 初始步长 η₁"] --> B["阶段1：内层条件梯度子求解<br/>基于 LMO 求解二次子问题至 FW 间隙 ≤ δ_k"]
    B --> C["阶段2：双重外层变量外推与聚合<br/>更新 y_k=(1-β_k)y_{k-1}+β_k z_k 与 x_k"]
    C --> D["阶段3：局部曲率感知与步长自适应更新<br/>计算局部 Lipschitz 估计 L_k 并更新 η_{k+1}"]
    D -->|未满足收敛标准| B
    D -->|FW 间隙达到容差| E["输出最终解 x_k"]

关键设计¶

1. 内层条件梯度子求解：解耦梯度与无投影二次逼近

传统投影梯度法在每一步需要精确求解欧氏投影 $\mathrm{argmin}_{z \in P} \frac{1}{2}\|z - (y_{k-1} - \eta_k \nabla f(x_{k-1}))\|^2$。AdCGS 将该高成本投影替换为一个显式的带一阶梯度的二次辅助子问题： $$z_k \approx \mathrm{argmin}_{z \in P} \left\{ \langle \nabla f(x_{k-1}), z \rangle + \frac{1}{2\eta_k} \|z - y_{k-1}\|^2 \right\}$$ 由于该辅助函数的梯度形式为 $\nabla \psi_k(u) = \nabla f(x_{k-1}) + \frac{u - y_{k-1}}{\eta_k}$，目标函数自身具备全局 $1/\eta_k$-Lipschitz 连续梯度且强凸，因此可以通过经典的 Frank-Wolfe（CG）循环求解。在第 $t$ 次内层循环中，只需调用一次 LMO：$v_t \in \mathrm{argmin}_{v \in P} \langle \nabla \psi_k(u_t), v \rangle$。算法监控其对偶间隙 $\mathcal{G}_k(u_t) = \max_{v \in P} \langle \nabla \psi_k(u_t), u_t - v \rangle$，并在其降至预设精度 $\delta_k$ 时截断退出。根据理论分析，求解该子问题达到 $\delta_k$ 精度所需的内层迭代步数严格有界于 $T_k = \lceil 6D^2 / (\eta_k \delta_k) \rceil$（其中 $D$ 为可行域直径），彻底规避了昂贵的正交投影计算。

2. 双重外层变量外推与聚合：稳定累积非精确误差

为获得 Nesterov 加速特性同时吸收内层非精确性带来的残差扰动，AdCGS 引入了滑动聚合序列 $y_k$ 与外推点序列 $x_k$： $$y_k = (1 - \beta_k) y_{k-1} + \beta_k z_k, \quad x_k = \frac{\tau_k}{1 + \tau_k} x_{k-1} + \frac{1}{1 + \tau_k} z_k$$ 其中参数选择 $\beta_1 = 0, \beta_k = \beta \in (0, 1 - \sqrt{6}/3]$（对于 $k \ge 2$），而 $\tau_k$ 满足递推关系 $\tau_1 = 0, \tau_k = k/2$（或更一般的广义自适应形式 $\tau_k = \tau_{k-1} + \frac{\alpha}{2} + \frac{2(1-\alpha)\eta_k L_{k-1}}{\tau_{k-1}}$）。通过建立精确的单步能量不等式，内层非精确残差在累加时转化为误差和 $\mathcal{S}_k = \sum_{i=1}^k \eta_{i+1}(\delta_{i+1} + \delta_i)$。由于设计了与迭代计数相匹配的衰减调度 $\delta_k = \frac{D_0^2}{k^{1+\theta}(k+1)}$（或固定迭代步下的 $\delta_k = \frac{D_0^2}{Nk}$），使得即使外层自适应步长逐步放大，累积误差项依然能够被常数级上界控制，保证了外推点 $x_k$ 能够稳步实现 $\mathcal{O}(1/k^2)$ 的加速前向推进。

3. 局部曲率感知与步长自适应更新：摆脱全局参数与线搜索

针对目标函数全局 Lipschitz 常数 $L$ 未知且局部几何曲率变化剧烈的问题，AdCGS 在每次外层迭代仅依据前后两步的实际位移和梯度差值，计算局部 Lipschitz 估计： $$L_k = \begin{cases} 0, & \text{if } D_f(x_{k-1}, x_k) = 0 \\ \frac{\|\nabla f(x_k) - \nabla f(x_{k-1})\|^2}{2 D_f(x_{k-1}, x_k)}, & \text{if } D_f(x_{k-1}, x_k) > 0 \end{cases} \quad (k \ge 2)$$ 其中 $D_f(x_{k-1}, x_k) = f(x_{k-1}) - f(x_k) - \langle \nabla f(x_k), x_{k-1} - x_k \rangle$ 为 Bregman 散度。随后，外层步长 $\eta_k$ 无需任何回溯线搜索，直接按局部估计进行自适应缩放： $$\eta_k = \min \left\{ \frac{k}{k-1}\eta_{k-1}, \, \frac{k-1}{8 L_{k-1}} \right\} \quad (k \ge 4)$$ 这一更新规则保证了步长随迭代进行按 $\mathcal{O}(k)$ 增长（满足 $\eta_k \ge \frac{k}{12 \hat{L}_{k-1}}$），同时在曲率剧烈变化区域自动收缩，从而在完全不依赖全局 $L$ 的情况下实现了与最优加速算法同阶的收敛保证。

损失函数 / 训练策略¶

对于局部强凸目标函数（局部强凸参数为 $\mu > 0$），AdCGS 通过多阶段重启策略（Algorithm 3）运行外层循环。每个阶段内固定运行外层迭代次数： $$N = \left\lceil \sqrt{\frac{15\gamma L}{\mu} \left( \frac{1}{\beta(1-\beta)} + \frac{3}{2}\eta_1 \right)} \right\rceil$$ 并将第 $s$ 阶段的内层容差设为 $\delta_k = \frac{2\phi_0}{2^s \mu N k}$。该策略确保目标函数误差在每个阶段呈几何级数减半：$f(w_s) - f(x^*) \le \frac{\phi_0}{2^s}$，从而在任意紧凸集上首次证明了无需多面体或强凸集等特殊几何假设的线性收敛率，总 FOO 复杂度为 $\mathcal{O}\left( \sqrt{L/\mu} \log_2(\phi_0/\epsilon) \right)$，总 LMO 复杂度为 $\mathcal{O}\left( \mu L D^2/\epsilon + \sqrt{L/\mu} \log_2(\phi_0/\epsilon) \right)$。

实验关键数据¶

主实验¶

论文在 Julia 1.12 环境下基于 FrankWolfe.jl 对三大代表性问题进行了评估：单纯形约束最小二乘回归、$\ell_2$ 球约束 $\ell_p$ 损失回归（$p=1.5$，属于非局部光滑设置），以及 $K$-稀疏多面体约束逻辑回归。基线包括经典 CGS、带线搜索的 CG、开环步长 CG、自适应 CG（AC-CGM 与 ACG）、投影梯度法（PG）以及基于投影的自适应加速算法 AC-FGM。

任务与约束集	维度与规模 $(m, n)$	对比指标（达到相同精度下）	本文方法 (AdCGS 系列)	经典 CGS	自适应无加速 (AC-CGM / ACG)	相对优势与表现
单纯形最小二乘回归	$(2500, 500)$	原向间隙下降至 $10^{-10}$ 所需 FOO 调用数	约 200 次 (AdCGS:0.5)	> 2000 次	停滞或 > 5000 次	梯度调用显著减少，收敛速度较 CGS 提升近一个数量级
单纯形最小二乘回归	$(2500, 500)$	达到目标间隙运行时间 (s)	最优 (显著领先)	耗时增加 3-5 倍	速度慢	自适应大步长抵消了稍多的 LMO 运算开销
$\ell_{1.5}$ 损失回归 (YearPrediction)	$(463715, 90)$	超大规模梯度样本下 Primal Gap	下降最陡峭 (AdCGS:0.0)	无法有效下降 (不满足局部光滑)	缓慢下降	克服非局部光滑性瓶颈，超越 PG 投影法
$K$-稀疏逻辑回归 (gisette)	$(6000, 5000)$	5000维高维特征下的 FW Gap	收敛至 $10^{-8}$ 最快 (AdCGS:0.0)	收敛缓慢	停滞震荡	在高维稀疏约束下，显著节约昂贵的数据集全梯度评估

消融实验¶

针对广义递推参数 $\alpha \in \{0.0, 0.1, 0.5, 1.0\}$ 以及第一轮步长初始化是否采用单次线搜索（LS1）进行了系统消融对比：

算法变体配置	步长外推参数 $\alpha$	第一轮线搜索 (LS1)	单纯形最小二乘 $(2500,500)$ 表现	说明与关键特性
AdCGS (理论标准版)	$\alpha = 1.0$	否 (利用扰动估计 $L_0$)	表现稳定，平稳加速收敛	严格保证理论证明的加速速率上界
AdCGS (LS1)	$\alpha = 1.0$	是 (仅在 $k=1$ 做微小线搜索)	出现数值不稳定波动	初始步长选取受首轮边界估计影响过大
AdCGS:0.5	$\alpha = 0.5$	否	全场最优 (FOO 与运行时间最佳)	经验上平衡了外推激进性与子问题求解难度
AdCGS:0.5 (LS1)	$\alpha = 0.5$	是	与无 LS1 版本表现完全相当	鲁棒性极强，对首轮线搜索不敏感
AdCGS:0.0	$\alpha = 0.0$	否	高维逻辑回归及 $\ell_p$ 回归上表现最佳	纯经验变体，在外层外推中赋予梯度差更大权重

关键发现¶

在以样本量巨大（如 YearPredictionMSD，样本数达 463,715）为特征的问题中，计算全梯度的代价极其高昂。AdCGS 通过滑动机制将多次 LMO 调用的成本分摊至单次 FOO 调用上，配合自适应步长，使得 Primal Gap 随墙上时钟时间下降的斜率显著高于基于精确投影的 PG 与未加速的 CG 变体。
尽管由于内层采用了更紧的对偶间隙容差 $\delta_k$，AdCGS 的总 LMO 调用次数略高于传统参数固定的 CGS，但因为无需全剧遍历调参且每次外层步长更大，其总时钟运行时间与 FOO 调用次数均大幅优于 CGS。
理论上 $\alpha=1.0$ 具备最优雅的完备证明，但在实践中，经验参数 $\alpha \in [0.0, 0.5]$ 表现出更优越的泛化加速性能，尤其在非严格光滑的 $\ell_{1.5}$ 回归中表现出超预期的收敛鲁棒性。

亮点与洞察¶

理论填补空白：首次彻底证明了无投影且无线搜索的凸优化算法能够达到 Nesterov $\mathcal{O}(1/k^2)$ 最优加速界，解决了长期以来“自适应无搜索”与“投影自由”不可兼得的技术难题。
无需特殊几何假设的线性收敛：传统 Frank-Wolfe 类算法的线性收敛通常高度依赖约束多面体的面几何结构（如边界原子、极点性质）或强凸集合假设；AdCGS 仅凭目标函数局部强凸性，在任意紧凸集上通过多阶段重启即可建立线性收敛保障。
实用的容差递减调度设计：推导出的 $\delta_k$ 衰减速率 $\mathcal{O}(1/k^{2+\theta})$ 精妙地契合了内层子问题的二次结构，使内层 CG 循环迭代次数 $T_k$ 随外层自适应步长的放大而平稳增长，为无投影算法的工程实现提供了坚实且极易部署的离散化调优准则。

局限与展望¶

局部强凸参数未知性：多阶段重启算法（Algorithm 3）的迭代步数 $N$ 需要预先知道局部强凸参数 $\mu$，目前尚缺乏伴随自适应 Lipschitz 常数一同在线鲁棒估计 $\mu$ 的分析保证。
函数类覆盖限制：当前完整的理论加速框架仅适用于普通凸函数与局部强凸函数，尚未拓展至非凸、弱凸（weakly convex）或随机抽样（stochastic）梯度设置。
内层 LMO 负担累积：在极高精度求解需求下，为严格压制外层累积误差，后期的内层容差 $\delta_k$ 较小，导致后期单轮外层迭代耗费的 LMO 调用次数增加。未来可结合动量加速内层 CG 或不精确 LMO 进一步降低复杂度。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立无投影且无线搜索的自适应加速理论框架，解决基础理论痛点。
实验充分度: ⭐⭐⭐⭐ 覆盖多种经典凸优化问题与超大规模实际数据集，对比基线全面，含深入消融。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严密自洽，单步不等式分解与误差项控制条理清晰。
价值: ⭐⭐⭐⭐⭐ 为大规模机器学习与高维受限优化的无投影工程实现提供了重要理论基石与实用算法。

任务与约束集	维度与规模 \((m, n)\)	对比指标（达到相同精度下）	本文方法 (AdCGS 系列)	经典 CGS	自适应无加速 (AC-CGM / ACG)	相对优势与表现
单纯形最小二乘回归	\((2500, 500)\)	原向间隙下降至 \(10^{-10}\) 所需 FOO 调用数	约 200 次 (AdCGS:0.5)	> 2000 次	停滞或 > 5000 次	梯度调用显著减少，收敛速度较 CGS 提升近一个数量级
单纯形最小二乘回归	\((2500, 500)\)	达到目标间隙运行时间 (s)	最优 (显著领先)	耗时增加 3-5 倍	速度慢	自适应大步长抵消了稍多的 LMO 运算开销
\(\ell_{1.5}\) 损失回归 (YearPrediction)	\((463715, 90)\)	超大规模梯度样本下 Primal Gap	下降最陡峭 (AdCGS:0.0)	无法有效下降 (不满足局部光滑)	缓慢下降	克服非局部光滑性瓶颈，超越 PG 投影法
\(K\)-稀疏逻辑回归 (gisette)	\((6000, 5000)\)	5000维高维特征下的 FW Gap	收敛至 \(10^{-8}\) 最快 (AdCGS:0.0)	收敛缓慢	停滞震荡	在高维稀疏约束下，显著节约昂贵的数据集全梯度评估

算法变体配置	步长外推参数 \(\alpha\)	第一轮线搜索 (LS1)	单纯形最小二乘 \((2500,500)\) 表现	说明与关键特性
AdCGS (理论标准版)	\(\alpha = 1.0\)	否 (利用扰动估计 \(L_0\))	表现稳定，平稳加速收敛	严格保证理论证明的加速速率上界
AdCGS (LS1)	\(\alpha = 1.0\)	是 (仅在 \(k=1\) 做微小线搜索)	出现数值不稳定波动	初始步长选取受首轮边界估计影响过大
AdCGS:0.5	\(\alpha = 0.5\)	否	全场最优 (FOO 与运行时间最佳)	经验上平衡了外推激进性与子问题求解难度
AdCGS:0.5 (LS1)	\(\alpha = 0.5\)	是	与无 LS1 版本表现完全相当	鲁棒性极强，对首轮线搜索不敏感
AdCGS:0.0	\(\alpha = 0.0\)	否	高维逻辑回归及 \(\ell_p\) 回归上表现最佳	纯经验变体，在外层外推中赋予梯度差更大权重