# Faster Projection-free Online Learning

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jan 2020.

## Built on by (most cited first, 30 of 40)

- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [HardCoRe-NAS: Hard Constrained diffeRentiable Neural Architecture Search](https://mlsanity.com/paper/2102.11646/) (2021)
- [Adaptive Fairness-Aware Online Meta-Learning for Changing Environments](https://mlsanity.com/paper/2205.11264/) (2022)
- [Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2602.08232/) (2026)
- [Projection-free Distributed Online Learning with Sublinear Communication Complexity](https://mlsanity.com/paper/2103.11102/) (2021)
- [Projection-free Adaptive Regret with Membership Oracles](https://mlsanity.com/paper/2211.12638/) (2022)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning](https://mlsanity.com/paper/2205.11470/) (2022)
- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (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)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)
- [Improved Projection-free Online Continuous Submodular Maximization](https://mlsanity.com/paper/2305.18442/) (2023)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Projection-Free Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2402.08799/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Riemannian Projection-free Online Learning](https://mlsanity.com/paper/2305.19349/) (2023)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [Optimized projection-free algorithms for online learning: construction and worst-case analysis](https://mlsanity.com/paper/2506.05855/) (2025)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (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)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [Gradient and Projection Free Distributed Online Min-Max Resource Optimization](https://mlsanity.com/paper/2112.03896/) (2021)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)

## Abstract (arXiv)

In many online learning problems the computational bottleneck for gradient-based methods is the projection operation. For this reason, in many problems the most efficient algorithms are based on the Frank-Wolfe method, which replaces projections by linear optimization. In the general case, however, online projection-free methods require more iterations than projection-based methods: the best known regret bound scales as T3/4. Despite significant work on various variants of the Frank-Wolfe method, this bound has remained unchanged for a decade. In this paper we give an efficient projection-free algorithm that guarantees T2/3 regret for general online convex optimization with smooth cost functions and one linear optimization computation per iteration. As opposed to previous Frank-Wolfe approaches, our algorithm is derived using the Follow-the-Perturbed-Leader method and is analyzed using an online primal-dual framework.