On Task Aware Compression: Common Information Dimension and Contextual Bandit Learning

Mr. Osama A. Hanna
The University of California, Los Angeles (UCLA)
Hosted by Department of Information Engineering, CUHK
Friday, 7 July, 2023
Room 804, William M.W. Mong Engineering Building

This talk highlights our recent work on two theoretical directions, namely common information dimension and contextual linear bandits. Both direction can be potentially leveraged for task aware compression.

Common information is a classical problem in information theory with many applications in cryptography, hypothesis testing and multi-modal representation learning. The exact common information between a set of random variables is defined as the minimum entropy of a shared random variable that allows for the exact distributive simulation of the random variables. It has been established that, in certain instances, infinite entropy is required to achieve distributive simulation, suggesting that continuous random variables may be needed in such scenarios. However, to date, there is no established metric to characterize the complexity of such cases. In this talk, we propose the concept of Common Information Dimension (CID), defined as the minimum dimension of a random variable required to distributively simulate a set of random variables. Our main contributions include the computation of the common information dimension for jointly Gaussian random vectors in a closed form.

Moving on to contextual linear bandits, we investigate the ability to compress the context without affecting learning performance. Linear bandit and contextual linear bandit problems have recently attracted extensive attention as they enable to support impactful active learning applications through elegant formulations. In linear bandits, a learner selects an action from a fixed action space at each round and receives a reward determined by the inner product of the action and an unknown parameter vector, plus noise. Contextual linear bandits introduce an additional layer of complexity by allowing the action space to vary at each round, thereby capturing context. The goal is to design an algorithm that learns to play as close as possible to the unknown optimal policy after a number of action plays. The contextual problem is considered more challenging than the linear bandit problem, which can be regarded as a contextual bandit problem with a fixed context. Surprisingly, in this talk, we show that the stochastic contextual problem can be solved as if it is a linear bandit problem. To accomplish this, we present a novel reduction framework that transforms any stochastic contextual linear bandit instance into a linear bandit instance. Our reduction framework opens up a new way to approach stochastic contextual linear bandit problems, and enables significant savings in communication cost in distributed setups. Furthermore, it yields improved regret bounds in a number of instances.


Osama A. Hanna is a Ph.D. candidate in the Electrical and Computer Engineering Department at the University of California, Los Angeles (UCLA). He received his BS and MS degrees in electrical engineering from the Faculty of Engineering Cairo University and Nile University in Egypt in 2014 and 2018 respectively. He received the Award of Excellence from Cairo University in 2014. He received the Masters Fellowship and a graduate Research Assistantship from Nile University for the years 2014-2018, and Marie Sklodowska-Curie Fellowship for the year of 2017. He received the Electrical and Computer Engineering Department Fellowship from UCLA for the year 2018/2019. His research interests are machine learning, information theory and mathematics.