# The Role of Dimension in the Online Chasing Problem

Hristo Papazov

###### Abstract

Let $(X,d)$ be a metric space and ${\mathcal{C}}\subseteq 2^{X}$ – a
collection of special objects. In the $(X,d,{\mathcal{C}})$-chasing problem,
an online player receives a sequence of online requests
$\\{B_{t}\\}_{t=1}^{T}\subseteq{\mathcal{C}}$ and responds with a trajectory
$\\{x_{t}\\}_{t=1}^{T}$ such that $x_{t}\in B_{t}$. This response incurs a
movement cost $\sum_{t=1}^{T}d(x_{t},x_{t-1})$, and the online player strives
to minimize the competitive ratio – the worst case ratio over all input
sequences between the online movement cost and the optimal movement cost in
hindsight. Under this setup, we call the $(X,d,{\mathcal{C}})$-chasing problem
chaseable if there exists an online algorithm with finite competitive ratio.
In the case of Convex Body Chasing (CBC) over real normed vector spaces,
Bubeck et al. [2019] proved the chaseability of the problem. Furthermore, in
the vector space setting, the dimension of the ambient space appears to be the
factor controlling the size of the competitive ratio. Indeed, recently, Sellke
[2023] provided a $d-$competitive online algorithm over arbitrary real normed
vector spaces $({\mathbb{R}}^{d},\lVert\cdot\rVert)$, and we will shortly
present a general strategy for obtaining novel lower bounds of the form
${\Omega}(d^{c}),\enspace c>0$, for CBC in the same setting.

In this paper, we also ask the more general question of whether metric-space
analogues of dimension exert a similar control on the hardness of chasing
balls over metric spaces. We answer this question in the negative for the
doubling and the Assouad dimensions of a metric space $(X,d)$. More
specifically, we prove that the competitive ratio of chasing a nested sequence
of balls can be arbitrary large for metric spaces of any doubling and Assouad
dimensions. We further prove that for any large enough $\rho\in{\mathbb{R}}$,
there exists a metric space $(X,d)$ of doubling dimension $\Theta(\rho)$ and
Assouad dimension $\rho$ such that no online selector can achieve a finite
competitive ratio in the general ball chasing regime.

##  1 Introduction and Related Work

In the Convex Body Chasing (CBC) problem for a specified real normed vector
space $({\mathbb{R}}^{d},\lVert\cdot\rVert)$, an online player/algorithm
${\mathcal{A}}$ begins at $x_{0}=0$, receives a convex body
$K_{t}\subseteq{\mathbb{R}}^{d}$ as a request at turn $t\in{\mathbb{N}}$, and
moves to a new point $x_{t}={\mathcal{A}}_{t}(K_{1},\dots,K_{t})\in K_{t}$,
incurring a movement cost $\lVert x_{t}-x_{t-1}\rVert$. After a finite
sequence of convex requests $K_{1},\dots,K_{T}$, the game ends with the player
accumulating a total cost of

${\texttt{cost}}_{T}(x_{1},\dots,x_{T})=\sum_{t=1}^{T}\lVert
x_{t}-x_{t-1}\rVert.$

Let us denote with

${\texttt{opt}}_{T}(K_{1},\dots,K_{T})=\min_{\\{y_{t}\in
K_{t}\\}_{t=1}^{T}}\sum_{t=1}^{T}\lVert y_{t}-y_{t-1}\rVert$

the optimal movement cost which a clairvoyant algorithm could achieve. With
these definitions, the competitive ratio of ${\mathcal{A}}$ becomes

$C({\mathcal{A}})=\sup\\{\frac{{\texttt{cost}}_{T}(x_{1},\dots,x_{T})}{{\texttt{opt}}_{T}(K_{1},\dots,K_{T})}:T\in{\mathbb{N}},\enspace
K_{t}\subseteq{\mathbb{R}}^{d}-\text{ convex body},\enspace
x_{t}={\mathcal{A}}_{t}(K_{1},\dots,K_{t}),\enspace\forall t\in[T]\\},$

and the algorithm ${\mathcal{A}}$ is said to be
$C({\mathcal{A}})-$competitive, where $C({\mathcal{A}})\in[1,\infty]$.
Moreover, we define the CBC problem over
$({\mathbb{R}}^{d},\lVert\cdot\rVert)$ as chaseable if there exists an online
player with a finite competitive ratio in that setting.

Notice that we tacitly assumed that ${\mathcal{A}}$ follows a deterministic
strategy. Instead, we could have allowed the selection
$x_{t}(w_{t})={\mathcal{A}}_{t}(K_{1},\dots,K_{t},w_{t})$ to also depend on
some random bits $w_{t}$. However, since
${\texttt{cost}}_{T}:({\mathbb{R}}^{d})^{T}\to{\mathbb{R}}_{\geq 0}$ is convex
due to the convexity of the norm $\lVert\cdot\rVert$, Jensen’s Inequality
implies that the deterministic algorithm ${\mathbb{E}}[{\mathcal{A}}]$ defined
through
${\mathbb{E}}[{\mathcal{A}}]_{t}={\mathbb{E}}_{w_{t}}{\mathcal{A}}_{t}$
achieves a lower total cost for any sequence of convex requests
$K_{1},\dots,K_{T}$:

${\texttt{cost}}_{T}({\mathbb{E}}_{w_{1},\dots,w_{T}}\left[(x_{1}(w_{1}),\dots,x_{T}(w_{T}))\right])\leq{\mathbb{E}}_{w_{1},\dots,w_{T}}\left[{\texttt{cost}}_{T}(x_{1}(w_{1}),\dots,x_{T}(w_{T}))\right].$

Hence, for the CBC problem, we can restrict our attention only to
deterministic online algorithms. In a more general setting of the chasing
problem, however, randomness becomes advantageous. Indeed, if we only keep the
minimal structural assumptions necessary for the chasing problem to make
sense, we arrive at the Metrical Service Systems (MSS) problem, where the
online player moves inside a metric space $(X,d)$ and the online sequence of
requests $S_{1},\dots,S_{T}$ consists of arbitrary subsets of $X$.111Note that
in the metric space setting, the performance of an online algorithm also
depends on the starting point $x_{0}$, so the competitive ratio in this case
will be calculated as a supremum over all allowed request sequences and
starting configurations. In this most abstract case of the chasing problem,
Manasse et al. [1988] proved $|X|-1$ to be the best possible competitive
ratio. Nonetheless, when the online player has access to random bits for point
selection, the papers [Bubeck et al., 2021] and [Bubeck et al., 2022]
establish matching upper and lower bounds of $\Theta(\log^{2}|X|)$ for the
best randomized competitive ratio.

Therefore, as the size of the ambient metric space $X$ increases, the
competitive ratio of the MMS problem grows prohibitively large. And clearly,
when $|X|=\infty$, no finitely competitive deterministic or randomized online
algorithm for MMS exists. However, with the introduction of some restrictions
on the family of chased-after objects ${\mathcal{C}}\subseteq 2^{X}$, the
problem setting becomes richer,222We invite the reader to consider the
introduction of [Sellke, 2023] for references to many online problems – such
as the $k-$server problem, online set covering, and scheduling – which emerge
from metrical service systems through restrictions on the family of possible
requests. and competitive algorithms begin to appear even over infinite metric
spaces.

The problem of convex body chasing over real normed vector spaces
$({\mathbb{R}}^{d},\lVert\cdot\rVert)$, first introduced by Friedman and
Linial [1993], emerged as one such convex relaxation of the MMS problem.
Friedman and Linial proved a finite competitive ratio in the two-dimensional
Euclidean setting and conjectured that a finitely competitive algorithm exists
in general. The initial efforts towards resolving the conjecture proved the
chaseability of the problem for subspace chasing [Antoniadis et al., 2016] and
nested333The adversary can request only collapsing sequences of convex bodies
$K_{1}\supseteq\dots\supseteq K_{T}$. convex body chasing [Bansa et al.,
2018]. Later work from Argue et al. Argue et al. [2019] gave an $O(d\log
d)-$competitive algorithm for nested CBC over any norm, and most recently in
the same regime, Bubeck et al. [2020] provided an algorithm, which moves to a
mixture of the Steiner point and the centroid of a convex body and achieves a
competitive ratio optimal up to an $O(\log d)$ factor over $\ell_{p}-$normed
spaces. In the general (non-nested) setting, Bubeck et al. [2019] resolved the
conjecture for Euclidean spaces by demonstrating the existence of a
$2^{O(d)}-$competitive online algorithm. Finally, Sellke [2023] and Argue et
al. [2021] independently gave an $O(\min(d,\sqrt{d\log T}))-$competitive
algorithm for convex body chasing in Euclidean spaces. Furthermore, Sellke’s
Steiner-point-based algorithm achieves competitive ratio at most $d$ for
arbitrary normed spaces, which matches the lower bound for the $\ell_{\infty}$
norm.

We stated above that the nested CBC algorithm of Bubeck et al. [2020] performs
nearly optimally in $\ell_{p}$ spaces, and we described the algorithm from
[Sellke, 2023] as the optimal for $\ell_{\infty}$ spaces. We will now discuss
existing lower bounds on the competitive ratio for nested CBC in order to
justify these claims.

######  Definition 1.1.

Let $\mathcal{D}(X,d,{\mathcal{C}})$ be the set of all all deterministic
online chasing algorithms in the $(X,d,{\mathcal{C}})$ setting. We define the
competitive ratio of the $(X,d,{\mathcal{C}})$-chasing problem as the
following infimum:

$R(X,d,{\mathcal{C}})=\inf_{{\mathcal{A}}\in\mathcal{D}(X,d,{\mathcal{C}})}C({\mathcal{A}}).$

We similarly define $\hat{R}(X,d,{\mathcal{C}})$ as the competitive ratio of
the nested $(X,d,{\mathcal{C}})$-chasing problem.

Note that we will only write $R(X)$ and $\hat{R}(X)$ when the distance metric
$d$ and the family of chased-after sets ${\mathcal{C}}$ are clear from
context. Also, notice that trivially $R(X)\geq\hat{R}(X)$.

Now, by sequentially considering the faces of the unit hypercube

$F_{0}=\\{\mathbf{z}\in{\mathbb{R}}^{d}:\lVert z\rVert_{\infty}=1\\},\enspace
F_{t}=F_{t-1}\cap\\{\mathbf{z}\in{\mathbb{R}}^{d}:z_{t}=\pm 1\\},\enspace
t\geq 1,$

depending on which one stands farther away from the online selector at time
$t$, Friedman and Linial [1993] showed a lower bound of $d$ on the competitive
ratio for the nested $\ell_{\infty}$ case. The same construction leads to a
lower bound of $d^{1-\frac{1}{p}}$ for $d-$dimensional $\ell_{p}$ spaces,
$p\geq 1$. Apart from these unit-cube lower bounds, Bubeck et al. [2020] used
the existence of a Hadamard matrix in dimensions $d=2^{k}$ to prove that
$\hat{R}(\ell_{p}^{d})\geq{\Omega}(\sqrt{d})$, where
$\ell_{p}^{d}=({\mathbb{R}}^{d},\lVert\cdot\rVert_{p})$. Thus, the following
lower bounds on the nested CBC competitive ratio have been proven to hold:

  * •

$\hat{R}(\ell_{p}^{d}\geq{\Omega}(d^{1-\frac{1}{p}})$ for $d\in{\mathbb{N}}$,
$p\in[0,\infty]$;

  * •

$\hat{R}(\ell_{p}^{d}\geq{\Omega}(\max(d^{1-\frac{1}{p}},\sqrt{d}))$ for
$d=2^{k},\enspace k\in{\mathbb{N}}$, $p\in[0,\infty]$.

In particular, no lower bounds have been established for non-$\ell_{p}$ norms.

### Our Results.

As our first main result, we develop a general strategy for transferring
bounds on the competitive ratio of the chasing problem from one setting
$(X,d_{X},{\mathcal{C}}_{X})$ to another $(Y,d_{Y},{\mathcal{C}}_{Y})$. We
then connect this general approach with several results from Convex Geometry
to prove the following theorem, which generalizes the aforementioned lower
bound from Bubeck et al. [2020] and provides the first known lower bound on
nested CBC for arbitrary normed spaces:

######  Theorem 1.2.

For every $d\in{\mathbb{N}}$ and $p\in[0,\infty]$, no online algorithm can
achieve a competitive ratio better than
${\Omega}(\max(d^{1-\frac{1}{p}},\sqrt{d}))$ in the nested convex body chasing
problem over $\ell_{p}^{d}$. Furthermore, no online algorithm can achieve a
competitive ratio better than ${\Omega}(d^{1/6})$ in the nested convex body
chasing problem over arbitrary normed spaces
$({\mathbb{R}}^{d},\lVert\cdot\rVert)$.

Our result combined with Sellke’s algorithm [Sellke, 2023] proves that the
competitive ratio of CBC satisfies the inclusion
$R({\mathbb{R}}^{d},\lVert\cdot\rVert)\in\left[{\Omega}(d^{1/6}),d\right]$ for
any norm $\lVert\cdot\rVert$. Hence, the vector-space dimension $d$ appears to
be the quantity controlling the hardness of CBC.

As our second research direction, we investigate the question of whether
metric-space analogues of dimension exert a similar control over the
competitive ratio $R(X,d,{\mathcal{C}})$ in the general
$(X,d,{\mathcal{C}})$-chasing problem. Of course, the family of chased-after
objects ${\mathcal{C}}$ can no longer be the set of convex bodies since
convexity requires a linear structure. We also want to impose some meaningful
restrictions on ${\mathcal{C}}$ in order for the problem be interesting
because setting ${\mathcal{C}}=2^{X}$ brings us back to the already resolved
metrical service systems problem. Hence, we decide to consider closed balls –
an object native to any metric space – as a metric-space substitute for
convex-body requests.

######  Definition 1.3.

Given $x\in X$ and $R\geq 0$, the closed ball $\bar{B}(x,R)$ is defined as the
set of points within radius $R$ from $x$:

$\bar{B}(x,R)=\\{y\in X:d(x,y)\leq R\\}.$

We will use $B(x,R)$ to denote the open ball of radius $R$ around $x$.

We can now set ${\mathcal{C}}=\\{\bar{B}(x,R):x\in X,\enspace R\geq 0\\}$ to
fully specify the Ball Chasing (BC) problem and the Nested Ball Chasing (NBC)
problem with competitive ratios $R(X)\geq\hat{R}(X)$, which we will try to
characterize in terms of the ${\gamma}-$cover dimension and the Assouad
dimension of $X$. We will postpone the definitions of the ${\gamma}-$cover and
Assouad dimensions to Section 3 and proceed with stating our NBC hardness
results.

######  Theorem 1.4.

For any ${\gamma}>1$ and $\rho,N>0$, there exists a metric space $(X,d)$ with
${\gamma}-$cover dimension ${\texttt{dim}}_{\gamma}(X)=\Theta_{\gamma}(\rho)$
such that no deterministic online algorithm can achieve a competitive ratio
better than $N$ in the nested ball chasing problem over $X$. In other words,
$R(X)\geq\hat{R}(X)\geq N$.

######  Remark 1.5.

We use the notation $\Theta_{\gamma}(\cdot),\enspace{\Omega}_{\gamma}(\cdot)$,
and $O_{\gamma}(\cdot)$ to indicate that the hidden constants depend only on
${\gamma}$.

######  Theorem 1.6.

There exists an absolute constant $c>0$ such that for every $\rho\geq c$,
there exists a countable metric space $(X,d)$ with Assouad dimension
${\texttt{dim}}_{A}(X)=\rho$ such that no deterministic online algorithm can
achieve a finite competitive ratio in the nested ball chasing problem over
$X$. In other words, $R(X)=\hat{R}(X)=\infty$.

##  2 Competitive Ratio Bounds through Metric Embeddings

Our goal in this section will be to prove Theorem 1.2 by developing a general
method for transferring competitive-ratio information between different
settings of the chasing problem. Without further ado, let
$(X,d_{X},{\mathcal{C}}_{X})$ and $(Y,d_{Y},{\mathcal{C}}_{Y})$ be two
distinct chasing environments.

######  Lemma 2.1.

Suppose there exists a bi-Lipschitz metric embedding $f:(X,d_{X})\to(Y,d_{Y})$
with distortion $D(f)={\texttt{Lip}}(f){\texttt{Lip}}(f^{-1})$such that
$\forall K\in{\mathcal{C}}_{X},\enspace f(K)\in{\mathcal{C}}_{Y}$. Then, every
deterministic online algorithm
${\mathcal{A}}_{Y}\in\mathcal{D}(Y,d_{Y},{\mathcal{C}}_{Y})$ with competitive
ratio $C(A_{Y})$ induces a deterministic online algorithm
${\mathcal{A}}_{X}\in\mathcal{D}(X,d_{X},{\mathcal{C}}_{X})$ through $f^{-1}$
such that $C(A_{X})\leq C(A_{Y})D(f)$.

###### Proof.

We define the deterministic online algorithm
${\mathcal{A}}_{X}\in\mathcal{D}(X,d_{X},{\mathcal{C}}_{X})$ the following
way. Let $y_{0}=f(x_{0})$ be the starting point in the $Y-$space. Given a
sequence of online requests $\\{K_{t}\\}_{t=1}^{T}\subseteq{\mathcal{C}}_{X}$,
we run ${\mathcal{A}}_{Y}$ on the embedded request sequence
$\\{f(K_{t})\\}_{t=1}^{T}\subseteq{\mathcal{C}}_{Y}$ to obtain an online
trajectory $\\{y_{t}\\}_{t=0}^{T}$. We then define the action of
${\mathcal{A}}_{X}$ at time $t$ as the movement towards point
$x_{t}=f^{-1}(y_{t})$. Now,

${\texttt{cost}}_{T}(x_{0},x_{1},\dots,x_{T})=\sum_{t=1}^{T}d(x_{t},x_{t-1})\leq{\texttt{Lip}}(f^{-1})\sum_{t=1}^{T}d(y_{t},y_{t-1})={\texttt{Lip}}(f^{-1}){\texttt{cost}}_{T}(y_{0},y1,\dots,y_{T}).$

Moreover,

$\displaystyle{\texttt{opt}}_{T}(x_{0},K_{1},\dots,K_{T})$
$\displaystyle=\inf_{\\{a_{t}\in K_{t}\\}_{t=1}^{T}}\sum_{t=1}^{T}\lVert
a_{t}-a_{t-1}\rVert$ $\displaystyle\geq\inf_{\\{a_{t}\in
K_{t}\\}_{t=1}^{T}}\sum_{t=1}^{T}\frac{1}{{\texttt{Lip}}(f)}\lVert
f(a_{t})-f(a_{t-1})\rVert$
$\displaystyle\geq\frac{1}{{\texttt{Lip}}(f)}\inf_{\\{b_{t}\in
f(K_{t})\\}_{t=1}^{T}}\sum_{t=1}^{T}\lVert b_{t}-b_{t-1}\rVert$
$\displaystyle=\frac{1}{{\texttt{Lip}}(f)}{\texttt{opt}}_{T}(f(x_{0}),f(K_{1}),\dots,f(K_{T})).$

Hence,

$\displaystyle C({\mathcal{A}}_{X})$ $\displaystyle=\sup_{x_{0}\in
X,T\in{\mathbb{N}},\\{K_{t}\\}_{t=1}^{T}\subseteq{\mathcal{C}}_{X}}\frac{{\texttt{cost}}_{T}(x_{0},x_{1},\dots,x_{T})}{{\texttt{opt}}_{T}(x_{0},K_{1},\dots,K_{T})}$
$\displaystyle\leq\sup_{x_{0}\in
X,T\in{\mathbb{N}},\\{K_{t}\\}_{t=1}^{T}\subseteq{\mathcal{C}}_{X}}{\texttt{Lip}}(f){\texttt{Lip}}(f^{-1})\frac{{\texttt{cost}}_{T}(y_{0},y_{1},\dots,y_{T})}{{\texttt{opt}}_{T}(f(x_{0}),f(K_{1}),\dots,f(K_{T}))}$
$\displaystyle\leq\sup_{y_{0}\in
Y,T\in{\mathbb{N}},\\{S_{t}\\}_{t=1}^{T}\subseteq{\mathcal{C}}_{Y}}D(f)\frac{{\texttt{cost}}_{T}(y_{0},y_{1},\dots,y_{T})}{{\texttt{opt}}_{T}(y_{0},S_{1},\dots,S_{T})}$
$\displaystyle=D(f)C({\mathcal{A}}_{Y}).$

∎

Now, let $f:(X,d_{X})\to(Y,d_{Y})$ be a bi-Lipschitz metric embedding which
maps ${\mathcal{C}}_{X}$ to ${\mathcal{C}}_{Y}$. For any algorithm
${\mathcal{A}}_{Y}\in\mathcal{D}(Y,d_{Y},{\mathcal{C}}_{Y})$, let us denote
with $f^{-1}({\mathcal{A}}_{Y})\in\mathcal{D}(X,d,{\mathcal{C}})$ the online
algorithm obtained by the procedure in the above lemma. Then,

$\displaystyle R(X)$
$\displaystyle=\inf_{{\mathcal{A}}_{X}\in\mathcal{D}(X,d,{\mathcal{C}})}C({\mathcal{A}}_{X})$
$\displaystyle\leq\inf_{f^{-1}({\mathcal{A}}_{Y}):{\mathcal{A}}_{Y}\in\mathcal{D}(Y,d_{Y},{\mathcal{C}}_{Y})}C(f^{-1}({\mathcal{A}}_{Y}))$
$\displaystyle\leq\inf_{{\mathcal{A}}_{Y}\in\mathcal{D}(Y,d_{Y},{\mathcal{C}}_{Y})}D(f)C(A_{Y})$
$\displaystyle=D(f)R(Y).$

Similarly, $\hat{R}(X)\leq D(f)\hat{R}(Y)$. Furthermore, if the metric
embedding $f$ is bijective such that $f({\mathcal{C}}_{X})={\mathcal{C}}_{Y}$,
then

$\boxed{\frac{1}{D(f)}\leq\frac{R(X)}{R(Y)}\leq
D(f)\enspace\enspace\enspace\text{and}\enspace\enspace\enspace\frac{1}{D(f)}\leq\frac{\hat{R}(X)}{\hat{R}(Y)}\leq
D(f).}$ (1)

Thus, metric embeddings which also preserve chasing families allow us to
transfer competitive ratio upper and lower bounds between different problem
settings. Let us see how we can apply this approach to derive novel lower
bounds on the competitive ratio for convex body chasing over different norms.

When $(X,\lVert\cdot\rVert_{X})$ and $(Y,\lVert\cdot\rVert_{Y})$ are
$d-$dimensional real normed vector spaces and the chased-after objects are
convex sets, we will focus on non-singular linear maps $T:X\to Y$ as our
choice for metric embeddings since linear maps conserve convexity under the
image and preimage operations. We will denote with $\lVert
T\rVert=\sup_{x:\lVert x\rVert_{X}=1}\lVert Tx\rVert_{Y}$ and $\lVert
T^{-1}\rVert=\sup_{y:\lVert y\rVert_{Y}=1}\lVert T^{-1}y\rVert_{X}$ the
operator norms of the bijective linear maps $T$ and $T^{-1}$. Hence,
$D(T)=\lVert T\rVert\lVert T^{-1}\rVert$. Now, the Banach-Mazur distance444We
refer the reader to [Tomczak-Jaegermann, 1989] for a thorough introduction to
the geometry of Banach spaces and the properties of the Banach-Mazur distance.
between the $d-$dimensional Banach spaces $X$ and $Y$ is defined as

$d_{BM}(X,Y)=\inf\\{D(T)|T:X\to Y-\text{isomorphism}\\},$

and we conclude that

$\boxed{\frac{1}{d_{BM}(X,Y)}\leq\frac{R(X)}{R(Y)}\leq
d_{BM}(X,Y)\enspace\enspace\enspace\text{and}\enspace\enspace\enspace\frac{1}{d_{BM}(X,Y)}\leq\frac{\hat{R}(X)}{\hat{R}(Y)}\leq
d_{BM}(X,Y).}$ (2)

The unit-cube construction from [Friedman and Linial, 1993] gave us the lower
bound $\hat{R}(\ell_{p}^{d})\geq d^{1-\frac{1}{p}}$, where $p\geq 1$. Hence,
for any $d-$dimensional Banach space $X$, inequality (2) implies

$\hat{R}(X)\geq\frac{d^{1-\frac{1}{p}}}{d_{BM}(X,\ell_{p}^{d})}.$

Let $\mathcal{B}_{d}$ be the set of all $d-$dimensional Banach spaces. As a
starting point of our search for convenient Banach-Mazur distances to
$\ell_{p}$ spaces, we recall John’s Theorem [John, 1948] (see [Ball et al.,
1997] for proof and discussion), which states that
$\sup_{X\in\mathcal{B}_{d}}d_{BM}(X,\ell_{2}^{d})=\sqrt{d}$. Unfortunately,
this bound leads to the trivial inequality $\hat{R}(X)\geq 1$. However, bounds
on the Banach-Mazur distance to $\ell_{\infty}^{d}$ prove more
fruitful.555Tikhomirov [2019] proved the best known lower bound
$\inf_{X\in\mathcal{B}_{d}}d_{BM}(X,\ell_{\infty}^{d})\geq d^{5/9}\log^{-C}d$
for some universal constant $C$. Indeed, Giannopoulos [1995] gave the
asymptotic upper bound
$\sup_{X\in\mathcal{B}_{d}}d_{BM}(X,\ell_{\infty}^{d})\leq O(d^{5/6})$, which
was later improved to the precise estimate
$\sup_{X\in\mathcal{B}_{d}}d_{BM}(X,\ell_{\infty}^{d})\leq 2d^{5/6}$ by
Youssef [2014]. Thus, we arrive at the nontrivial lower bound on the
competitive ratio of CBC over arbitrary Banach spaces

$R(X)\geq\hat{R}(X)\geq\frac{1}{2}d^{1/6},\enspace\forall
X\in\mathcal{B}_{d}.$

Furthermore, when dealing with $\ell_{p}$ norms, Propostion 37.6 from
[Tomczak-Jaegermann, 1989] states that for any dimension $d\in{\mathbb{N}}$
and $1\leq p<2<q\leq\infty$,
$d_{BM}(\ell_{p}^{d},\ell_{q}^{d})=\Theta(d^{\alpha})$, where
${\alpha}=\max(\frac{1}{p}-\frac{1}{2},\frac{1}{2}-\frac{1}{q})$. Therefore,
setting $q=\infty$, we obtain $d_{BM}=\Theta(\sqrt{d})$. Thus, inequality (2)
entails

$R(\ell_{p}^{d})\geq\hat{R}(\ell_{p}^{d})\geq{\Omega}(\sqrt{d}),\enspace\forall
p\in[1,2),$

which concludes the proof of Theorem 1.2.

##  3 Metric-Dimension Preliminaries

Having proved that the vector-space dimension controls the hardness of CBC, we
proceed to investigate the effect of metric covering dimensions on the
competitive ratio of the ball chasing problem. However, before we jump into
the proofs of our main theorems, we first need to set up some notation and
preliminary observations.

Given a metric space $(X,d)$ and a subset $E\subseteq X$, we denote with
$N_{r}(E)$ the smallest number of open balls in $X$ with radius at most $r$
that cover $E$.

######  Definition 3.1.

For ${\gamma}>1$, the ${\gamma}-$cover constant of a metric space $(X,d)$ is
the smallest integer $\lambda_{\gamma}$ such that for every $R>0$ and every
$x\in X$, the open ball $B(x,R)$ can be covered by at most $\lambda_{\gamma}$
open balls of radius $R/{\gamma}$. In other words,

$\lambda_{\gamma}=\sup_{x\in X,R>0}N_{R/{\gamma}}(B(x,R)).$

The ${\gamma}-$cover dimension of $X$ is then defined as
$\rho_{\gamma}=\log_{\gamma}\lambda_{\gamma}$ and denoted as
${\texttt{dim}}_{\gamma}(X)$. Whenever ${\texttt{dim}}_{\gamma}(X)<\infty$,
the metric space $X$ is said to be doubling.

The above definition seemingly generalizes the doubling dimension
(${\gamma}=2$) introduced in [Gupta et al., 2003]. However, the
${\gamma}-$cover dimension still suffers from the inherent arbitrariness of
the choice of ${\gamma}$ and should be considered as a precise quantity only
up to a constant factor. Indeed, notice that for $1<{\alpha}<{\beta}$,

$\lambda_{\alpha}\leq\lambda_{\beta}\leq\lambda_{\alpha}^{\left\lceil\log_{\alpha}{\beta}\right\rceil},$

so

${\texttt{dim}}_{\alpha}(X)\leq{\texttt{dim}}_{\beta}(X)<(1+\log_{\beta}{\alpha}){\texttt{dim}}_{\alpha}(X).$

Intuitively, the ${\texttt{dim}}_{\gamma}(X)$ expresses the extent to which
the size of the space increases as you travel further away and thus captures a
relative measure of the dimension of the space. We make this intuition
concrete through Lemma 3.2 which relates the ${\gamma}-$cover dimension of
$(R^{d},\lVert\cdot\rVert)$ to the vector-space dimension $d$. The proofs of
all lemmas in this preliminaries section can be found in Appendix A.666We make
no claims about the novelty of the preliminary lemmas, and we note that Lemma
3.2, Lemma 3.6, and Lemma 3.7 can be found in [Heinonen, 2001] and [Matoušek,
2013].

######  Lemma 3.2.

Let ${\gamma}>1$ and let $(X,d)=({\mathbb{R}}^{d},\lVert\cdot\rVert)$. Then,
${\texttt{dim}}_{\gamma}(X)=\Theta_{\gamma}(d)$.

Next, we demonstrate the robustness of the ${\gamma}-$cover dimension under
the submetric relation – a property shared with the ordinary vector-space
dimension.

######  Lemma 3.3.

Let ${\gamma}>1$ and let $(Y,d|_{Y})$ be a metric subspace of $(X,d)$. Then,
${\texttt{dim}}_{\gamma}(Y)\leq O_{\gamma}({\texttt{dim}}_{\gamma}(X))$.

As a final property of the ${\gamma}-$cover dimension that will be useful in
our proofs, we show an upper bound on the ${\gamma}-$cover dimension of the
union of two distant metric subspaces.

######  Lemma 3.4.

Let ${\gamma}>1$ and let $(Z,d)$ be a metric space such that $Z=X\cup Y$. If
$d(X,Y)\geq 2{\gamma}\max\\{\texttt{diam}(X),\texttt{diam}(Y)\\}$, then
${\texttt{dim}}_{\gamma}(Z)=\max\\{{\texttt{dim}}_{\gamma}(X),{\texttt{dim}}_{\gamma}(Y)\\}$.

Now, we introduce a more precise metric dimension called the Assouad dimension
[Assouad, 1983] or the (metric) covering dimension.777We invite the reader to
consider Chapter 10 of [Heinonen, 2001], Chapter 3 of [Matoušek, 2013], and
[Fraser, 2022] for an in-depth discussion of doubling metric spaces and the
properties of the Assouad dimension.

######  Definition 3.5.

The Assouad dimension of a metric space $(X,d)$ is defined as the infimal
$\rho_{A}\geq 0$ for which there exists a constant $C>0$ such that for all
radii $0<r<R$ and all $x\in X$,

$N_{r}(B(x,R))\leq C\left(\frac{R}{r}\right)^{\rho_{A}}.$

We will denote the Assouad dimension of $X$ with ${\texttt{dim}}_{A}(X)$.

Notice that finite metric spaces have Assouad dimension 0. Also, not
surprisingly:

######  Lemma 3.6.

The metric spaces with finite Assouad dimension are precisely the doubling
metric spaces. Moreover, whenever $(X,d)$ is doubling and ${\gamma}>1$,
${\texttt{dim}}_{A}(X)\leq{\texttt{dim}}_{\gamma}(X)$.

Furthermore, the Assouad dimension perfectly agrees with the vector-space
dimension.

######  Lemma 3.7.

Let $(X,d)=({\mathbb{R}}^{d},\lVert\cdot\rVert)$. Then,
${\texttt{dim}}_{A}(X)=d$.

We conclude the preliminaries section with an intermediate-value theorem for
the Assouad dimension that we will use in the proof of Theorem 1.6.

######  Theorem 3.8.

Let $(X,d)$ be a doubling metric space.

  * •

Chen et al. [2020] proved that for any $\rho\in[0,{\texttt{dim}}_{A}(X)]$,
there exists a metric subspace $(Y,d|_{Y})\subseteq(X,d)$ such that
${\texttt{dim}}_{A}(Y)=\rho$.

  * •

Wang and Wen [2016] proved that when $X$ is bounded and
$\rho\in[0,{\texttt{dim}}_{A}(X))$, then there exists a countable metric
subspace $(Y,d|_{Y})\subseteq(X,d)$ such that ${\texttt{dim}}_{A}(Y)=\rho$.

##  4 Arbitrary Bad Competitive Ratio in Nested Ball Chasing

See 1.4

###### Proof.

We are given as input $\rho>0$ and $N>0$, and we want to construct a metric
space $(X,d)$ with ${\texttt{dim}}_{\gamma}(X)=\Theta_{\gamma}(\rho)$ such
that $\hat{R}(X)\geq N$.

### Defining the Metric Space.

The metric space $(X,d)$ will consist of two parts: an $n-$point set
$P=\\{p_{1},p_{2},\dots,p_{n}\\}$ of "nearby" points and a set of $2^{n}-2$
"faraway" points $Z=\\{z_{S}:S\subseteq[n],\enspace S\neq\emptyset,[n]\\}$
that the adversary will use for ball centers. The hard chasing instances will
be designed in such a way that the online player starts at a point in $P$ and
is forced to traverse the whole of $P$ before the nested request sequence
terminates. The points in $Z$ will be placed so far away from $P$ that
crossing over to them will immediately inflict a competitive ratio worse than
$N$. Thus, the strategy of the online adversary will be to adaptively
construct a sequence of nested balls $B_{1}\supset\dots\supset B_{n-1}$ such
that at time $t\geq 1$, $B_{t}\setminus B_{t-1}=x_{t-1}$ – the point currently
occupied by the online player. This way, the online player will necessarily
travel a distance of at least $(|P|-1)d_{\min}(P)$, while the optimal path
$d(x_{0},x_{n})$ would have length at most $d_{\max}(P)$. Hence, no
deterministic online algorithm can achieve competitive ratio better than
$(|P|-1)/\Delta(P)$, where $\Delta(P)=d_{\max}(P)/d_{\min}(P)$ is the aspect
ratio of the metric subspace $P$. Therefore, we now have the concrete goal of
designing a metric space $(X,d)$ where the ${\gamma}-$cover dimension has no
control over the size of $(|P|-1)/\Delta(P)$. We proceed with the description
of $(X,d)$.

Figure 1: $(X,d)$ with ${\texttt{dim}}_{\gamma}(x)=\Theta_{\gamma}(\rho)$ and
$\hat{R}(X)\geq N$.

Let $P\subseteq{\mathbb{R}}^{k}$ be a $k-$dimensional grid with unit distance
between adjacent points and $D$ points on each side of the grid. Hence,
$n=D^{k}$. The grid $P$ will be endowed with the $\ell_{\infty}$ metric, so
$d(p_{i},p_{j})\in\\{1,2,\dots,D-1\\},\enspace\forall i\neq j\in[n]$. Next, we
specify the ball-centers set $Z$. For each $S\subseteq[n]:\enspace
S\neq\emptyset,[n]$, we place a point $z_{S}$ on a line (in arbitrary order)
at unit distance from the neighboring points. Thus, the distance between the
first and the last element on the ball-centers line becomes $2^{n}-3$. Then,
for each $j\in[n]$ and $S\subseteq[n]:\enspace S\neq\emptyset,[n]$, we let

$d(z_{S},p_{j})=\begin{cases}R+1&\text{if }j\in S;\\\
R&\text{otherwise},\end{cases}$

where we set
$R={\gamma}2^{n+1}>2{\gamma}\max(\texttt{diam}(P),\texttt{diam}(Z))$.

### Proof of Valid Metric.

Clearly, our metric, as defined, satisfies symmetry and positivity, so we only
need to check that the triangle inequality holds. Since the triangle
inequality holds separately within $P$ and $Z$, we just need to convince
ourselves that no triangle with vertices both in $P$ and $Z$ violates the
triangle inequality.

### Nested Sequence of Balls.

Since $R>\texttt{diam}(Z)$, we get that $Z\subseteq B(z_{S},R)$, and thus

$B(z_{S},R)=Z\cup\\{x_{j}:j\notin S\\}.$

Now, let $S_{t}$ be the set of indices of points in $P$ that the online player
has visited prior to the ball request at time $t\geq 1$. Then, the adaptive
adversary can pick $B(z_{S_{t}},R)$ and force the online player to move to
another point in $P$ or $Z$. If the online player decides to jump to $Z$, the
request sequence terminates. Otherwise, the adversary continues to request
balls of the form $B(z_{S_{t+1}},R)=B(z_{S_{t}},R)\setminus\\{x_{t}\\}$ until
all points in $P$ have been exhausted.

### Bounding the Doubling Dimension.

We proceed with the bounding of the ${\gamma}-$cover dimension of $X$.
Clearly, the line $(Z,d|_{Z})$ can be isometrically embedded into
$({\mathbb{R}},|\cdot|)$, so by Lemma 3.3, ${\texttt{dim}}_{\gamma}(Z,d)\leq
O_{\gamma}({\texttt{dim}}_{\gamma}({\mathbb{R}},|\cdot|))$. Now, Lemma 3.2
tells us that
${\texttt{dim}}_{\gamma}({\mathbb{R}},|\cdot|)=\Theta_{\gamma}(1)$, so we
conclude that ${\texttt{dim}}_{\gamma}(Z,d)\leq O_{\gamma}(1)$. Again, by
Lemma 3.2,
${\texttt{dim}}_{\gamma}({\mathbb{R}}^{k},\lVert\cdot\rVert_{\infty})=\Theta_{\gamma}(k)$,
so Lemma 3.3 yields ${\texttt{dim}}_{\gamma}(P)\leq
O_{\gamma}({\texttt{dim}}_{\gamma}(k))$. Therefore, Lemma 3.4 helps us
establish that ${\texttt{dim}}_{\gamma}(X)\leq O_{\gamma}(k)$.

On the other hand, if we consider a point $x$ at the interior of the grid $P$,
the ball $B(x,\frac{2{\gamma}-1}{{\gamma}})$ will contain $3^{k}$ points, but
every ball of radius $\frac{2{\gamma}-1}{{\gamma}^{2}}$ will contain precisely
a single point. Hence, $\lambda_{\gamma}(P)\geq 3^{k}$, which implies that
${\texttt{dim}}_{\gamma}(P)\geq{\Omega}_{\gamma}(k)$. Now, Lemma 3.4 entails
${\texttt{dim}}_{\gamma}(X)\geq{\Omega}_{\gamma}(k)$, so overall
${\texttt{dim}}_{\gamma}(X)=\Theta_{\gamma}(k)$. Thus, we let
$k=\left\lceil\rho\right\rceil+1$, which concludes the proof that
${\texttt{dim}}_{\gamma}(X)=\Theta_{\gamma}(\rho)$.

### Bounding the Competitive Ratio.

As a last step in the proof, we lower-bound the competitive ratio
$\hat{R}(X)$. Note that due to the design of the nested sequence of requests,
the optimal traveled distance never exceeds $d_{\max}(P)=D-1$. Thus, if the
online player decides to jump to $Z$ at some point in time, the competitive
ratio of the chasing sequence becomes greater than $R/D>>(|P|-1)/\Delta(P)$.
Otherwise, as we discussed in the beginning of the section, the competitive
ratio becomes at least $(|P|-1)/\Delta(P)>D^{k-1}>D^{\rho}$. Now, since $D$
represents a free parameter, we can pick $D$ large enough so that
$\hat{R}(X)>D^{\rho}\geq N$.

∎

######  Remark 4.1.

Exactly the same construction shows that for any $N>0$ and $\rho\geq 1$, there
exists a metric space $(X,d)$ of KR-dimension888See [Karger and Ruhl, 2002]
for the precise definition and origin of the KR-dimension. $\Theta(\rho)$ such
that $\hat{R}(X)\geq N$.

##  5 Greedy Upper Bound on $\hat{R}(X)$ for Nested Ball Chasing

In this section, we show a simple greedy algorithm for the NBC problem over
arbitrary metric spaces $(X,d)$ (without doubling assumptions), which matches
up to a constant factor the lower bound on $\hat{R}(X)$ that we proved in the
doubling setting. Indeed, given a starting point $x_{0}$ and a nested request
sequence $\mathcal{S}=\\{B_{1},\dots,B_{T}\\}$, let us define
$P_{x_{0},\mathcal{S}}=B(x_{0},d^{*})$ as the problem-space set, where
$d^{*}=d(x_{0},B_{T})$ stands for the optimal traveled distance. With this
notation, the proof of Theorem 1.4 demonstrated that there exists a metric
space $(X,d)$ with fixed ${\gamma}-$cover dimension such that

$\hat{R}(X)\geq\sup_{x_{0}\in X,\mathcal{S}-\text{ nested ball
sequence}}\frac{|P_{x_{0},\mathcal{S}}|-1}{\Delta(P_{x_{0},\mathcal{S}})}.$

The theorem below shows once more that contrary to the situation in the
vector-space setting, a fixed ${\gamma}-$cover dimension does not make the NBC
problem easier over metric spaces.

######  Theorem 5.1.

Let $(X,d)$ be an arbitrary metric space on which we consider the nested ball
chasing problem. Then, with the above notation,

$\hat{R}(X)\leq\sup_{x_{0}\in X,\mathcal{S}-\text{ nested ball
sequence}}2|P_{x_{0},\mathcal{S}}|-1.$

###### Proof.

Let us consider a greedy online algorithm which starts at $x_{0}$ and responds
with $x_{t}=\operatorname*{argmin}_{x\in B_{t}}d(x,x_{0})$ – the closest point
to $x_{0}$ in $B_{t}$. WLOG, assume $x_{t-1}\notin B_{t}$. (Otherwise, the
algorithm simply skips the step without incurring any penalty.) Notice that
$d^{*}=d(x_{0},B_{T})=d(x_{0},x_{T})\geq d(x_{0},x_{t})$ for $t\in[T]$. Hence,
using the triangle inequality, we bound the online cost as follows:

$d(x_{0},x_{1})+\dots+d(x_{T-1},x_{T})\leq
d(x_{0},x_{T})+2\sum_{t=1}^{T-1}d(x_{0},x_{t})\leq(2T-1)d^{*}.$

Thus, the greedy algorithm achieves a competitive ratio of at most $2T-1$.
Furthermore, we know that $T$ must be bounded by
$|B(x_{0},d^{*})|=|P_{x_{0},\mathcal{S}}|$ since the assumption $x_{t-1}\notin
B_{t}$ guarantees that each step evicts an element of $B(x_{0},d^{*})$.

∎

##  6 Infinite Competitive Ratio for Any Fixed Assouad Dimension

We will now show that enforcing a finite Assouad dimension on a metric space
$(X,d)$ proves to be too liberal of a constraint for the NBC problem to be
chaseable. Hence, the question of finding a condition which allows for
meaningful ball chasing in the absence of linear structure remains open.

See 1.6

###### Proof.

We want to build a metric space $(X,d)$ with ${\texttt{dim}}_{A}(X)=\rho$ and
$\hat{R}(X)=\infty$. The construction of that space will be carried out in two
phases. The first phase will use induction to glue together countably many
copies of the metric space we designed for Theorem 1.4. This gluing procedure
will ensure that $\hat{R}(X)=\infty$. Then, in phase two, we will attach the
result from phase one to a subset of a normed vector space of proper
dimension, which will guarantee that ${\texttt{dim}}_{A}(X)=\rho$. Let us
begin.

### Phase I.

Let us fix some ${\gamma}>1$. For every $N\in{\mathbb{N}}$, Theorem 1.4,
provides the existence of a metric space $(X_{N},d_{N})$ with NBC competitive
ratio $\hat{R}(X_{N})\geq N$ and ${\gamma}-$cover dimension
${\texttt{dim}}_{\gamma}(X_{N})=\Theta_{\gamma}(1)=c$, where $c$ represents
the absolute constant in the statement of Theorem 1.6. We set
$(Y_{1},D_{1})=(X_{1},d_{1})$, and for $N\geq 2$, we construct the metric
spaces $(Y_{N},D_{N})$ iteratively by gluing together $(X_{N},d_{N})$ and
$(Y_{N-1},D_{N-1})$ in the following way:

  * •

The distances between pairs of points both inside either $X_{N}$ or $Y_{N-1}$
remain unchanged.

  * •

$\forall x\in X_{N},\enspace\forall y\in Y_{N-1}$, we let
$D_{N}(x,y)=R_{N}=2{\gamma}\max(\texttt{diam}(X_{N}),\texttt{diam}(Y_{N-1}))$.

Clearly, the triangle inequality holds inside every so-constructed space
$(Y_{N},D_{N})$. Moreover, a simple inductive argument in conjunction with
Lemma 3.4 yields ${\texttt{dim}}_{\gamma}(Y_{N})=c$. Finally, since the
competitive ratio $\hat{R}(\cdot)$ is monotonically increasing under the
superset operation, we get obtain $\hat{R}(Y_{N})\geq N$. Therefore, the
following two identities hold for the metric space
$(Y,D)=\bigcup_{N=1}^{\infty}(Y_{N},D_{N})$:

  * •

${\texttt{dim}}_{\gamma}(Y)=c$;

  * •

$\hat{R}(Y)=\infty$.

Figure 2: $(X,d)$ with ${\texttt{dim}}_{\mathcal{A}}(x)=\rho$ and
$\hat{R}(X)=\infty$.

### Phase II.

Let us fix some $m\in{\mathbb{N}}$ such that $m>\rho\geq c$. We construct the
metric space $(Z,d)$ by gluing $(Y,D)$ and some arbitrary normed space
$({\mathbb{R}}^{m},\lVert\cdot\rVert)$ together in the following way:

  * •

The distances between pairs of points both inside either $Y$ or
${\mathbb{R}}^{m}$ remain unchanged.

  * •

$\forall N\in{\mathbb{N}},\enspace\forall x\in X_{N},\enspace\forall
y\in{\mathbb{R}}^{m}$, we let $d(x,y)=R_{N}+\lVert y\rVert$.

We only need to check that the triangle inequality holds between the following
triplets:

  * •

$M>N$, $x\in X_{M}$, $y\in X_{N}$, $z\in{\mathbb{R}}^{m}$: $d(x,y)=R_{M}$,
$d(y,z)=R_{N}+\lVert z\rVert$, $d(z,x)=R_{M}+\lVert z\rVert$;

  * •

$x,y\in X_{N}$, $z\in{\mathbb{R}}^{m}$: $d(x,y)<R_{N}$, $d(y,z)=R_{N}+\lVert
z\rVert$, $d(z,x)=R_{N}+\lVert z\rVert$;

  * •

$x\in X_{N}$, $y,z\in{\mathbb{R}}^{m}$: $d(x,y)=R_{N}+\lVert y\rVert$,
$d(y,z)=\lVert y-z\rVert$, $d(z,x)=R_{N}+\lVert z\rVert$.

Hence, $(Z,d)$ is a well-defined metric space.

Now, let $M=B(0,r)\subset Z$ be the open ball of radius $r>0$ around the
origin of ${\mathbb{R}}^{m}$, and notice that when $r<R_{1}$, then
$M\subset{\mathbb{R}}^{m}$. From the proof of Lemma 3.7, we know that
${\texttt{dim}}_{A}(M)=m$, and from Theorem 3.8, we can find a countable
subset $L$ of $M$ such that ${\texttt{dim}}_{A}(L)=\rho$. We can finally
define the countable metric space promised in the beginning of the proof. Let
$X=Y\cup L$ and let $X$ inherit the metric distance $d$ from $Z$. Since
$\dim_{A}(L)=\rho$ and since there exists an open ball in $X$ which contains
precisely $L$, we conclude that ${\texttt{dim}}_{A}(X)\geq\rho$.

In order to prove that ${\texttt{dim}}_{A}(X)\leq\rho$, let us consider an
open ball $B(x,R)$ for some $x\in X$ and let $R>r>0$. If $B(x,R)\subseteq L$,
then there exists a constant $C_{L}$ such that $N_{r}(B(x,R))\leq
C_{L}\left(\frac{R}{r}\right)^{\rho}$. On the other hand, if there exists
$y\in B(x,R)\cap Y$, then $B(x,R)\subseteq B(y,2R)$. Hence, by Lemma 3.6,
there exists a constant $C_{Y}$ such that

$N_{r}(B(x,R))\leq N_{r}(B(y,2R))\leq C_{Y}\left(\frac{2R}{r}\right)^{c}\leq
2^{\rho}C_{Y}\left(\frac{R}{r}\right)^{\rho}.$

Therefore, ${\texttt{dim}}_{A}(X)=\rho$. Moreover, since $(Y,D)\subset(X,d)$,
$\hat{R}(X)=\infty$. ∎

## References

  * Antoniadis et al. [2016] Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato.  Chasing convex bodies and functions.  In _LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings 12_ , pages 68–81. Springer, 2016.
  * Argue et al. [2019] CJ Argue, Sébastien Bubeck, Michael B Cohen, Anupam Gupta, and Yin Tat Lee.  A nearly-linear bound for chasing nested convex bodies.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 117–122. SIAM, 2019.
  * Argue et al. [2021] CJ Argue, Anupam Gupta, Ziye Tang, and Guru Guruganesh.  Chasing convex bodies with linear competitive ratio.  _Journal of the ACM (JACM)_ , 68(5):1–10, 2021\.
  * Assouad [1983] Patrice Assouad.  Plongements lipschitziens dans $\mathbb{R}^{n}$.  _Bulletin de la Société Mathématique de France_ , 111:429–448, 1983.
  * Ball et al. [1997] Keith Ball et al.  An elementary introduction to modern convex geometry.  _Flavors of geometry_ , 31(1–58):26, 1997.
  * Bansa et al. [2018] Nikhil Bansa, Martin Böhm, Marek Eliáš, Grigorios Koumoutsos, and Seeun William Umboh.  Nested convex bodies are chaseable.  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1253–1260. SIAM, 2018.
  * Bubeck et al. [2019] Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, and Mark Sellke.  Competitively chasing convex bodies.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 861–868, 2019.
  * Bubeck et al. [2020] Sébastien Bubeck, Bo’az Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke.  Chasing nested convex bodies nearly optimally.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1496–1508. SIAM, 2020.
  * Bubeck et al. [2021] Sébastien Bubeck, Michael B Cohen, James R Lee, and Yin Tat Lee.  Metrical task systems on trees via mirror descent and unfair gluing.  _SIAM Journal on Computing_ , 50(3):909–923, 2021\.
  * Bubeck et al. [2022] Sébastien Bubeck, Christian Coester, and Yuval Rabani.  The randomized $k$-server conjecture is false!  _arXiv preprint arXiv:2211.05753_ , 2022.
  * Chen et al. [2020] Changhao Chen, Meng Wu, and Wen Wu.  Accessible values for the assouad and lower dimensions of subsets.  2020\.
  * Fraser [2022] Jonathan M Fraser.  Assouad dimension and fractal geometry: updates on open problems.  2022\.
  * Friedman and Linial [1993] Joel Friedman and Nathan Linial.  On convex body chasing.  _Discrete & Computational Geometry_, 9(3):293–321, 1993.
  * Giannopoulos [1995] AA Giannopoulos.  A note on the banach-mazur distance to the cube.  In _Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1992–94_ , pages 67–73. Springer, 1995.
  * Gupta et al. [2003] Anupam Gupta, Robert Krauthgamer, and James R Lee.  Bounded geometries, fractals, and low-distortion embeddings.  In _44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings._ , pages 534–543. IEEE, 2003.
  * Heinonen [2001] Juha Heinonen.  _Lectures on analysis on metric spaces_.  Springer Science & Business Media, 2001.
  * John [1948] Fritz John.  Extremum problems with inequalities as subsidiary conditions.  _Interscience Publishers, Inc., New York. January_ , 8:187–204, 1948.
  * Karger and Ruhl [2002] David R Karger and Matthias Ruhl.  Finding nearest neighbors in growth-restricted metrics.  In _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_ , pages 741–750, 2002.
  * Manasse et al. [1988] Mark Manasse, Lyle McGeoch, and Daniel Sleator.  Competitive algorithms for on-line problems.  In _Proceedings of the twentieth annual ACM symposium on Theory of computing_ , pages 322–333, 1988.
  * Matoušek [2013] Jirı Matoušek.  Lecture notes on metric embeddings.  Technical report, Technical report, ETH Zürich, 2013.
  * Sellke [2023] Mark Sellke.  Chasing convex bodies optimally.  In _Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2020-2022_ , pages 313–335. Springer, 2023.
  * Tikhomirov [2019] Konstantin Tikhomirov.  On the banach–mazur distance to cross-polytope.  _Advances in Mathematics_ , 345:598–617, 2019.
  * Tomczak-Jaegermann [1989] Nicole Tomczak-Jaegermann.  Banach-mazur distances and finite-dimensional operator ideals.  _(No Title)_ , 1989.
  * Wang and Wen [2016] Wen Wang and Shengyou Wen.  An intermediate-value property for assouad dimension of metric space.  _Topology and its Applications_ , 209:120–133, 2016.
  * Youssef [2014] Pierre Youssef.  Restricted invertibility and the banach–mazur distance to the cube.  _Mathematika_ , 60(1):201–218, 2014.

##  Appendix A Proofs of Metric-Dimension Lemmas

We first note that the ${\gamma}-$cover dimension agrees up to a constant with
the ordinary definition of dimension of a normed vector space.

See 3.2

###### Proof.

We first need to define the concept of an ${\varepsilon}-$net:

######  Definition A.1.

Given a metric space $(X,d)$, a set of points $\mathcal{N}\subseteq X$ is
called an ${\varepsilon}-$net of $X$ if
$X=\bigcup_{x\in\mathcal{N}}B(x,{\varepsilon})$ and
$d(x,y)\geq{\varepsilon},\enspace\forall x\neq y\in\mathcal{N}$. Note that
${\varepsilon}-$nets can be constructed greedily over $X$ by starting with
$\mathcal{N}=\emptyset$ and repeatedly adding an arbitrary point from
$X\setminus\bigcup_{x\in\mathcal{N}}B(x,{\varepsilon})$ to $\mathcal{N}$ until
$X$ is exhausted.

Now we can proceed with our proof. Let $r>0$ and ${\varepsilon}\in(0,1)$. We
will prove that every open ball of radius $r$ can be covered by at most
$(1+2/{\varepsilon})^{d}$ balls of radius ${\varepsilon}r$. Let
$x\in{\mathbb{R}}^{d}$ and let $\mathcal{N}$ be an ${\varepsilon}r-$net of
$B(x,r)$. Then, $B(x,r)\subseteq\bigcup_{y\in\mathcal{N}}B(y,{\varepsilon}r)$.
Note that the balls $B(y,{\varepsilon}r/2)$ are all disjoint, so

$\text{vol}\left(\bigcup_{y\in\mathcal{N}}B(y,{\varepsilon}r/2)\right)=|\mathcal{N}|({\varepsilon}r/2)^{d}\text{vol}({\mathbb{B}})$

where ${\mathbb{B}}$ is the unit ball in
$({\mathbb{R}}^{d},\lVert\cdot\rVert)$. Now,

$\bigcup_{y\in\mathcal{N}}B(y,{\varepsilon}r/2)\subseteq\bigcup_{y\in
B(x,r)}B(y,{\varepsilon}r/2)\subseteq B(x,r+{\varepsilon}r/2)$

so $|\mathcal{N}|({\varepsilon}r/2)^{d}\text{vol}({\mathbb{B}})\leq
r^{d}(1+{\varepsilon}/2)^{d}\text{vol}({\mathbb{B}})$. Hence,
$|\mathcal{N}|\leq(1+2/{\varepsilon})^{d}$. This allows us to conclude that
$\lambda_{\gamma}\leq(1+2{\gamma})^{d}$, or equivalently,
${\texttt{dim}}_{\gamma}(X)\leq d\log_{\gamma}(1+2{\gamma})$.

Similarly, we have that
$\text{vol}(B(x,r))=r^{d}\text{vol}(\mathbb{B})={\gamma}^{d}\text{vol}(B(y,r/{\gamma}))$
for all $y$, so $\lambda_{\gamma}\geq{\gamma}^{d}$, thus proving that
${\texttt{dim}}_{\gamma}(X)\geq d$. Therefore, we conclude that
$d\leq{\texttt{dim}}_{\gamma}(X)\leq d\log_{\gamma}(1+2{\gamma})$. ∎

See 3.3

###### Proof.

Let us denote with $B_{Y}(\cdot,\cdot)$ and $B_{X}(\cdot,\cdot)$ the open
balls in $Y$ and $X$, respectively. Hence, $\forall y\in Y,\enspace r>0$,
$B_{Y}(y,r)\subseteq B_{X}(y,r)$, which can be covered by
$\lambda_{\gamma}^{\left\lceil\log_{\gamma}(2{\gamma})\right\rceil}$ open
balls in $X$ of radius $r/(2{\gamma})$. Thus, we have

$B_{Y}(y,r)\subseteq B_{X}(y,r)\subseteq\bigcup_{x^{\prime}\in
X^{\prime}}B_{X}(x^{\prime},r/(2{\gamma}))$

where
$|X^{\prime}|\leq\lambda_{\gamma}^{\left\lceil\log_{\gamma}(2{\gamma})\right\rceil}$.
If we define $Y^{\prime}$ to to be a set of arbitrarily chosen $y^{\prime}\in
B_{Y}(y,r)$ from every nonempty $B_{X}(x^{\prime},r/(2{\gamma}))$, then
clearly, $B_{X}(x^{\prime},r/(2{\gamma}))\subseteq B_{X}(y^{\prime},r/2)$.
Hence,
$\lambda_{\gamma}(Y)\leq\lambda_{\gamma}^{\left\lceil\log_{\gamma}(2{\gamma})\right\rceil}$,
so ${\texttt{dim}}_{\gamma}(Y)<{\texttt{dim}}_{\gamma}(X)(2+\log_{\gamma}2)$.
∎

See 3.4

###### Proof.

Let $\lambda_{X}$ and $\lambda_{Y}$ be the ${\gamma}-$cover constants of $X$
and $Y$. If an open ball $B(z,R)$ is completely contained in $X$ or $Y$, then
$N_{R/{\gamma}}(B(z,R))\leq\max(\lambda_{X},\lambda_{Y})$. On the other hand,
if $B(z,R)$ contains points $x\in X$ and $y\in Y$, then $R\geq d(X,Y)/2$.
Therefore, $R/{\gamma}\geq\max\\{\text{diam}(X),\text{diam}(Y)\\}$, so the
whole space can be covered by $B(x,R/{\gamma})$ and $B(y,R/{\gamma})$.
Therefore, the doubling constant of
$\lambda_{g}(Z)\leq\max\\{\lambda_{X},\lambda_{Y}\\}$. ∎

See 3.6

###### Proof.

Fix some ${\gamma}>1$ and let $(X,d)$ be a metric space. Clearly,
$\dim_{A}(X)<\infty$ implies that for every $R>0$ and $x\in X$,

$N_{R/{\gamma}}(B(x,R))\leq C{\gamma}^{\dim_{A}(X)},$

so
${\texttt{dim}}_{\gamma}(X)\leq{\texttt{dim}}_{A}(X)+\log_{\gamma}C<\infty$.
On the other hand, if ${\texttt{dim}}_{\gamma}(X)<\infty$, then we have two
cases to consider. First, let $x\in X,\enspace R>0$, and let $r=R/{\alpha}$
such that ${\alpha}\in(0,{\gamma})$. Then,

$N_{R/{\alpha}}(B(x,R))\leq N_{R/{\gamma}}(B(x,R))=\lambda_{\gamma}.$

Second, if ${\alpha}\geq{\gamma}$, then

$N_{R/{\alpha}}(B(x,R))\leq\lambda_{\gamma}^{\left\lceil\log_{\gamma}{\alpha}\right\rceil}<\lambda_{\gamma}{\alpha}^{{\texttt{dim}}_{\gamma}(X)}.$

Hence, ${\texttt{dim}}_{A}(X)\leq{\texttt{dim}}_{\gamma}(X)$. ∎

See 3.7

###### Proof.

In the proof of Lemma 3.2, we showed that for any $x\in{\mathbb{R}}^{d}$ and
$0<r<R$,

$\left(\frac{R}{r}\right)^{d}\leq
N_{r}(B(x,R))\leq\left(1+2\frac{R}{r}\right)^{d}<3^{d}\left(\frac{R}{r}\right)^{d}.$

∎