Abstract
The primal-dual schema has been a powerful tool in online optimization and competitive analysis. In a joint project with Bubeck, Cohen, Y. T. Lee, and Madry, we recast some of those methods in the language of entropic regularization and mirror descent. This perspective led to advances in competitive analysis, notably for the infamous k-server problem. While driven by a compelling underlying philosophy, some aspects of the resulting algorithms and analysis are still ad-hoc. I will present joint work with Christian Coester on the first "canonical" instantiation of this method. This is an O(log n)-competitive algorithm for the Metrical Task Systems problem on any HST (hierarchically separated tree), where the underlying algorithm is simply mirror descent on the probability simplex. The algorithm has an appealing local interpretation, where agents sitting at nodes of the HST independently and concurrently modify the marginal probabilities according to a simple update rule. Moreover, it achieves optimal bicriteria "refined" guarantees (in the language of Bansal, Buchbindrer, and Naor).