# Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 41 references that are in the map.
- First posted on arXiv 6 Mar 2026.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [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)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (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)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Riemannian Optimization via Frank-Wolfe Methods](https://mlsanity.com/paper/1710.10770/) (2017)
- [Frank-Wolfe Algorithms for Saddle Point Problems](https://mlsanity.com/paper/1610.07797/) (2016)
- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Conditional Gradient Methods](https://mlsanity.com/paper/2211.14103/) (2022)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization](https://mlsanity.com/paper/2002.11860/) (2020)
- [Accelerated Stochastic Gradient-free and Projection-free Methods](https://mlsanity.com/paper/2007.12625/) (2020)
- [Stochastic Frank-Wolfe for Composite Convex Minimization](https://mlsanity.com/paper/1901.10348/) (2019)
- [Heavy Ball Momentum for Conditional Gradient](https://mlsanity.com/paper/2110.04243/) (2021)
- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [Conditional gradient type methods for composite nonlinear and stochastic optimization](https://mlsanity.com/paper/1602.00961/) (2016)
- [Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization](https://mlsanity.com/paper/1901.01287/) (2019)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [A Parameter-Free Conditional Gradient Method for Composite Minimization under H"older Condition](https://mlsanity.com/paper/2305.18181/) (2023)
- [Model Function Based Conditional Gradient Method with Armijo-like Line Search](https://mlsanity.com/paper/1901.08087/) (2019)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [A generalized conditional gradient method for multiobjective composite optimization problems](https://mlsanity.com/paper/2302.12912/) (2023)
- [Splitting the Conditional Gradient Algorithm](https://mlsanity.com/paper/2311.05381/) (2023)

## Built on by (most cited first, 1 of 1)

- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)

## Abstract (arXiv)

We propose ALFCG (Adaptive Lipschitz-Free Conditional Gradient), the first textitadaptive projection-free framework for stochastic composite nonconvex minimization that textitrequires neither global smoothness constants nor line search. Unlike prior conditional gradient methods that use openloop diminishing stepsizes, conservative Lipschitz constants, or costly backtracking, ALFCG maintains a self-normalized accumulator of historical iterate differences to estimate local smoothness and minimize a quadratic surrogate model at each step. This retains the simplicity of Frank-Wolfe while adapting to unknown geometry. We study three variants. ALFCG-FS addresses finite-sum problems with a SPIDER estimator. ALFCG-MVR1 and ALFCG-MVR2 handle stochastic expectation problems by using momentum-based variance reduction with single-batch and two-batch updates, and operate under average and individual smoothness, respectively. To reach an ε-stationary point, ALFCG-FS attains O(N+√Nε-2) iteration complexity, while ALFCG-MVR1 and ALFCG-MVR2 achieve tildeO(σ2ε-4+ε-2) and tildeO(σε-3+ε-2), where N is the number of components and σ is the noise level. In contrast to typical O(ε-4) or O(ε-3) rates, our bounds reduce to the optimal rate up to logarithmic factors tildeO(ε-2) as the noise level σ → 0. Extensive experiments on multiclass classification over nuclear norm balls and ℓp balls show that ALFCG generally outperforms state-of-the-art conditional gradient baselines.