Evolving Entropic Regularization

May 18, 2022, 2:15 PM - 3:00 PM


Online Event

Sebastien Bubeck, Microsoft Research

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.