# Optimized projection-free algorithms for online learning: construction and worst-case analysis

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 39 references that are in the map.
- First posted on arXiv 6 Jun 2025.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Do LLM Agents Have Regret? A Case Study in Online Learning and Games](https://mlsanity.com/paper/2403.16843/) (2024)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019)
- [Exact Worst-case Performance of First-order Methods for Composite Convex Optimization](https://mlsanity.com/paper/1512.07516/) (2015)
- [Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods](https://mlsanity.com/paper/2203.07305/) (2022)
- [Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions](https://mlsanity.com/paper/1902.00947/) (2019)
- [PEPit: computer-assisted worst-case analyses of first-order optimization methods in Python](https://mlsanity.com/paper/2201.04040/) (2022)
- [On Fundamental Proof Structures in First-Order Optimization](https://mlsanity.com/paper/2310.02015/) (2023)
- [A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent](https://mlsanity.com/paper/1712.09498/) (2017)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (2021)

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

- [Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading](https://mlsanity.com/paper/2509.06466/) (2025)
- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)
- [Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization](https://mlsanity.com/paper/2610.00254/) (2026)

## Abstract (arXiv)

This work studies and develop projection-free algorithms for online learning with linear optimization oracles (a.k.a. Frank-Wolfe) for handling the constraint set. More precisely, this work (i) provides an improved (optimized) variant of an online Frank-Wolfe algorithm along with its conceptually simple potential-based proof, and (ii) shows how to leverage semidefinite programming to jointly design and analyze online Frank-Wolfe-type algorithms numerically in a variety of settings-that include the design of the variant (i). Based on the semidefinite technique, we conclude with strong numerical evidence suggesting that no pure online Frank-Wolfe algorithm within our model class can have a regret guarantee better than O(T^3/4) (T is the time horizon) without additional assumptions, that the current algorithms do not have optimal constants, that the algorithm benefits from similar anytime properties O(t^3/4) not requiring to know T in advance, and that multiple linear optimization rounds do not generally help to obtain better regret bounds.