Seminars
View all Seminars | Download ICal for this eventOnline and Bandit Algorithms Beyond â„“_p Norms
Series: Bangalore Theory Seminars
Speaker: Thomas Kesselheim, University of Bonn
Date/Time: Apr 28 16:00:00
Location: Microsoft Teams - ON-LINE Talk (See Teams link below)
Abstract:
Vector norms play a fundamental role in computer science and optimization, so there is an ongoing effort to generalize existing algorithms to settings beyond ??_?? and ??_p norms. We show that many online and bandit applications for general norms admit good algorithms as long as the norm can be approximated by a function that is ??gradient-stable?, a notion that we introduce. Roughly it says that the gradient of the function should not drastically decrease (multiplicatively) in any component as we increase the input vector. We prove that several families of norms, including all monotone symmetric norms, admit a gradient-stable approximation, giving us the first online and bandit algorithms for these norm families.
In particular, our notion of gradient-stability gives O(log^2(dimension))-competitive algorithms for the symmetric norm generalizations of Online Generalized Load Balancing and Bandits with Knapsacks. Our techniques extend to applications beyond symmetric norms as well, e.g., to Online Vector Scheduling and to Online Generalized Assignment with Convex Costs. Some key properties underlying our applications that are implied by gradient-stable approximations are a ??smooth game inequality? and an approximate converse to Jensens inequality.
Joint work with Marco Molinaro and Sahil Singla
Microsoft teams link:
Link
We are grateful to the Kirani family for generously supporting the theory seminar series
Hosts: Rameesh Paul, Rahul Madhavan, Aditya Subramanian and Aditya Abhay Lonkar