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(τ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 σ2mapsto 2Lambda Gσ2 and L2mapsto 2Lambda L2, where Lambda=O(τmixlog T). For positive centered noise, the tuned method achieves expected sample complexity widetildeO((τmix2Gσ+τmix5/2Gσ2)varepsilon-3+τmix5varepsilon-2). The exactly noiseless specialization achieves widetildeO(varepsilon-2) with mixing-time-free constants, while a mixing-time-oblivious variant achieves widetildeO(τmix6varepsilon-3+τmix3varepsilon-2). All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.