Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization

arXiv:2607.25785v1 Announce Type: cross Abstract: 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(au_{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 sigma^2mapsto 2Lambda G_sigma^2 and L^2mapsto 2Lambda L^2, where Lambda=O(au_{mix}log T). For positive centered noise, the tuned method achieves expected sample complexity widetilde{O}((au_{mix}^2G_sigma+au_{mix}^{5/2}G_sigma^2)arepsilon^{-3}+au_{mix}^5arepsilon^{-2}). The exactly noiseless specialization achieves widetilde{O}(arepsilon^{-2}) with mixing-time-free constants, while a mixing-time-oblivious variant achieves widetilde{O}(au_{mix}^6arepsilon^{-3}+au_{mix}^3arepsilon^{-2}). All guarantees are in expectation under a fixed transition kernel. Controlled numerical studies examine dependence sensitivity, a nonconvex composite instance, and clipping behavior.

Source: arXiv cs.LG | 2026-07-29