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

arXiv: https://arxiv.org/abs/2607.25785 · HTML: https://mlsanity.com/paper/2607.25785/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 34 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 26 of 26)

- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Convergence Rate of Frank-Wolfe for Non-Convex Objectives](https://mlsanity.com/paper/1607.00345/) (2016)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Stochastic Recursive Momentum for Policy Gradient Methods](https://mlsanity.com/paper/2003.04302/) (2020)
- [A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2003.00430/) (2020)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization](https://mlsanity.com/paper/2004.04357/) (2020)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Stochastic Frank-Wolfe: Unified Analysis and Zoo of Special Cases](https://mlsanity.com/paper/2406.06788/) (2024)
- [Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometry](https://mlsanity.com/paper/2408.01848/) (2024)
- [Stochastic-Constrained Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2312.04312/) (2023)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)
- [Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization](https://mlsanity.com/paper/2605.25255/) (2026)

## Abstract (arXiv)

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.