arXiv preprint ·
A Linear Lower Bound for Convex Body Chasing in Every $\ell_p$ Norm
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We establish an $Ω(d)$ lower bound on the competitive ratio of convex body chasing in $\mathbb{R}^d$ with $\ell_p$ movement costs for any $p \in [1, \infty)$. Previously, the best known lower bound for general $p$ was $Ω(\max\{\sqrt{d}, d^{1-1/p}\})$, established by Bubeck et al. (2019); a linear lower bound was known only for $p = \infty$, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed $p \in [1, \infty)$ and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio $O(d)$ - is asymptotically optimal for every $\ell_p$ norm. Our lower bound 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)$ in that setting. 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 vector space while approximately preserving movement costs up to a factor of $O(r)$, which establishes the lower bound.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Geometry of Limits in ReLU Function Spaces
The Geometry of Anisotropic Dilation for Optimal Regularization
Boundary Geometry Determines Optimal Shallow ReLU Approximation under Weighted Coefficient Constraints
Spacetime Quasicrystals and Computational Complexity Theory in the Road Towards Quantum Gravity
Formalizing the Intrinsic Dimension of Objective Landscapes by a Generalized Notion of Co-dimension
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.