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

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.