Online metric allocation and time-varying regularization

Conference item

We introduce a general online allocation problem that connects several of the most fundamental problems in online optimization. Let 𝑀 be an 𝑛-point metric space. Consider a resource that can be allocated in arbitrary fractions to the points of 𝑀. At each time 𝑡, a convex monotone cost function 𝑐_𝑡 : [0, 1] → ℝ₊ appears at some point 𝑟_𝑡 ∈ 𝑀. In response, an algorithm may change the allocation of the resource, paying movement cost as determined by the metric and service cost 𝑐_𝑡 (𝑥_𝑟𝑡 ), where 𝑥_𝑟𝑡 is the fraction of the resource at 𝑟_𝑡 at the end of time 𝑡. For example, when the cost functions are 𝑐_𝑡(𝑥) = 𝛼𝑥, this is equivalent to randomized MTS, and when the cost functions are 𝑐_𝑡(𝑥) = ∞·𝟙_𝑥<1/𝑘, this is equivalent to fractional 𝑘-server.

Because of an inherent scale-freeness property of the problem, existing techniques for MTS and 𝑘-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 𝑂(log𝑛)-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 Θ(𝑛) on tree metrics, which imply deterministic and randomized competitive ratios of 𝑂(𝑛²) and 𝑂(𝑛 log 𝑛) respectively on arbitrary metrics.

Authors: Bansal, N; Coester, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Host title: Leibniz International Proceedings in Informatics (LIPIcs)
• Volume: 244
• Pages: 13:1–13:13
• Article number: 13
• Place of publication: Dagstuhl, Germany
• Publication date: 2022-09-01
• Acceptance date: 2022-06-20
• Event title: 30th Annual European Symposium on Algorithms (ESA 2022)
• Event location: Berlin/Potsdam, Germany
• Event website: https://algo-conference.org/2022/esa/
• Event start date: 2022-09-05
• Event end date: 2022-09-07
• DOI: 10.4230/LIPIcs.ESA.2022.13
• ISSN: 1868-8969
• ISBN: 9783959772471
• Language: English
• Keywords: competitive analysis; FFR; regularization; mirror descent; metrical task systems; 𝑘-server; online algorithms
• Subjects: Theory of computation – k-server algorithms; Theory of computation – online algorithms