---
author:
- |
    Mark Sellke\
    Stanford University
bibliography:
- 'cbc\_FSP\_update.bib'
title: Chasing Convex Bodies Optimally
---

Introduction
============

Let $K_1,K_2,\dots, K_N$ be a sequence of convex sets inside $\mathbb R^d$. The *convex body chasing* problem asks an online player starting at $x_0$ to choose online a sequence of points $x_n\in K_n$ minimizing the total cost $\sum_{n=1}^N ||x_n-x_{n-1}||$. The problem is framed in terms of competitive analysis, meaning that the player aims for a finite competitive ratio between his cost and the cost of best offline sequence he could have chosen in hind-sight.

Chasing convex bodies was originally proposed in [@friedmanlinial] as a convex version of general set chasing problems on metric spaces, including the famous $k$-server problem. An algorithm with finite competitive ratio was given in the original paper for the already non-trivial $d=2$ case, and was conjectured to exist for larger $d$. The best lower bounds were obtained by essentially using the faces of a hypercube, which shows that the competitive ratio is at least $\sqrt{d}$ in Euclidean space and at least $d$ in $\ell^{\infty}$.

Following a lack of progress on the full conjecture, restricted cases such as chasing subspaces were studied (e.g. [@2016chasing]). A notable restricted case is chasing *nested* convex bodies, where the convex sets $K_1\supseteq K_2\supseteq \dots $ are required to decrease. Nested chasing was introduced in [@nestedarechaseable] and solved rather comprehensively in [@ABCGL] and then [@chasingnested2018]. The latter work gave a nearly optimal algorithm for all $\ell^p$ spaces, as well as a memoryless $\min(d,O(\sqrt{d\log N}))$ competitive algorithm for Euclidean spaces based on the *Steiner point* of a convex body.

Some time after chasing convex bodies was posed, an equivalent functional variant called *chasing convex functions* was given. In chasing convex functions, the request is a convex function $f_n:\mathbb R^d\to\mathbb R^+$ instead of a convex set. The cost function now consists of two additive parts: the movement cost $\sum_{n=1}^N ||x_n-x_{n-1}||$ from before, and a service cost $\sum_{n=1}^N f_n(x_n)$. Chasing convex functions subsumes chasing convex bodies by considering for any body $K$ the function $f^K$ which is $0$ on $K$ and $+\infty$ off of $K$. At the start of subsection \[subsec:reductions\] we in fact explain why we can use a finite $f^K$. Conversely, convex function chasing in $\mathbb R^d$ can be reduced to convex body chasing in $\mathbb R^{d+1}$ up to a constant factor by alternating requests of the epigraphs $\{(x,y)\in \mathbb R^d\times \mathbb R: y\geq f_n(x)\}$ of the convex functions $f_n$ with the hyperplane $\mathbb R^d\times \{0\}$.

The functional perspective opens more possibility for applications. Indeed, chasing convex functions was originally considered for efficiently powering data centers [@datacenters]. More abstractly, it resembles the well-studied framework of online convex optimization (see e.g. [@hazan2016introduction] for an introduction). Instead of aiming for a small additive regret against the best single action, we now aim for a multiplicative guarantee against the best *changing* sequence of actions. The movement costs arise naturally from this point of view: the player’s movement cost is an upper bound for the advantage of seeing $f_n$ before choosing $x_n$, so long as the functions $f_n$ are Lipschitz. Some restricted cases of chasing convex function have also been studied. For example, [@1dSOCO] studies the precise competitive ratio in $1$ dimension, while [@SOCObalanced] shows a dimension-free competitive ratio when the cost functions increase linearly away from their minima.

New Results
-----------

Recently, in our joint work with S. Bubeck, Y.T. Lee, and Y. Li [@chasingconvex2018] we gave the first algorithm achieving a finite competitive ratio of convex body chasing, which used induction on the dimension. However they obtained an exponential upper bound $2^{O(d)}$, leaving a large gap.

We give an upper bound of $d$ for the competitive ratio of chasing convex bodies in a general normed space, which is tight for $\ell^{\infty}$, and nearly matches the $\sqrt{d}$ lower bound for Euclidean space. More fully, our main result is:

\[thm:main\] In any $d$-dimensional normed space there exists a $d+1$ competitive algorithm for chasing convex functions and a $d$ competitive algorithm for chasing convex bodies. In the former case, the service cost is $1$-competitive against the total cost of the offline optimum. Moreover in Euclidean space this algorithm is $O(\sqrt{d\log N})$-competitive if there are $N$ requests.

The proof is inspired by our joint work with S. Bubeck, B. Klartag, Y.T. Lee, and Y. Li [@chasingnested2018] on chasing nested convex bodies. It is shown there that moving to the new body’s *Steiner point*, a stable center point of any convex body defined long ago in [@steineroriginal], gives total movement at most $d$ starting from the unit ball in $d$ dimensions. It is easy to reduce the general problem to this setting up to a constant factor. (They only gave the result for Euclidean space, but we explain in Subsection \[subsec:generalnormedspace\] why it works in general.) We generalize their argument by defining the functional Steiner point of any convex function, intuitively a stable approximate minimum. We show that for continuous time convex function chasing, following the functional Steiner point of the work function (which encodes the total cost of all requests so far) achieves competitive ratio $d+1$. This easily implies the same result in the discrete time setting. Finally, we show that the same algorithm gives a nearly optimal $\sqrt{d\log N}$ upper bound for Euclidean space, following the same result for nested chasing in [@chasingnested2018].

After this work was completed, we were informed that C.J. Argue, Anupam Gupta, Guru Guruganesh, and Ziye Tang jointly obtained similar results for this problem in [@AGGT]. These works were initially posted to the ArXiv simultaneously. Later we added Section \[sec:unify\] which unifies the two solutions.

Problem Setup
=============

Notations and Conventions
-------------------------

We assume the starting position is $x_0=0$. Because we switch between the continuous and discrete time settings, we use variables the $T,t,s$ to denote real times and $N,n$ to denote integer times. We denote by $\dashint_{x\in X} f(x)dx$ the average value $\frac{\int_{x\in X} f(x)dx}{\int_{x\in X} 1dx}$ of $f(x)$ on $X$. We denote by $B_1$ the unit ball in $\mathbb R^d$, and $\mathbb S^{d-1}$ the unit sphere.

Equivalence of Bodies and Functions, and Continuous Time Formulation {#subsec:reductions}
--------------------------------------------------------------------

First we argue that chasing convex bodies is a special case of chasing convex functions, even though the functions are require to be finite. The reduction from bodies to functions goes by taking $f_n(x)=f^{K_n}$ for $f^K(x):=3d(x,K)$. Now, we claim that both the player and the offline optimum should always play $x_n\in K_n$ for the sequence $(f_1,f_2,\dots)$ of function requests. The reason is simply that both the player and the offline optimum only improve their performance by moving to the closest point in $K_n$ and back. Indeed, if $\hat x_n\notin K_n$ is a potential choice for $x_n$, this modification incurs a movement cost of $2d(\hat x_n,K_n)$ but reduces the service cost by $3d(\hat x_n,K_n)$.

The main part of our proof is more natural in continuous time. In continuous time chasing convex functions, the adversary gives a piecewise continuous family of functions $f_t$, and the player constructs a bounded variation path $(x_t)$ online. (The paths constructed by the algorithm will be continuous, but the optimal path might be piecewise continuous.) The loss of the player is

$$\int_{t=0}^T f_t(x_t)+||x'_t||dt.$$

Here the integral of $||x'_t||$ is understood to mean the total variation of the path $x_t$ in the case of singularities or discontinuities. The goal is again to achieve a finite competitive ratio.

For the continuous time problem we require that the functions $f_t(x)$ be convex in $x$, piecewise continuous in $t$, and finite everywhere. We now show how to reduce the original discrete time problem to the continuous time problem.

\[prop:continuoustodiscrete\]

Suppose $f_1,f_2,\dots, f_N$ is a sequence of requests for discete-time chasing convex functions. For $t\in [0,N]$ let $f_t=f_{n}$ for $t\in [n-1,n)$. If a $C$-competitive algorithm for the continuous time requests $f_t$ exists, then a $C$-competitive algorithm for the discrete time requests exists. In fact, the discretized algorithm has lower movement cost and lower service cost.

It is easy to see that the continuous and discrete time problems have the same offline optimum value. Given a solution path $x_t$ to the continuous time problem, when the player sees a discrete time request $f_n$ he knows what his continuous time path for $t\in [n-1,n)$ would be, and can simply move to the lowest-cost point on this path defined by $x_{t_n}$ for $t_n=\min_{t\in [n-1,n)} f_n(x_t)$. It is easy to see that the sequence $(x_{t_1},\dots, x_{t_n})$ has both a smaller movement and service cost than the continuous path $(x_t)_{t\in [0,T]}$, hence the result.

Outline of the Paper
--------------------

In section \[sec:setup\], we recall the Steiner point and define the functional Steiner point. We also dicuss the work function and its concave conjugate. In section \[sec:linearCR\] we establish the $d+1$ competitive ratio for chasing convex functions. For conceptual and notational ease, in these two sections we only consider the Euclidean setting. In section \[sec:extra\], we prove the $O(\sqrt{d\log N})$ upper bound for the Euclidean case and finally explain why the linear estimates hold in any normed space.

Functional Steiner Point and Work Function {#sec:setup}
==========================================

We recall here the definition of the Steiner point of a convex body, and extend it to convex functions. The Steiner point of a convex body $K$ is the functional Steiner point of the function which is $0$ on $K$ and infinite outside $K$.

Given a convex body $K\subseteq \mathbb R^d$, the Steiner point $s(K)$ is defined in the following two equivalent ways:

1.  For any vector $v\in {\mathbb{R}}^d$, let $f_K(v)=\arg\max_{x\in K}(v\cdot x) $ be the extremal point in $K$ in direction $v$. Then compute the average of this extremal point for a random vector in the unit ball: $$s(K)=\dashint_{v\in B^{d}_1(0)} f_K(v) dv.$$

2.  For unit vector $\theta\in \mathbb{S}^{d-1}\subset {\mathbb{R}}^d$, let $h_K(\theta)=\max_{x\in K}(\theta\cdot x)$ be the support function for $K$ in direction $\theta$, and compute $$s(K)=d\dashint_{\theta\in \mathbb{S}^{d-1}} h_K(\theta)\theta d\theta.$$

The definitions are equivalent because of the divergence or Gauss-Green theorem and the identity $\nabla h_K(v)=f_K(v)$. The factor $d$ comes from the discrepancy in total measure of the ball and the sphere.

Note that for a convex body the functions $h_K$ and $f$ are homogenous so e.g. we could average over the same set in the two definitions. However for the functional Steiner point there is a difference, so we maintain the separation. To define functional Steiner point for a general convex function, we generalize the support function $h_K$ to the concave conjugate, which coincides in the case of convex bodies. Recall that for a convex function $W$, the concave conjugate $W^*(v)$ is the *concave* function defined by

$$W^*(v)=\min_w \left(W(w)-v^T w\right)$$

We also define

$$v^*=\arg\min_w \left(W(w)-v^T w\right)$$

to be the conjugate point to $v$ with respect to $W_t$. Geometrically $v^*$ is the input with $\nabla W(v^*))=v$.

Now we can define the functional Steiner point.

Given a convex function $W:\mathbb R^d\to\mathbb R^+$ with $W^*(v)$ finite for all $v\in B_1$, the functional Steiner point $s(W)$ is defined in the following two equivalent ways:

1.  $$s(W)=\dashint_{v\in B_1} v^* dv.$$

2.  $$s(W)= -d\dashint_{\theta\in \mathbb{S}^{d-1}} W^*(\theta)\theta d\theta.$$

As with the original Steiner point, these definitions coincide because of the divergence or Gauss-Green theorem and the concave conjugate characterization $\nabla W^*(v) = -v^*.$ Technically, the value $v^*$ might not be well-defined for some $v$ values, but by Alexandrov’s theorem $W^*$ has a second derivative almost everywhere, which implies $v^*$ is well-defined for almost all $v$.

To avoid confusion we note that technically, specializing our functional Steiner point to the nested case does not yield the Steiner point of $K_n$ at time $n$. The reason is that the ordinary Steiner point $s(K_n)$ is the functional Steiner point of $f_{K_n}(x):=d(x,K_n)$ while the work function (defined in the next subsection) is $W_n(x)=||x-x_0||.$

Properties of the Work Function
-------------------------------

Our algorithm is given by staying at the Steiner point of the work function, so here we give the basic properties of the work function. The work function $W_t(x)$ at any time $t$ is defined as the smallest cost OPT could have at time $t$ while starting at $x_0=0$ and ending up at $x_t=x$.

Given a family $\{f_s(x):s\in [0,t]\}$ of functions convex in $x$ and piecewise continuous in $s$, the work function $W_t(x)$ is defined by

$$\begin{aligned}
W_t(x)=&  \inf_{x_s:[0,t]\to\mathbb R^d, x_0=0} \int_0^t f_s(x_s)+||x'_s||ds\\
=& \inf_{x_s:[0,t]\to\mathbb R^d,x_0=0} \Gamma_t(x_s).\end{aligned}$$

Here we allow $x_s$ to be any function of bounded variation with the correct value $x_0=0$, and interpret $\int_0^t ||x'_s||ds$ as the total variation of the path. We call $\Gamma_t(x_s)$ the *cost* of the path $x_s$.

Note that our definition allows movement after the final request, so we do not necessarily need to pay $f_t(x)$ in $W_t(x)$ but we have to pay $f_t(y)+||y-x||$ for some $y$.

In the case that $f_s(x)$ is piecewise constant in $s$ (which is all we need for the discrete problem), it is rather obvious that the best offline continuous time strategy coincides with the best offline discrete time strategy. For mathematical completeness, we argue that the infimum is attained in the definition above in general. Indeed, given a constant $C$ larger than the infimum, consider the set of paths with total variation at most $C$, starting from $x_0=0$. Such paths can be parametrized instead by their distributional derivatives, which are exactly the vector-valued Radon measures on $[0,t]$ with total variation at most $C$. Such measures form a compact set in the usual e.g. Wasserstein topology, and the total variation is a lower semicontinuous functional, meaning that it only decreases under limits of paths. Therefore, given the infimum value defining the work function, we can take a sequence of paths with value converging to the infimum, and find a subsequential limit in the topology just described. Such a limit must exactly attain the infimum.

We will denote by $W^*_t(\cdot)$ the concave conjugate of $W_t$, and $v^*_t$ the position with $\nabla W_t(v^*_t)=v$. We record the following proposition summarizing the properties of the work function.

The work function $W_t$ and its concave conjugate $W^*_t$ satisfy:

1.  $W_0(x)=||x||.$

2.  $W_t(x)$ is increasing in $t$ and is convex for all fixed $t$.

3.  $W^*_0(v)=0$ whenever $|v|\leq 1$.

4.  $W^*_t(v)$ is increasing in $t$ and concave for fixed $t$.

5.  $W^*_t(v)$ is non-negative and finite whenever $|v|\leq 1.$

It is clear that $W_0(x)=||x||$, and that $W_t(x)$ is increasing in $t$. Convexity holds because the entire optimization problem is convex in path space, and implies that $W^*_t(\cdot)$ is concave. The computation of $W^*_0$ is clear, and since $W_t$ is increasing so is $W^*_t$. $W^*_t(v)$ is finite for all $|v|\leq 1$ because $W_t(0)$ (say) is finite.

We also prove the following easy lemma which is key to the upcoming analysis.

\[lem:boundondual\]

For all $t$ we have:

$$\max_{|\theta|\leq 1} W^*_t(\theta)\leq  2\cdot \min_{x}W_t(x)$$

$$\dashint_{\theta\in\mathbb S^{d-1}} W^*_t(\theta) d\theta \leq \min_{x} W_t(x).$$

$$\dashint_{v\in B_1} W^*_t(v) dv \leq \min_{x} W_t(x).$$

Define

$$OPT_t=\arg\min_x W_t(x).$$

Since $W^*_t$ is defined as a minimum, we can upper bound $W^*_t$ by plugging in $OPT_t$ to the minimization problem. This gives

$$W^*_t(\theta) \leq W_T(OPT_t)-\theta\cdot OPT_t.$$

Since $|OPT_t|\leq |W_t(OPT_t)|$ all claims are clear.

Alternatively, since $\min_x W_t(x)=W_t^*(0)$, the latter two claims are just the concavity of $W_t^*$.

The next lemma allows us to compute the time derivative of $W^*_t(v)$ for fixed $v$ with $|v|<1$. The proof is an exercise in real analysis which we leave to the appendix.

\[lem:derivativeWt\]

For any $\delta>0$ suppose $f_s(x)$ is jointly continuous in $(s,x)$ and convex in $x$ for all $(s,x)\in [t,t+\delta)\times \mathbb R^d$. Then for almost all fixed $v$ with $|v|<1$ we have

$$\frac{d}{dt} \left(W^*_t(v)\right) = f_t(v^*_t).$$

Proof of Linear Competitive Ratio {#sec:linearCR}
=================================

Our algorithm is to take $x_t=s(W_t)$. We call this the continuous time functional Steiner point, and call the discretization obtained from Proposition \[prop:continuoustodiscrete\] the discrete time functional Steiner point. We will use the first (primal) definition of the functional Steiner point to control the functional cost and the second (dual) definition to control the movement cost. Note that the offline optimum we are competing with is exactly $\min_xW_T(x)=W^*_T(0)$. In this section we prove the following main theorem.

\[thm:linearCR\]

The continuous time functional Steiner point $x_t=s(W_t)$ is $d+1$ competitive in Euclidean space. In particular it satisfies:

1.  The movement cost of $x_t$ is $d$-competitive:

    $$\int_{t=0}^T ||x'_t||dt \leq d\cdot\min_x W_t(x).$$

2.  The service cost of $x_t$ is $1$-competitive:

    $$\int_{t=0}^T f_t(x_t)dt \leq \min_x W_t(x).$$

\[cor:discretelinearCR\]

In $d$-dimensional Euclidean space, the discrete time functional Steiner point is $d+1$ competitive for chasing convex functions and $d$ competitive for chasing convex bodies.

This follows from Proposition \[prop:continuoustodiscrete\] and the fact that chasing convex bodies has $0$ service cost.

We start with part $1$, which parallels the proof of Theorem 2.1 in [@chasingnested2018]. From the dual definition of $s(W_t)$ and the fact that $W^*_t$ increases with $t$, the total movement is bounded by

$$\int_{t=0}^T ||x'_t||dt \leq d\dashint_{\theta\in\mathbb S^{d-1}} W^*_T(\theta) d\theta .$$

By the lemma we just proved we know $d\dashint_{\theta\in\mathbb S^{d-1}} W^*_T(\theta) d\theta \leq d\min_x W_T(x)$. This completes the proof of part $1$.

Now we turn to part $2$, estimating the service cost. Using the first definition of the functional Steiner point and convexity of $f_t$, we know that

$$f_t(s(W_t)) \leq \dashint_{v\in B_1} f_t(v^*_t)dv .$$

Integrating in time and using Lemma \[lem:derivativeWt\] gives the bound on the service cost:

$$\begin{aligned}
\int_{t=0}^T f_t(x_t)dt \leq & \dashint_{v\in B_1} \int_{t=0}^T f_t(v_t^*) dtd\theta \\
\leq & \dashint_{v\in B_1}\int_{t=0}^T \frac{d}{dt} \left(W^*_t(v)\right) dt dv\\
\leq & \dashint_{v\in B_1} W^*_T(v)-W^*_0(v) dv\\
= & \dashint_{v\in B_1} W^*_T(v) dv\\
\leq & \min_x W_T(x).\end{aligned}$$

This finishes the proof.

Although computing the functional Steiner point might appear to require detailed knowledge of the functions $f_t$, only local data of $f_t$ is essential for the guarantee. Indeed, in the continuous time setting the player can achieve the same guarantee only given access to $f_t(x_t)$ and $\nabla f_t(x_t)$. This is because the player can always lower bound $f_t$ by

$$f_t(x)\geq \tilde f_t(x):= \max_x(f_t(x_t)+\nabla f_t(x_t)^T (x-x_t),0).$$

In general, if the player is $C$-competitive against some functions $\tilde f_t$ with $\tilde f_t(x_t)=f_t(x_t)$ and $\tilde f_t(x)\leq f_t(x)$ for all $x$, it is clear that the player is $C$-competitive overall. Because our algorithm yields a continuous path, only this first order information is required to follow the functional Steiner point for $\tilde f_t$, and hence be competitive with $f_t$ as well.

Similar remarks apply in the discrete time case, where we are given $f_n(x_{n-1})$ and $\nabla f_n(x_{n-1})$ before choosing $x_n$. The only difference is that we now pay an additive cost of $2Ld$ in the competitive ratio under the assumption that the functions $f_n$ are $L$-Lipschitz. The reason is that here we have to make discontinuous jumps, and we don’t know the function value $f_n(x_n)$ when choosing $x_n$. When $f_n$ are Lipschitz we can bound this error using the movement cost.

Nearly Optimal Bound and Arbitrary Normed Space {#sec:extra}
===============================================

In this section we prove the two extensions claimed in Theorem \[thm:main\]. First we prove the $O(\sqrt{d\log N})$ upper bound in Euclidean space using concentration of measure, following [@chasingnested2018]. Second, we define the functional Steiner point in any normed space, and explain why it is $d+1$ competitive in this greater generality.

Nearly Linear Competitive Ratio for Discrete Requests {#sec:discretetime}
-----------------------------------------------------

Here we prove the upper bound $O(\sqrt{d\log N})$ for the discrete time problem. The proof is by concentration of measure on the sphere and follows Theorem 3.3 of [@chasingnested2018]. The intuition is: suppose $\int_{\theta\in\mathbb S^{d-1}}W^*_n(\theta)-W^*_{n-1}(\theta)d\theta$ is significant. Then the movement from $s(W_n)\to s(W_{n+1})$ is an integral of pushes by different $\theta$ vectors in the second definition of functional Steiner point. By concentration of measure, these pushes will mostly decorrelate when the total amount of pushing is non-trivially large.

For any $0\leq \varepsilon <1$, the set $$\{{v\in B_1}:v_{i}\geq \varepsilon\}$$ occupies at most $e^{-d \varepsilon^{2}/2}$ fraction of the unit ball.

\[lem:hardtomove\]

Suppose that $|W^*_n(\theta)-W^*_{n-1}(\theta)|\leq C$ for all $\theta$, and set $$\lambda=\dashint_{v\in B_1} W^*_n(v)-W^*_{n-1}(v)dv.$$ Then we have the estimate

$$||s(W_n)-s(W_{n-1})||_2 = O\left(\lambda C\sqrt{d \log\left(\frac{C}{\lambda}\right)}\right).$$

Note that $||s(W_n)-s(W_{n-1})||_2=\sup_{|w|=1}w^T\left(s(W_n)-s(W_{n-1})\right)$. So we fix a unit vector $w$ and estimate the inner product. Setting $g_n(\theta)=W^*_n(\theta)-W^*_{n-1}(\theta)>0$, this inner product is

$$w^T\left(s(W_n)-s(W_{n-1})\right)= d\dashint_{\theta\in \mathbb S^{d-1}} g_n(\theta) w^T\theta.$$

Now, $g_n(\theta)\in [0,C]$ for all $\theta$ and $g_n$ has average value $\lambda$. Just given these two constraints, the integral is maximized when $g_n(\theta)=C$ for the set of $\theta$ values most correlated with $w$, and $g_n(\theta)=0$ otherwise. The conclusion now follows easily.

For discrete time convex function chasing with requests $f_1,\dots,f_N$, the discrete time functional Steiner point algorithm is $\min(d,O(\sqrt{d\log N})$ competitive.

Call the continuous path $(x_t)_{t\in [0,N]}$ so the discrete path is $x_{t_n}$ for $t_n\in [n-1,n)$. As proved in the proposition, we know the movement and service costs for this discrete path are at most that of the continuous path, so we only need to establish the $O(\sqrt{d\log N})$ competitive ratio on the movement of the discrete path.\
Recall that by Lemma \[lem:boundondual\] we have

$$\max_{|\theta|\leq 1} W^*_N(\theta)\leq  2\cdot \min_{x}W_N(x).$$

Therefore, we can apply Lemma \[lem:hardtomove\] with $C=2\cdot \min_{x}W_N(x)$ to the movement $|x_{t_n}-x_{t_{n-1}}|$ at each step. Set $\lambda_n=\int_{\theta\in\mathbb S^{d-1}}\left(W^*_{t_n}(\theta)-W^*_{t_{n-1}}(\theta)\right)d\theta$. By Lemma \[lem:hardtomove\] the total movement is at most the maximum value of

$$d^{1/2}\sum_{n\leq N} \lambda_n C\sqrt{\log\left(\frac{C}{\lambda_n}\right)}$$

subject to the constraint that the $\lambda_n$ are all non-negative and sum to $\dashint_{\theta\in\mathbb S^{d-1}} W^*_N(\theta)d\theta\leq C$. Because the function $h(x)=x\sqrt{\log(x^{-1})}$ is concave for $x\in [0,1]$, by Jensen’s inequality the maximum is achieved when all $\lambda_n$ are equal. This gives an upper bound $O(C\sqrt{d\log N})$ which means a competitive ratio of $O(\sqrt{d\log N})$ as desired.

Non-Euclidean Spaces {#subsec:generalnormedspace}
--------------------

By John’s Theorem, all the preceding results for Euclidean space hold in any normed space up to a distortion factor of at most $\sqrt{d}$. In fact the functional Steiner point can be defined in any normed space. As a result, our $d+1$ upper bound holds in this greater generality. We first give the general definition of the ordinary Steiner point.

[@steinerlipschitz Chapter 6]

Let $X$ be an arbitrary $d$-dimensional normed space, and $K\subseteq X$ a convex body. The Steiner point $s(K)\in X$ is defined in the following two equivalent ways:

1.  For any dual vector $v\in X^*$, let $f_K(v)=\arg\max_{x\in K}(\theta\cdot x) $ be the extremal point in $K$ in direction $\theta$. Then compute the average of this extremal point for a random vector in the dual unit ball: $$s(K)=\dashint_{v\in B^*_1} f_K(v) dv.$$

2.  For any dual unit vector $\theta\in \partial B^*_1$, let $h_K(\theta)=\max_{x\in K}(\theta\cdot x)$ be the support function for $K$ in direction $\theta$, and compute $$s(K)=d\dashint_{\theta\in \partial B^*_1} h_K(\theta)n(\theta) d\mu(\theta).$$

Here the measure in the first integral is volume measure, which up to normalization does not depend on any norm properties of $\mathbb R^d$, only the vector space structure. In the second integral, $n(\theta)\in X$ is the outward unit normal to the unit dual ball $B^*_1$ at $\theta$, defined by $||n(\theta)||_X=1$ and $n(\theta)^T\theta = 1$. The surface measure $\mu(\theta)$ is the *cone measure*, which can be sampled by taking a uniformly random $z\in B^*_1$ and normalizing it to $\frac{z}{||z||}.$ See [@steinerlipschitz] chapter $6$ for a careful derivation of essentially this fact, again via the divergence theorem.

This definition immediately generalizes the upper bound $d$ for nested chasing [@chasingnested2018] in any normed space. As with the Steiner point for Euclidean space, all that is needed about the functions $f_K$ and $h_K$ is the gradient relationship $\nabla h_K=f_K$. As a result, we can again extend the definition of Steiner point to the functional Steiner point of a convex function.

Let $X$ be an arbitrary $d$-dimensional normed space, and $W:X\to\mathbb R^+$ a convex function with $W^*(v)$ finite for all $v$ in the dual unit ball $B^*_1$. The functional Steiner point $s(W)\in X$ is defined in the following two equivalent ways:

1.  $$s(W)=\dashint_{v\in B^*_1} v^* dv.$$

2.  $$s(W)= -d\dashint_{\theta\in \partial B^*_1} W^*(\theta)n(\theta) d\mu(\theta).$$

In any $d$-dimensional normed space, the functional Steiner point achieves competitive ratio $d+1$ for chasing convex functions and competitive ratio $d$ for chasing convex bodies.

Having defined the proper setup, the proof is completely identical to the Euclidean case.

A Unified View on the Functional Steiner Point {#sec:unify}
==============================================

We have given a solution to chasing convex bodies using the functional Steiner point of the work function. Concurrently [@AGGT] gave a different solution by taking the Steiner point of a (convex) level set of the work function.

In this section (which was added after the initial concurrent posting) we unify these two constructions. In particular we show that Steiner point of any level set of $W_t$ is equal to the functional Steiner point after requesting that level set. For a sufficiently large level set, the final request is vacuous and the definitions exactly coincide.

In the context of [@AGGT], this has two consequences. First, their algorithm achieves competitive ratio $O(d)$ in any normed space, even though their proof seems to rely on reflections which are only valid in Euclidean space. Second, it shows that the doubling trick they use is unnecessary since taking an infinitely large level set to begin with exactly recovers the functional Steiner point.

Functional Steiner Point as an Online Selector
----------------------------------------------

We start by giving a direct proof that the functional Steiner point in an online selector, i.e. that $s(W_t)\in K_t$. This can be deduced implicitly from the purely functional proof in the main body together with the reduction from functions to sets, but for this section it is useful to write it out explicitly. We also give an interpretation of the functional Steiner point as a curvature center, which also parallels the ordinary Steiner point.

For a $1$-Lipschitz convex function $W$, the support set $Supp(W)\subseteq \mathbb R_d$ is the set of points having a subgradient with norm strictly less than $1$.

For chasing convex bodies we have $Supp(W_t)\subseteq K_t$. In particular, if $x\notin K_t$ then $\nabla W_t(x)$ is a unit vector pointing from $y\to x$, where $y$ is the last point in $K_t$ for the path $0\to x$ achieving cost $W_t(x)$ and satisfying requests $(K_1,\dots,K_t)$.

For $z$ on the line segment $yx$, it is clear by definition of $y$ that $W_t(x)-W_t(z)=||x-z||$. Since $W$ is $1$-Lipschitz, this implies the result.

We always have $s(W_t)\in K_t$ for chasing convex bodies.

By the primal definition, $s(W_t)$ is a convex combination of points in $Supp(W_t)\subseteq K_t$.

A simple induction shows that $|\nabla W_t(x)|=1$ unless $x\in \partial K_s$ for some $s\leq t$. Therefore $Supp(W_t)$ is a measure zero set and $W_t$ is highly non-smooth when chasing convex bodies. However one loses nothing by smoothing the work function by a small mollifier, so these singularities do not cause any meaningful issues.

We can be more precise about the statement that $s(W)$ is a convex combination of the points in $Supp(W)$. By applying a change of variables and noting that the Jacobian of the gradient is the Hessian, we obtain that the functional Steiner point $s(W)$ equals

$$s(W)=\int_{x\in\mathbb R^d} \det(\nabla^2 W(x)) \cdot x dx.$$

A similar change of variables shows that the Steiner point $s(K)$ is the center of mass of $\partial K$ weighted by the Gaussian curvature, the product of the principal curvatures. This gives an interpretation of the functional Steiner point $s(W)$ as a renormalized Steiner point of $epigraph(W)$, similar to the results in the next subsection.

Steiner Points of Level Sets
----------------------------

We now complete the connection to the solution of [@AGGT].

For a chasing convex bodies/functions problem and $R\geq \min_x W_t(x)$, define the (convex) level set

$$\Omega_{t,R}=\{x:W_t(x)\leq R\}.$$

Also define $W_t^{K}$ to be the work function at time $t+1$ if $K_{t+1}=K$.

\[lem:unify\]

We have $Supp(W_t^{\Omega_{t,R}})\subseteq Supp(W_t)$ for any $R\geq \min_x W_t(x)$.

\[thm:unify\]

For any $R\geq \min_x W_t(x)$ we have $s(\Omega_{t,R})=s(W_t^{\Omega_{t,R}})\in K_t$. If $R$ is large enough that $K_s\subseteq \Omega_{t,R}$ for all $s<t$ then $s(\Omega_{t,R})=s(W_t)$.

Because $\Omega_{t,R}$ is a level set, we see that

$$W_t^{\Omega_{t,R}}(x)=\Bigg\{\begin{array}{lr}
        W_t(x), & \text{for } x\in \Omega_{t,R}\\
        d(x,\Omega_{t,R})+R, & \text{for } x\notin \Omega_{t,R}\\
        \end{array}$$

From this it is easy to see that $Supp(W_t^{\Omega_{t,R}})\subseteq Supp(W_t)$. Indeed, the only possible new support points are on the boundary $\partial\Omega_{t,R}$ of the level set. Fix a boundary point $y\in\partial\Omega_{t,R}$ not already in $Supp(W_t)$. Since $\Omega_{t,R}$ is a level set, we know that $\nabla W_t(y)$ consists only of outward normal vectors to $\Omega_{t,R}$ at $y$ (or, in the normal cone if $y$ is a corner). Since these are subgradients, this means that the derivative of $W_t$ at $y$ in some inward direction $v$ with $-v$ in the normal cone is $-1$. This will remain true in $W_t^{\Omega_{t,R}}$, showing that $y\notin Supp(W_t^{\Omega_{t,R}})$ as claimed.

The lemma combined with the primal definition immediately implies $s(W_t^{\Omega_{t,R}})\in K_t$. Also it is clear that for $R$ large we have $W_t=W_t^{\Omega_{t,R}}$. Therefore the only thing to prove is that $s(W_t^{\Omega_{t,R}})=s(\Omega_{t,R})$. This is the heart of our unification.

The point is that for $|\theta|=1$, we have

$$f_{\Omega_{t,R}}(\theta)\in \arg\max_{x\in \mathbb R^d} (W_t^{\Omega_{t,R}}(x)-x\cdot\theta).$$

Where again $f_K(v)=\arg\max_{x\in K}(v\cdot x).$ Therefore:

$$\begin{aligned}
s(W_t^{\Omega_{t,R}})=&(-d)\cdot \dashint_{|\theta|=1}W_t^*(\theta)\cdot \theta d\theta \\
=&(-d)\cdot \dashint_{|\theta|=1}\left(W_t(f_{\Omega_{t,R}}(\theta))-f_{\Omega_{t,R}}(\theta)\cdot\theta\right)\cdot \theta d\theta \\
=&(-d)\cdot \dashint_{|\theta|=1}\left(R-f_{\Omega_{t,R}}(\theta)\cdot\theta\right)\cdot \theta d\theta \\
=& d\cdot \dashint_{|\theta|=1}\left(f_{\Omega_{t,R}}(\theta)\cdot\theta\right)\cdot \theta d\theta \\
=&d\cdot \dashint_{|\theta|=1}h_{\Omega_{t,R}}(\theta)\cdot \theta d\theta\\
=& s(\Omega_{t,R}).\end{aligned}$$

In words, the above calculation can described as follows: the support function of a set and the Legendre-Fenchel of a function transform only differ by a function value term. Using a level set of the function makes this term constant, hence vanish under spherically symmetric integration, so the definitions coincide in this case.

For a general work function $W_t$, i.e. a $1$-Lipschitz convex function with $W_t(x)-|x|$ positive and bounded, the same proof shows that $\lim_{R\to\infty}s(\Omega_{t,R})=s(W_t)$. Indeed, the above proof relies on the fact that

$$\max_{x\in\mathbb R^d} (W_t^{\Omega_{t,R}}(x)-x\cdot\theta)=\max_{x\in\partial\Omega_{t,R}} (W_t^{\Omega_{t,R}}(x)-x\cdot\theta).$$

But the difference always vanishes in the limit $R\to\infty$, so we obtain the result by the bounded convergence theorem.

Acknowledgement {#acknowledgement .unnumbered}
===============

I thank Sébastien Bubeck, Bo’az Klartag, Yin Tat Lee, and Yuanzhi Li for the introduction to convex body chasing and the Steiner point, and many stimulating discussions. I thank Ethan Jaffe, Felipe Hernandez, and Christian Coester for discussions about properties of the work function. I additionally thank Sébastien for helpful comments on older versions of the paper. The author gratefully acknowledges the support of an NSF graduate fellowship and a Stanford graduate fellowship.

Appendix
========

We prove the result for all $v$ where $v^*_t$ is well-defined, that is, where $\nabla^2 W^*_t(v)$ exists. Almost all $v$ satisfy this by Alexandrov’s theorem, and it means $W_t$ is strictly convex at $v^*_t$.

First we note that

$$\begin{aligned}
W^*_{t+\delta}(v)=& \min_{x_s:[0,t]\to\mathbb R^d} \left(\int_{0}^{t+\delta} (f_s(x_s)+||x'_s||ds -v^Tx_t\right)\\
=& \min_{ x_s:[t,t+\delta]\to \mathbb R^d}\left(W_t(x_t)+\int_{t}^{t+\delta}f_s(x_s)+||x'_s||ds - v^Tx_{t+\delta}\right)\\
:=& \min_{ x_s:[t,t+\delta]\to \mathbb R^d} \Gamma(x_s). \end{aligned}$$

For small $\delta>0$, we show $W^*_{t+\delta}(v)=W^*_t(v)+\delta f_t(v^*_t)+o(\delta)$. For the upper bound, we have

$$\begin{aligned}
W^*_{t+\delta}(v)\leq & W^*_t(v)+\int_t^{t+\delta} f_s(v^*_t)ds\\ = & W^*_t(v)+\delta f_t(v^*_t)+o(\delta)\end{aligned}$$

because we can move optimally to $v^*_t$ and take $x_s$ constant during $s\in [t,t+\delta]$.

For the lower bound the idea is that by strict convexity, for small $\delta$ if $x_t$ is far from $v_t^*$, the minimization problem already has too large a value. We have

$$W_t(w)\geq W_t(v^*_t)+v^T(w-v^*_t)+f(|w-v^*_t|)$$ for some non-negative convex $f$ with $f(x)$ bounded away from $0$ when $|x|$ is bounded away from $0$.

Considering the minimization problem for $W^*_{t+\delta}(v)$, if $x_t=w$ then we have

$$\begin{aligned}
\Gamma(x_s)\geq & W_t(w)+\int_t^{t+\delta} f_s(x_s)+||x'_s||ds-v^Tx_{t+\delta} \\
\geq & W_t(v^*_t)+v^T(w-v^*_t)+f(|w-v^*_t|) + \int_t^{t+\delta} f_s(x_s)+||x'_s||ds-v^Tx_{t+\delta} \end{aligned}$$

Because $\int_t^{t+\delta} ||x'_s||ds \geq |x_{t+\delta}-x_t| \geq v^T(x_{t+\delta}-x_t)$ and $w=x_t$ we have

$$\begin{aligned}
\Gamma(x_s)\geq & W_t(v^*_t)-v^Tv^*_t+f(|w-v^*_t|) + \int_t^{t+\delta} f_s(x_s)ds\\
\geq & W_t(v^*_t)-v^Tv^*_t+f(|w-v^*_t|)\\
\geq & W^*_t(v)+f(|w-v^*_t|)\end{aligned}$$

Because $W_{t+\delta}(v)=W_t(v)+O(\delta)$, we see that for $\delta\to 0$ small we must have $|x_t-v_t^*|\to 0$ for any optimal trajectory $x_s$. Additionally, we have

$$\int_t^{t+\delta} ||x'_s||ds + v^T(x_t-x_{t+\delta}) \geq (1-|v|)\int_t^{t+\delta} ||x'_s||ds \geq (1-|v|)\max_{s\in [t,t+\delta]} |x_t-x_s|.$$

which implies $|x_t-x_s|=o(1)$ for all optimal trajectories since $|v|<1$. From this we see that all optimal trajectories have $\int_t^{t+\delta} f_s(x_s)ds = \delta(f_t(v^*_t) +o(1)).$ Combining gives the desired lower bound.
