12
votes
Accepted
Sampling monotone Boolean functions
In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system ...
- 3,402
8
votes
Accepted
Qubit gates in google supremacy
Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They ...
- 24.9k
4
votes
Accepted
How many samples are needed to reconstruct a path?
Here’s a simple idea: try a certain number $s$ of samples, and for each vertex, record how many times its colour agreed with the provided bit.
For vertices outside the path, they agree with ...
- 18.2k
4
votes
Is uniform convergence faster for low-entropy distributions?
This is very much a partial answer to my question. I'm hoping for a much better bound (or a counterexample). I managed to show a very weak bound. It is not very useful, but it does at least show that ...
- 2,803
4
votes
Is uniform convergence faster for low-entropy distributions?
First, let's use McDiarmid's inequality to conclude that
$$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge
\mathbb{E}|| \bar X - \mu ||_\infty
+
\varepsilon \right] \le e^{-2n\varepsilon^2},$$
so it ...
- 10.6k
3
votes
Accepted
Coreset and VC dimension
The answer of Har-Peled is mainly regarding problems where you wish to cover points by shapes (e.g. balls). A strong relation to eps-nets and hitting sets can be found e.g. in his paper here
For the ...
- 146
2
votes
Is uniform convergence faster for low-entropy distributions?
We have largely resolved the question for product measures. I'm going to change the notation from the OP to be in line with our paper,
https://arxiv.org/abs/2209.04054
I'll be writing $\mu$ rather ...
- 10.6k
2
votes
Accepted
Sample complexity for learning Boltzmann Distribution parameters
Under appropriate smoothness conditions (satisfied by the Boltzmann distribution), the maximum likelihood is asymptotically normal. Meaning: the vector $\sqrt n(\theta-\hat\theta)$ will have ...
- 10.6k
2
votes
Accepted
Lower bound for the OR problem
After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I ...
- 630
1
vote
Accepted
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
From the DKW inequality, it follows one can learn an arbitrary distribution over $\mathbb{R}$ (and in particular over $\{1,2,\dots,n\}$ to Kolmogorov distance* $\varepsilon$ with probability at least $...
- 4,481
1
vote
Sample Complexity for Order Statistics
One way to approach this problem is via the CDF transformation. Consider $Z=F(X)$. We know $Z$ is uniformly distributed in $[0,1]$. Let $Z_{(1)},...,Z_{(m)}$ be the order statistics of these $m$ ...
Only top scored, non community-wiki answers of a minimum length are eligible