8 papers
Thompson Sampling Is 2-Competitive for Mistakes
Mark Sellke, Gregory Valiant
We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our an…
A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
Chirag Pabbaraju, Gregory Valiant, Rishi Verma
This paper revisits the classical problem of determining the bias of a weighted coin, where the bias is known to be either or , while…
Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
Spencer Compton, Gregory Valiant
Le Cam's two-point testing method yields perhaps the simplest lower bound for estimating the mean of a distribution: roughly, if it is impossible to well-distinguish a distribution…
Discovering Data Structures: Nearest Neighbor Search and Beyond
Omar Salemohamed, Laurent Charlin, Shivam Garg +2
We propose a general framework for end-to-end learning of data structures. Our framework adapts to the underlying data distribution and provides fine-grained control over query and…
Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc, Gregory Valiant
We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the ty…
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis
Gregory Valiant
We describe two algorithms for multiplying n x n matrices using time and energy n^2 polylog(n) under basic models of classical physics. The first algorithm is for multiplying integ…
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton, Gregory Valiant
Given data drawn from a collection of Gaussian variables with a common mean but different and unknown variances, what is the best algorithm for estimating their common mean? We pre…
Testing with Non-identically Distributed Samples
Shivam Garg, Chirag Pabbaraju, Kirankumar Shiragur +1
We examine the extent to which sublinear-sample property testing and estimation apply to settings where samples are independently but not identically distributed. Specifically, we…