Online Multiserver Convex Chasing and Optimization
  We introduce the problem of $k$-chasing of convex functions, a simultaneous
generalization of both the famous k-server problem in $R^d$, and of the problem
of chasing convex bodies and functions. Aside from fundamental interest in this
general form, it has natural applications to online $k$-clustering problems
with objectives such as $k$-median or $k$-means. We show that this problem
exhibits a rich landscape of behavior. In general, if both $k > 1$ and $d > 1$
there does not exist any online algorithm with bounded competitiveness. By
contrast, we exhibit a class of nicely behaved functions (which include in
particular the above-mentioned clustering problems), for which we show that
competitive online algorithms exist, and moreover with dimension-free
competitive ratio. We also introduce a parallel question of top-$k$ action
regret minimization in the realm of online convex optimization. There, too, a
much rougher landscape emerges for $k > 1$. While it is possible to achieve
vanishing regret, unlike the top-one action case the rate of vanishing does not
speed up for strongly convex functions. Moreover, vanishing regret necessitates
both intractable computations and randomness. Finally we leave open whether
almost dimension-free regret is achievable for $k > 1$ and general convex
losses. As evidence that it might be possible, we prove dimension-free regret
for linear losses via an information-theoretic argument.
