这篇论文搞了个新方法MC-ALFCG，专门对付马尔可夫链采样下的非凸优化，理论复杂度给得很细，数值实验也做了，搞优化算法的可以看看。
该论文提出MC-ALFCG，一种结合动量条件梯度与耦合截断多级蒙特卡洛估计的方法，用于处理固定遍历马尔可夫链单轨迹梯度采样下的非凸复合优化。在正中心噪声下，期望样本复杂度为Õ(τ_mix²G_σ ε⁻³ + τ_mix^(5/2) G_σ² ε⁻³ + τ_mix⁵ ε⁻²)，其中τ_mix为混合时间。精确无噪声版本达到Õ(ε⁻²)的复杂度且常数与混合时间无关。数值实验验证了参数灵敏度和剪枝行为。
Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization
We study stochastic composite nonconvex optimization over a compact convex set when gradient samples arrive along a single trajectory of a fixed ergodic Markov chain. Existing single-trajectory variance-reduction theory covers smooth unconstrained objectives; we address the projection-free composite setting using the generalized Frank-Wolfe gap. We propose MC-ALFCG, which combines a momentum conditional-gradient method with coupled capped multilevel Monte Carlo estimation and per-iteration clipping. The deepest nested average uses consecutive states from the same trajectory, yielding conditional bias $O(τ_{\mathrm{mix}}/T)$ uniformly over the starting state, while coupling controls the gradient-difference second moment through the iterate displacement. Clipping enforces the pathwise bounds needed by the adaptive analysis. We reduce the Markovian recursion to its independent-sampling counterpart under $σ^2\mapsto 2ΛG_σ^2$ and $L^2\mapsto 2ΛL^2$, where $Λ=O(τ_{\mathrm{mix}}\log T)$. For positive centered noise, the tuned method achieves expected sample complexity $\widetilde{O}((τ_{\mathrm{mix}}^2G_σ+τ_{\mathrm{mix}}^{5/2}G_σ^2)\varepsilon^{-3}+τ_{\mathrm{mix}}^5\varepsilon^{-2})$. The exactly noiseless specialization achieves $\widetilde{O}(\varepsilon^{-2})$ with mixing-time-free constants, while a mixing-time-oblivious variant achieves $\widetilde{O}(τ_{\mathrm{mix}}^6\varepsilon^{-3}+τ_{\mathrm{mix}}^3\varepsilon^{-2})$. All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.