Online Multiserver Convex Chasing and Optimization
This work addresses fundamental online optimization challenges with applications to clustering, but it is incremental in extending known problems to more general settings.
The paper tackles the problem of k-chasing of convex functions, a generalization of the k-server and convex chasing problems, showing that no online algorithm with bounded competitiveness exists for general cases with k>1 and d>1, but competitive algorithms exist for a class of functions including clustering problems with dimension-free ratios. It also explores top-k action regret minimization in online convex optimization, revealing that vanishing regret is possible but with limitations such as no speed-up for strongly convex functions and requiring intractable computations and randomness.
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.