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

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(\tau_{\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 $\sigma^2\mapsto 2\Lambda G_\sigma^2$ and $L^2\mapsto 2\Lambda L^2$, where $\Lambda=O(\tau_{\mathrm{mix}}\log T)$. For positive centered noise, the tuned method achieves expected sample complexity $\widetilde{O}((\tau_{\mathrm{mix}}^2G_\sigma+\tau_{\mathrm{mix}}^{5/2}G_\sigma^2)\varepsilon^{-3}+\tau_{\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}(\tau_{\mathrm{mix}}^6\varepsilon^{-3}+\tau_{\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.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2607.25785 [math.OC]

(or arXiv:2607.25785v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2607.25785 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.