Sebastien Bubeck, Microsoft Research

Abstract

I will recall the entropic regularization approach to metrical task systems/k-server. I will then show how to use an *evolving* entropy functional to regularize when the underlying metric space is revealed bit by bit. The punchline is the resolution of layered graph traversal introduced by Papadimitriou and Yannakakis in 1989.

[Video]