# Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 57 references that are in the map.
- First posted on arXiv 23 May 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Logarithmic Regret for Adversarial Online Control](https://mlsanity.com/paper/2003.00189/) (2020)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees](https://mlsanity.com/paper/2202.04721/) (2022)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory](https://mlsanity.com/paper/2102.01623/) (2021)
- [Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities](https://mlsanity.com/paper/1702.03040/) (2017)
- [Frank-Wolfe and friends: a journey into projection-free first-order optimization methods](https://mlsanity.com/paper/2106.10261/) (2021)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [Curvature of Feasible Sets in Offline and Online Optimization](https://mlsanity.com/paper/2002.03213/) (2020)

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

- [Projection-free Online Exp-concave Optimization](https://mlsanity.com/paper/2302.04859/) (2023)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [Projection-Free Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2402.08799/) (2024)
- [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 Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets](https://mlsanity.com/paper/2402.12868/) (2024)
- [On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-balls](https://mlsanity.com/paper/2506.19752/) (2025)
- [Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts](https://mlsanity.com/paper/2506.01685/) (2025)
- [Lower Bounds for Linear-Oracle Online Learning](https://mlsanity.com/paper/2609.38375/) (2026)

## Abstract (arXiv)

In this paper, we develop new efficient projection-free algorithms for Online Convex Optimization (OCO). Online Gradient Descent (OGD) is an example of a classical OCO algorithm that guarantees the optimal O(√T) regret bound. However, OGD and other projection-based OCO algorithms need to perform a Euclidean projection onto the feasible set Csubset ℝd whenever their iterates step outside C. For various sets of interests, this projection step can be computationally costly, especially when the ambient dimension is large. This has motivated the development of projection-free OCO algorithms that swap Euclidean projections for often much cheaper operations such as Linear Optimization (LO). However, state-of-the-art LO-based algorithms only achieve a suboptimal O(T3/4) regret for general OCO. In this paper, we leverage recent results in parameter-free Online Learning, and develop an OCO algorithm that makes two calls to an LO Oracle per round and achieves the near-optimal widetildeO(√T) regret whenever the feasible set is strongly convex. We also present an algorithm for general convex sets that makes widetilde O(d) expected number of calls to an LO Oracle per round and guarantees a widetilde O(T2/3) regret, improving on the previous best O(T3/4). We achieve the latter by approximating any convex set C by a strongly convex one, where LO can be performed using widetilde O(d) expected number of calls to an LO Oracle for C.