From the 1 of 6 linked papers with an AI index.
6 papers
Thompson Sampling Is 2-Competitive for Mistakes
Mark Sellke, Gregory Valiant
The paper proves that Thompson sampling incurs at most twice the expected number of suboptimal arm selections as any other policy in Bayesian bandit settings, under independent arm…
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…
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…
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…
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…
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…