# Curvature of Feasible Sets in Offline and Online Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2020.

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

- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [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)
- [Online Convex Optimization with a Separation Oracle](https://mlsanity.com/paper/2410.02476/) (2024)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets](https://mlsanity.com/paper/2303.05037/) (2023)
- [Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds](https://mlsanity.com/paper/2411.12154/) (2024)

## Abstract (arXiv)

It is known that the curvature of the feasible set in convex optimization allows for algorithms with better convergence rates, and there has been renewed interest in this topic both for offline as well as online problems. In this paper, leveraging results on geometry and convex analysis, we further our understanding of the role of curvature in optimization: - We first show the equivalence of two notions of curvature, namely strong convexity and gauge bodies, proving a conjecture of Abernethy et al. As a consequence, this show that the Frank-Wolfe-type method of Wang and Abernethy has accelerated convergence rate O(frac1t2) over strongly convex feasible sets without additional assumptions on the (convex) objective function. - In Online Linear Optimization, we identify two main properties that help explaining why/when Follow the Leader (FTL) has only logarithmic regret over strongly convex sets. This allows one to directly recover a recent result of Huang et al., and to show that FTL has logarithmic regret over strongly convex sets whenever the gain vectors are non-negative. - We provide an efficient procedure for approximating convex bodies by strongly convex ones while smoothly trading off approximation error and curvature. This allows one to extend the improved algorithms over strongly convex sets to general convex sets. As a concrete application, we extend the results of Dekel et al. on Online Linear Optimization with Hints to general convex sets.