# Chasing Nested Convex Bodies Nearly Optimally

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2018.

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

- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [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)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Diversified Recommendations for Agents with Adaptive Preferences](https://mlsanity.com/paper/2210.07773/) (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)
- [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)
- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets](https://mlsanity.com/paper/2608.29074/) (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)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)
- [Selectivity Estimation for Linear Queries via Online Learning](https://mlsanity.com/paper/2607.02895/) (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)
- [Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions](https://mlsanity.com/paper/2609.11207/) (2026)

## Abstract (arXiv)

The convex body chasing problem, introduced by Friedman and Linial, is a competitive analysis problem on any normed vector space. In convex body chasing, for each timestep t∈mathbb N, a convex body Ktsubseteq mathbb Rd is given as a request, and the player picks a point xt∈ Kt. The player aims to ensure that the total distance sumt=0T-1||xt-xt+1|| is within a bounded ratio of the smallest possible offline solution. In this work, we consider the nested version of the problem, in which the sequence (Kt) must be decreasing. For Euclidean spaces, we consider a memoryless algorithm which moves to the so-called Steiner point, and show that in a certain sense it is exactly optimal among memoryless algorithms. For general finite dimensional normed spaces, we combine the Steiner point and our recent previous algorithm to obtain a new algorithm which is nearly optimal for all ℓpd spaces with p≥ 1, closing a polynomial gap.