无需光滑常数或线搜索，自适应投影无梯度优化新方法。
Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization
- 用历史迭代差值自归一化估计局部光滑性，每步最小化二次近似模型。
- 在噪声趋近零时，收敛率逼近最优的 O(ε⁻²)，显著优于传统方法。
- 适用于未知几何结构的非凸随机优化，适合机器学习中的稀疏约束问题。
我们提出 ALFCG（自适应无光滑常数条件梯度），首个无需全局光滑常数或线搜索的自适应投影无梯度框架，用于随机复合非凸优化。与以往使用开环递减步长、保守光滑常数或昂贵回溯的方法不同，ALFCG通过维护历史迭代差值的自归一化累加器来估计局部光滑性，并在每步最小化二次代理模型，保持 Frank-Wolfe 简洁性的同时适应未知几何结构。研究了三种变体：针对有限和问题的 ALFCG-FS 使用 SPIDER 估计器；针对随机期望问题的 ALFCG-MVR1 与 ALFCG-MVR2 分别采用单批与双批动量方差缩减，在平均与个体光滑条件下运行。达到 ε-平稳点所需迭代复杂度分别为：ALFCG-FS 为 𝒪(N + √N ε⁻²)，ALFCG-MVR1 为 ˜𝒪(σ²ε⁻⁴ + ε⁻²)，ALFCG-MVR2 为 ˜𝒪(σε⁻³ + ε⁻²)，其中 N 为组件数，σ 为噪声水平。当 σ → 0 时，这些界降至最优率 ˜𝒪(ε⁻²)。在核范数球与 ℓₚ 球上的多分类实验表明，ALFCG 通常优于现有最优条件梯度基线。
原文摘要 · Abstract (English)
We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first \textit{adaptive} projection-free framework for stochastic composite nonconvex minimization that \textit{requires neither global smoothness constants nor line search}. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an $ε$-stationary point, ALFCG-FS attains $\mathcal{O}(N+\sqrt{N}ε^{-2})$ iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve $\tilde{\mathcal{O}}(σ^2ε^{-4}+ε^{-2})$ and $\tilde{\mathcal{O}}(σε^{-3}+ε^{-2})$, where $N$ is the number of components and $σ$ is the noise level. In contrast to typical $\mathcal{O}(ε^{-4})$ or $\mathcal{O}(ε^{-3})$ rates, our bounds reduce to the optimal rate up to logarithmic factors $\tilde{\mathcal{O}}(ε^{-2})$ as the noise level $σ\to 0$. Extensive experiments on multiclass classification over nuclear norm balls and $\ell_p$ balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。