# Efficient Projection-Free Online Methods with Stochastic Recursive Gradient

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2019.

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Adaptive Fairness-Aware Online Meta-Learning for Changing Environments](https://mlsanity.com/paper/2205.11264/) (2022)
- [Compression-aware Training of Neural Networks using Frank-Wolfe](https://mlsanity.com/paper/2205.11921/) (2022)
- [Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2308.07536/) (2023)
- [From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization](https://mlsanity.com/paper/2405.00065/) (2024)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Continuous Diagnosis and Prognosis by Controlling the Update Process of Deep Neural Networks](https://mlsanity.com/paper/2210.02719/) (2022)
- [A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization](https://mlsanity.com/paper/2402.08621/) (2024)
- [Confidence-Guided Learning Process for Continuous Classification of Time Series](https://mlsanity.com/paper/2208.06883/) (2022)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)
- [CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems](https://mlsanity.com/paper/2105.14216/) (2021)
- [Improved Regret Bounds for Online Submodular Maximization](https://mlsanity.com/paper/2106.07836/) (2021)
- [Projection-Free Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/2305.01333/) (2023)
- [Dynamic Environment Responsive Online Meta-Learning with Fairness Awareness](https://mlsanity.com/paper/2402.12319/) (2024)
- [Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe](https://mlsanity.com/paper/2510.13713/) (2025)
- [On Private Online Convex Optimization: Optimal Algorithms in ℓp-Geometry and High Dimensional Contextual Bandits](https://mlsanity.com/paper/2206.08111/) (2022)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)

## Abstract (arXiv)

This paper focuses on projection-free methods for solving smooth Online Convex Optimization (OCO) problems. Existing projection-free methods either achieve suboptimal regret bounds or have high per-iteration computational costs. To fill this gap, two efficient projection-free online methods called ORGFW and MORGFW are proposed for solving stochastic and adversarial OCO problems, respectively. By employing a recursive gradient estimator, our methods achieve optimal regret bounds (up to a logarithmic factor) while possessing low per-iteration computational costs. Experimental results demonstrate the efficiency of the proposed methods compared to state-of-the-arts.