Seminars

View all Seminars  |  Download ICal for this event

Competitive Analysis via Mirror Descent (Part 1)

Series: Bangalore Theory Seminars

Speaker: Christian Coester, University of Oxford

Date/Time: Mar 20 17:00:00

Location: Online Talk-teams link follows

Abstract:
Mirror descent is a generalization of gradient descent and is a fairly general technique in algorithm design, originating from convex optimization and used extensively in online learning. In recent years, it has led to the successful discovery of optimal competitive ratios for various fundamental problems in online algorithms. In this two-part lecture, we survey how the technique can be used to obtain competitive online algorithms. Part 1 covers foundations and initial applications to metrical task systems. Part II covers additional applications including k-server, layered graph traversal and metric allocation.


Microsoft Teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan