A Linear Lower Bound for Convex Body Chasing in Every ℓp Norm
Abstract
We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in ℝd with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was Ω(d1/6), established by Papazov (2023); stronger lower bounds were known for ℓp norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of Ω(max{√d, d1−1/p}). In particular, a linear lower bound was known only for the ℓ∞ norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and ℓp lower bounds for p < ∞ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio O(d) - is asymptotically optimal for every norm. Our approach is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of Ω(r2) for requests of size O(r). We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a (2r+1)-dimensional ℓp vector space while approximately preserving movement costs up to a factor of O(r); the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.
Related
- A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
- A sharp lower bound for torsional rigidity of convex domains
- A Lower Bound for the Heavy-Ball Method on Smooth Convex Functions
- Mathematical Classification of Switching Types and Hierarchical Structures: Three Switching Types, Six Hierarchical Structures, Coefficient of Variation Lower Bound, and Discretization Plateau Effect in the k-Regime Linear Switching Model
- A near-linear upper bound for the Yellowstone permutation: a(n) <= n (ln n)^7 for every n >= 3
BibTeX
@misc{christianson2026linear,
title = {{A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm}},
author = {Nicolas Christianson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32670},
eprint = {2610.32670},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32670},
}
RIS
TY - UNPB
TI - A Linear Lower Bound for Convex Body Chasing in Every ℓ_p Norm
AU - Nicolas Christianson
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32670
UR - https://arxiv.org/abs/2610.32670
AB - We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in ℝ^d with movement costs measured in any norm. Previously, the best known lower bound valid across all norms was Ω(d^1/6), established by Papazov (2023); stronger lower bounds were known for ℓ_p norms, where Bubeck, Klartag, Lee, Li, and Sellke (2019) had established a lower bound of Ω(max{√d, d^1−1/p}). In particular, a linear lower bound was known only for the ℓ_∞ norm, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior universal and ℓ_p lower bounds for p < ∞ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio O(d) - is asymptotically optimal for every norm. Our approach is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of Ω(r^2) for requests of size O(r). We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a (2r+1)-dimensional ℓ_p vector space while approximately preserving movement costs up to a factor of O(r); the general result then follows via Milman's (1985) quotient-of-a-subspace theorem.
ER -