8 papers · 1 filter
Computational Explorations of Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm…
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…
Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set
Davin Choo, Chandler Squires, Arnab Bhattacharyya +1
Accurate estimates of causal effects play a key role in decision-making across applications such as healthcare, economics, and operations. In the absence of randomized experiments,…
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…
Learnability of Parameter-Bounded Bayes Nets
Arnab Bhattacharyya, Davin Choo, Sutanu Gayen +1
Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal p…
Online bipartite matching with imperfect advice
Davin Choo, Themis Gouleakis, Chun Kai Ling +1
We study the problem of online unweighted bipartite matching with offline vertices and online vertices where one wishes to be competitive against the optimal offline algori…
Outlier Robust Multivariate Polynomial Regression
Vipul Arora, Arnab Bhattacharyya, Mathews Boban +2
We study the problem of robust multivariate polynomial regression: let be an unknown -variate polynomial of degree at most in each variabl…
Optimal estimation of Gaussian (poly)trees
Yuhao Wang, Ming Gao, Wai Ming Tai +2
We develop optimal algorithms for learning undirected Gaussian trees and directed Gaussian polytrees from data. We consider both problems of distribution learning (i.e. in KL dista…