新算法解决非光滑目标的随机组合优化问题，收敛更快更稳定。
Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe
- 用动量追踪雅可比和函数误差，生成完整随机线性近似。
- 非凸问题下达到 $\mathcal{O}(K^{-1/4})$ 收敛率，最优复杂度。
- 适用于鲁棒损失、风险度量等传统方法无法处理的场景。
随机组合优化旨在求解形如 $\min_{\bm{x} \in \mathcal{X}} F(\bm{f}(\bm{x}), \bm{x})$ 的目标，其中 $\bm{f}$ 仅可通过含噪声的随机查询获取。现有方法通常假设外层函数 $F$ 连续可微，这排除了众多实际应用，如鲁棒最大损失、条件风险价值（CVaR）和范数正则项。本文提出混合动量随机弗兰克-沃尔夫算法，放弃对 $F$ 光滑性的要求。通过结合基于动量的雅可比追踪器与泰勒校正函数追踪器，算法将整个随机线性化结果输入广义线性最小化预言机，而非单一梯度。在非凸目标下，外层函数 $L_F$-李普希茨时，建立 $\mathcal{O}(K^{-1/4})$ 的广义弗兰克-沃尔夫间隙收敛率，匹配预期光滑条件下无投影单样本随机方法的最优复杂度。分析还拓展至重尾噪声预言机，具有有界 $r$-阶矩（$r \in (1, 2]$），并随噪声消失恢复 Vladarean 等（2023）的确定性速率。
原文摘要 · Abstract (English)
Stochastic compositional optimization minimizes objectives of the form $\min_{\bm{x} \in \mathcal{X}} F(\bm{f}(\bm{x}), \bm{x})$, where $\bm{f}$ is accessible only through noisy stochastic queries. Existing methods for this problem assume that the outer function $F$ is continuously differentiable, which excludes many practically important applications such as robust max-of-losses, Conditional Value-at-Risk, and norm regularizers. We propose the Hybrid Momentum Stochastic Frank--Wolfe algorithm, which drops the smoothness assumption on $F$. By combining a momentum-based Jacobian tracker with a Taylor-corrected function tracker, the algorithm feeds an entire stochastic linearization -- rather than a single gradient -- into a generalized linear minimization oracle. We establish an $\mathcal{O}(K^{-1/4})$ convergence rate in the generalized Frank--Wolfe gap for non-convex objectives with $L_F$-Lipschitz outer functions, matching the optimal complexity for projection-free single-sample stochastic methods under expected smoothness. The analysis extends to heavy-tailed noise oracles with bounded $r$-th moments for $r \in (1, 2]$ and recovers the deterministic rates of Vladarean et al (2023) as the noise vanishes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。