6 papers
Testing Sparse Functions over the Reals
Vipul Arora, Arnab Bhattacharyya, Philips George John +1
Over the last three decades, function testing has been extensively studied over Boolean, finite fields, and discrete settings. However, to encode the real-world applications more s…
Product distribution learning with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John +1
Given i.i.d.~samples from an unknown distribution , the goal of distribution learning is to recover the parameters of a distribution that is close to . When belongs to th…
Distribution Learning Meets Graph Structure Sampling
Arnab Bhattacharyya, Sutanu Gayen, Philips George John +2
This work establishes a novel link between the problem of PAC-learning high-dimensional graphical models and the task of (efficient) counting and sampling of graph structures, usin…
Learning multivariate Gaussians with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John +1
We revisit the problem of distribution learning within the framework of learning-augmented algorithms. In this setting, we explore the scenario where a probability distribution is…
p-Mean Regret for Stochastic Bandits
Anand Krishna, Philips George John, Adarsh Barik +1
In this work, we extend the concept of the -mean welfare objective from social choice theory (Moulin 2004) to study -mean regret in stochastic multi-armed bandit problems. Th…
Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
Philips George John, Arnab Bhattacharyya, Silviu Maniu +2
Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomi…