# Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 26 Feb 2022.

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

- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Lipschitz constant estimation of Neural Networks via sparse polynomial optimization](https://mlsanity.com/paper/2004.08688/) (2020)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [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)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [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)
- [Primal-dual stochastic gradient method for convex programs with many functional constraints](https://mlsanity.com/paper/1802.02724/) (2018)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [Stochastic Frank-Wolfe for Composite Convex Minimization](https://mlsanity.com/paper/1901.10348/) (2019)
- [A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization](https://mlsanity.com/paper/1507.06243/) (2015)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions](https://mlsanity.com/paper/1905.11535/) (2019)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Almost surely constrained convex optimization](https://mlsanity.com/paper/1902.00126/) (2019)
- [Conditional gradient methods for stochastically constrained convex minimization](https://mlsanity.com/paper/2007.03795/) (2020)

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

- [Federated Frank-Wolfe Algorithm](https://mlsanity.com/paper/2408.10090/) (2024)

## Abstract (arXiv)

We propose a stochastic conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm's execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs.