Online Metric Allocation and Time-Varying Regularization

Abstract

We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let M be an n-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of M. At each time t, a convex monotone cost function c_t: [0,1] → ℝ_+ appears at some point r_t ∈ M. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost c_t(x_{r_t}), where x_{r_t} is the fraction of the resource at r_t at the end of time t. For example, when the cost functions are c_t(x) = α x, this is equivalent to randomized MTS, and when the cost functions are c_t(x) = ∞⋅1_{x < 1/k}, this is equivalent to fractional k-server.
Because of an inherent scale-freeness property of the problem, existing techniques for MTS and k-server fail to achieve similar guarantees for metric allocation. To handle this, we consider a generalization of the online multiplicative update method where we decouple the rate at which a variable is updated from its value, resulting in interesting new dynamics. We use this to give an O(log n)-competitive algorithm for weighted star metrics. We then show how this corresponds to an extension of the online mirror descent framework to a setting where the regularizer is time-varying. Using this perspective, we further refine the guarantees of our algorithm.
We also consider the case of non-convex cost functions. Using a simple 𝓁₂²-regularizer, we give tight bounds of Θ(n) on tree metrics, which imply deterministic and randomized competitive ratios of O(n²) and O(nlog n) respectively on arbitrary metrics.