22 października 2019 10:15
[Seminarium ZOK] Christian Coester on "Pure entropic regularization for metrical task systems" (COLT 2019, wspólnie z James R. Lee)
Tytuł: Pure entropic regularization for metrical task systems
Autorzy: Christian Coester and James R. Lee
Prelegent: Christian Coester
Czas i miejsce: wtorek, 22-go października 2019, 10:15, sala 310.
Praca z COLT 2019.
Streszczenie:
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.