Oct. 22, 2019, 10:15 a.m.

Title: Pure entropic regularization for metrical task systems
Authors: Christian Coester and James R. Lee
Speaker: Christian Coester
Time and place: Tuesday, 22nd of October 2019, 10:15 am, room 310.

Appeared in COLT 2019.


Metrical task systems (MTS) are a general framework for online problems, containing many other online problems (e.g. the k-server problem) as special cases: The possible states of an algorithm for MTS are points in some metric space of cardinality n. At each time step, a cost function is revealed, mapping each point of the metric space to a service cost associated with being in that state. Whenever a cost function is revealed, the algorithm can change its state, paying the service cost of the new state, but also paying a movement cost equal to the distance from the old to the new state. I will present recent joint work with James Lee: For HST metrics, we show an algorithm with 1-competitive service cost and O(log n)-competitive movement cost compared to the optimal total cost. These refined guarantees are optimal, and they imply an algorithm with 1-competitive service cost and O((log n)^2)-competitive movement cost on general metrics. Our algorithm is an instantiation of online mirror descent with a regularizer derived from a multiscale conditional entropy.