12
BP and most of its variants are proved to converge on graphs without cycles. When you have cycles they show very strange behavior sometimes. For these cases people have tried different approximations schemes, for example Sherali-Adams, Lovasz-Schrijver, and Lasserre Hierarchies.
See [1] for a comprehensive review of these approximations. Also (Wainwright ...
10
As you mention, it is possible to determine the optimal average success probability numerically, which can be done efficiently via semidefinite programming (see e.g. this paper by Eldar, Megretski and Verghese or these lecture notes by John Watrous), but no closed form expression is known.
However, there are several known upper and lower bounds on the ...
9
I think it's a simple application of Hoeffding's inequality. Using your notation, let $Q_i = \frac1m C_i$, i.e. $Q$ is the empirical distribution that approximates $P$. The total variation distance between $P$ and $Q$, i.e. half the $\ell_1$ distance, is
$$
\max_{S \subseteq [n]} \left| \sum_{i \in S}{P_i} - \sum_{i \in S}{Q_i}\right|.
$$
Let $P(S):= \sum_{...
9
This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$ be the covariance of $\gamma_i$ and $\gamma_j$. Consider the complete graph on $\{1, \dots, 2n\}$; assign weight $c_{...
7
See Theorem 23 in Section 9.3 of Ryan O'Donnell's book Analysis of Boolean functions. Even though the theorem there is stated for $\pm 1$ variables, it holds for Gaussians as well (see Chapter 10 of the book for details on that).
For the more general statement, see Exercise 7 in these lecture notes of Terry Tao.
6
I would expect that the empty relation corresponds to the always-zero probability distribution. Disjoint union corresponds to addition of probability distributions. However, standard union would be more complicated. I don't really know if there is some way to encode the standard union for probability distributions. (I have heard people say that ...
6
It appears that $O(1/\epsilon^2)$ samples — as usul showed below — is enough for testing, so that the sample complexity is exactly $\Theta(1/\epsilon^2)$; actually, it turns out this number of samples us even enough for learning $D$ up to an additive $\epsilon$ wrt the $L_2$ norm.
Let $\hat{D}$ be the empirical density function obtained by drawing $m$ i.i.d....
5
Your construction does not work in general for the value of $k$ given.
Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have
$$
Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right),
$$
for $k \ll d$. Of ...
5
Here's a paper where the authors used BP to obtain a fully polynomial-time randomized approximation scheme for the the capacitated minimum-cost network flow problem.
5
The question this response was trying to answer, roughly: "What is a way to reveal information about the outcome of $n$ i.i.d. coin flips that helps you learn the bias of the coin, but wihout revealing too much about the individual bits?"
Since the bits are i.i.d., the numbers $h$ and $t$ (number each of heads and tails) are completely sufficient to ...
5
$F_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful.
Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F_0$ counting turns out to be quite useful.
$F_1$ counting, or ...
5
What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (the best upper bound is $\sqrt{T} N$ samples).
This is true but not an issue for the planted clique paper you mentioned. That paper is concerned with proving a ...
5
Yuval Peres gave the answer in terms of the Kullback-Leibler divergence. Another way is to recall that the sample complexity will be captured by the inverse of the squared Hellinger distance between the two coins.
Now, letting $D_p$ and $D_{p+\varepsilon}$ be the distributions of a Bernoulli random variable with parameter $p$ and $p+\varepsilon$ ...
5
Write $p=p_0=1-q$. We may assume that $\epsilon<\eta \le p\le 1/2$. Then the sample complexity is of order $\log(1/\delta)$ times the reciprocal of the relative entropy $D((p,q)||(p+\epsilon,q-\epsilon))$.
This yields sample complexity $\Theta(p\epsilon^{-2}\log(1/\delta))$.
5
Using the relation between total variation and $L_1$/$\ell_1$ distance of the probability/distribution/mass functions, we have
$$\begin{align}
d_{\rm TV}(D_1, D_2) &= \frac{1}{2}\lVert D_1-D_2\rVert_1
= \frac{1}{2}\lVert \beta D_2 +(1-\beta)D_3 - D_2\rVert_1\\
&= \frac{1-\beta}{2}\lVert D_3 - D_2\rVert_1
= (1-\beta)d_{\rm TV}(D_2, D_3).
\end{align}$$
4
Here is a different proof, adapted from the monograph The semicircle law, free random variables and entropy. Let $X_i$ be an infinite sequence of i.i.d. variables with distribution $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$, so that $ Y_n :=\frac{X_1+\cdots+X_n}{\sqrt{n}} $ converges in distribution to a standard Gaussian. We will show how to compute the limit of $...
4
If your function is $f:\mathbb{R}\to\mathbb{R}$, you can "learn" $f'$ as a standard regression problem (linear, polynomial, etc.) and then recover $f$ up to an additive constant by integrating $f'$. Obviously, you will only able to recover $f$ up to an additive constant from the derivative.
Update: As for error estimates, here's a simple one. Suppose you've ...
4
Essentially, this follows from three facts:
learning a Gaussian in total variation distance $\delta$ is equivalent to learning its two parameters, $\mu,\Sigma$, to (respectively) $\ell_2$ and relative Frobenius norms $O(\delta)$. (Since then the "empirical Gaussian" with the mean and covariance you estimated will be $\delta$-close to the true Gaussian).
...
4
$\chi^2$-divergence is not a Bregman divergence.
I'll show it for sample size $n=1$. We would have
$$
(x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$
If $y=0$ and $x>0$ this says
$$x=f(x)-f(0)-xf'(0),$$
$$1=\frac{f(x)-f(0)}x-f'(0).$$
Taking $x\to 0^+$ this gives the contradiction $1=0$.
4
This is addressed in the following paper of Karp and Kleinberg:
Karp, Richard M.; Kleinberg, Robert. Noisy binary search and its applications. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 881--890, ACM, New York, 2007.
You can find a copy on Kleinberg's website.
3
I will attempt to atone for my previous error by showing something opposite -- that $\tilde{\Theta}\left(\frac{1}{\epsilon^2}\right)$ samples are sufficient (the lower bound of $1/\epsilon^2$ is almost tight)! See what you think....
The key intuition starts from two observations. First, in order for distributions to have an $L_2$ distance of $\epsilon$, ...
2
You need McDiarmid's inequality, or in particular the Hoeffding inequality, which is a simplification:
Given $n$ independent $X_i$ with the property that $X_i \in [a_i, b_i]$, and $X = (1/n)\sum X_i$, then
$$ \text{Pr}(|X - EX| \ge t) \le 2 \exp(\frac{2t^2n^2}{\sum (b_i - a_i)^2}) $$
2
I seem to have resolved this question. The claim (on page 5 of this http://www.eccc.hpi-web.de/report/2015/063/ survey by Cannone) should have been that one can approximate a distribution to within $\ell_2$ distance $\epsilon$ in $O(\frac{n}{\epsilon^2})$ samples (He does not mention approximate in what sense).
This seems to follow directly from an ...
2
@odea, one can see that $\chi^2(P||Q) \leq c D(P||Q)$ cannot hold in general by taking a two point space with $P = \{ 1 , 0\}$ and $Q = \{ q, 1-q \}$. Then $\chi^2(P ; Q) = \frac 1 q -1$ while $D(P||Q) = \log \frac 1 q$. Such a $c$ would need to satisfy $c \geq \frac{x-1}{\log x}$ for $x \to \infty$.
However, if one assumes that $c=\| \frac{dP}{dQ} \|_\...
2
Your definition of $\chi^2$ divergence is missing a term; namely,
$$
\chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2
= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1
$$
(see e.g. this Wikipedia article on $f$-divergences).
With this in hand, recall that by concavity of the logarithm, we have
$$
\log x \leq x-1, \qquad \forall x &...
2
I agree with D.W. that this should just be a dynamic programming question.
Assume that $P_B$ is known and that we have a prior on $P_A$ and that $N$ is known. (Without a prior on $P_A$ or a known $N$, I do not see how your objective or "optimal" are well-defined.)
Let optimal mean "maximizes expected number of heads" with the expectation over both the coin ...
2
Clément Canonne and I worked this out at some point.
Let $X_j$ be the number of realizations of $j \in [d]$. So $\mathbb{E} X_j = np_j$.
\begin{align*}
\mathbb{E} J_n^r &= \mathbb{E} \|\hat{P}_n - P \|_r^r \\
&= \frac{1}{n^r} \sum_{j=1}^d \mathbb{E} |X_j - \mathbb{E}X_j|^r \\
&\leq \frac{1}{n^r} \sum_{j=1}^d 3\mathbb{E} X_j & (*) ...
2
This can be done efficiently if the size of the samples $S$ is not too large. Let $m$ denote the maximum possible size of $S$. Then the following procedure outputs exactly the correct distribution:
Draw a sample $S$ (using the black box $A$). With probability $|S|/m$, keep $S$ and go to step 2. Otherwise, go back to step 1 and draw a new sample.
Choose ...
2
I tried to find a simple and accessible analysis of AIC. A definitive work seems to be Barron, Birgé, Massart, "Risk bounds for model selection via penalization"
https://link.springer.com/article/10.1007/s004400050210
though I can't vouch for accessibility.
Instead, let's analyze your sinusoids example. Suppose I have a parametric class of densities over $[...
2
In Appendix B of [Ashtiani et al., Neurips 2018]. https://arxiv.org/pdf/1710.05209.pdf
Only top voted, non community-wiki answers of a minimum length are eligible
