# Linear Bandits on Uniformly Convex Sets

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 10 Mar 2021.

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

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Adaptive Sampling for Stochastic Risk-Averse Learning](https://mlsanity.com/paper/1910.12511/) (2019)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities](https://mlsanity.com/paper/1702.03040/) (2017)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- [Curvature of Feasible Sets in Offline and Online Optimization](https://mlsanity.com/paper/2002.03213/) (2020)
- [Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/1906.07867/) (2019)
- [Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets](https://mlsanity.com/paper/2011.03351/) (2020)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)

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

- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [Efficient Online-Bandit Strategies for Minimax Learning Problems](https://mlsanity.com/paper/2105.13939/) (2021)
- [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)

## Abstract (arXiv)

Linear bandit algorithms yield tildeO(n√T) pseudo-regret bounds on compact convex action sets Ksubsetℝn and two types of structural assumptions lead to better pseudo-regret bounds. When K is the simplex or an ℓp ball with p∈]1,2], there exist bandits algorithms with tildeO(√nT) pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond ℓp balls that enjoy pseudo-regret bounds of tildeO(√nT), which answers an open question from [BCB12, S 5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than O(√n). However, this comes at the expense of asymptotic rates in T varying between tildeO(√T) and tildeO(T).