k-experts - Online Policies and Fundamental Limits
# 114
Abstract
In this talk, we introduce the k-experts problem - a generalization of the classic problem Prediction with Expert Advice. Unlike the traditional setup, where the online learner selects exactly one expert from a pool of N experts at each round, in the k-experts problem, the learner chooses a subset of k experts at each round, where k is a fixed integer between 1 and N. The rewards, which are revealed to the learner at the end of each round, may depend arbitrarily on the set of selected experts. Our goal is to design an online learning policy that incurs minimal regret compared to selecting the best-in-hindsight fixed collection of k experts at every round. In this pursuit, we propose SAGE (Sampled Hedge) - a framework for designing efficient online learning policies by leveraging statistical sampling techniques. We show that SAGE yields an efficient online learning policy with a near-optimal regret bound for a broad class of admissible reward functions. Towards this, we establish a surprising connection between the admissibility of reward functions and the non-emptiness of the core of a related cooperative game. Furthermore, going beyond the static regret metric, we give an information-theoretic characterization of the mistake bounds achievable by online learning policies for stable loss functions. We will conclude this talk by establishing a tight regret lower bound and reporting experimental results with standard datasets. Joint work with Sourav Sahoo (IIT Madras) and Samrat Mukhopadhyay (IIT (ISM) Dhanbad). A preliminary version of the paper appeared in AISTATS 2022.
Abhishek Sinha, TIFR
Abhishek Sinha is currently a faculty member in the School of Technology and Computer Science at the Tata Institute of Fundamental Research, Mumbai, India. Prior to joining TIFR, he had been on the faculty of the Dept. of Electrical Engineering at the Indian Institute of Technology Madras. He received his Ph.D. from the Massachusetts Institute of Technology, where he was affiliated with the Laboratory for Information and Decision Systems. Thereafter, Abhishek worked as a senior engineer at Qualcomm Research, San Diego, in the 5G standardization group. He obtained his M.E. degree in Telecommunication Engg. from the Indian Institute of Science, Bangalore, and B.E. degree in Electronics and Telecommunication Engg. from Jadavpur University, Kolkata, India. He is a recipient of the INSA Medal for Young Scientists (2021), Best Paper Awards in INFOCOM 2018 and MobiHoc 2016, and Jagadis Bose National Science Talent Search (JBNSTS) scholarship, Kolkata, India. His areas of interest include theoretical machine learning, networks, and information theory.