# Chasing Convex Bodies Optimally

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

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

- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Smoothed Online Optimization with Unreliable Predictions](https://mlsanity.com/paper/2202.03519/) (2022)
- [Optimal Comparator Adaptive Online Learning with Switching Cost](https://mlsanity.com/paper/2205.06846/) (2022)
- [Sequential Strategic Screening](https://mlsanity.com/paper/2301.13397/) (2023)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor](https://mlsanity.com/paper/2205.00741/) (2022)
- [Online Optimization with Feedback Delay and Nonlinear Switching Cost](https://mlsanity.com/paper/2111.00095/) (2021)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates](https://mlsanity.com/paper/2609.20701/) (2026)
- [Smoothed Online Combinatorial Optimization Using Imperfect Predictions](https://mlsanity.com/paper/2204.10979/) (2022)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)
- [Consistent Model Chasing Is Minimax Optimal: The Exact Value of Scalar Adversarial Adaptive Control under Large Parametric Uncertainty](https://mlsanity.com/paper/2608.13651/) (2026)
- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)

## Abstract (arXiv)

In the chasing convex bodies problem, an online player receives a request sequence of N convex sets K1,dots, KN contained in a normed space mathbb Rd. The player starts at x0∈ mathbb Rd, and after observing each Kn picks a new point xn∈ Kn. At each step the player pays a movement cost of ||xn-xn-1||. The player aims to maintain a constant competitive ratio against the minimum cost possible in hindsight, i.e. knowing all requests in advance. The existence of a finite competitive ratio for convex body chasing was first conjectured in 1991 by Friedman and Linial. This conjecture was recently resolved with an exponential 2O(d) upper bound on the competitive ratio. We give an improved algorithm achieving competitive ratio d in any normed space, which is exactly tight for ℓ∞. In Euclidean space, our algorithm also achieves competitive ratio O(√dlog N), nearly matching a √d lower bound when N is subexponential in d. The approach extends our prior work for nested convex bodies, which is based on the classical Steiner point of a convex body. We define the functional Steiner point of a convex function and apply it to the associated work function.