From the 1 of 22 linked papers with an AI index.
22 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…
A Counterexample to the Gaussian Completely Monotone Conjecture
Yuzhou Gu, Mark Sellke
We provide an explicit probability measure on for which the fifth time derivative of the entropy along the heat flow is positive at some time. This disproves the Gauss…
Short proofs in combinatorics, probability and number theory II
Boris Alexeev, Moe Putterman, Mehtaab Sawhney +2
We give a quintet of proofs resulting from questions posed by ErdÅs. These questions concern ordinary lines in planar point sets, sequences with uniformly small exponential sums,…
Short proofs in combinatorics and number theory
Boris Alexeev, Moe Putterman, Mehtaab Sawhney +2
We give a triplet of short proofs, each of which answers a question raised by ErdÅs. The first concerns the small prime factors of , the second concerns whether an a…
Stable algorithms cannot reliably find isolated perceptron solutions
Shuyang Gong, Brice Huang, Shuangping Li +1
We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A strikin…
Strong Low Degree Hardness for Stable Local Optima in Spin Glasses
Brice Huang, Mark Sellke
It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima exhibiting e.g. local strict convexit…