10
votes
Accepted
What is the connection between moments of Gaussians and perfect matchings of graphs?
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 $...
- 3,844
9
votes
Accepted
Approximating distributions from samples
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 ...
- 18k
7
votes
Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables
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 ...
- 14.1k
5
votes
Learning a coin's bias (localized)
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 ...
- 4,361
5
votes
Accepted
Learning a coin's bias (localized)
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-\...
- 441
5
votes
Accepted
L1 / Variational Distance between distributions
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\...
- 4,361
5
votes
What is the connection between moments of Gaussians and perfect matchings of graphs?
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[...
- 14.1k
5
votes
Accepted
Tolerance parameter of statistical query model and adaptivity
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 (...
- 881
5
votes
Accepted
Is there an equivalent to VC-dimension for density estimation as opposed to classification?
For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to ...
- 10.1k
4
votes
Accepted
Learning from derivative data
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'$. ...
- 10.1k
4
votes
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
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
$$
(...
- 4,361
4
votes
Accepted
Testing for finite expectation
This seems to be addressed in the following paper by Joseph P. Romano, Section 3 [1] (specifically, Example 1):
Example 1 (Finite versus not finite mean). Let $X$ be $X_1, \dots, X_n$, $n$ i.i.d. ...
- 4,361
4
votes
Accepted
About learning a single Gaussian in total-variation distance
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 ...
- 4,361
4
votes
Accepted
Is the Chi-square divergence a Bregman divergence?
$\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=\...
- 4,400
4
votes
Accepted
Binary search on coin heads probability
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 ...
- 4,361
3
votes
Accepted
Is this a known learning problem?
Well, we wrote a paper on it, so now it's definitely known:
https://arxiv.org/abs/2010.09886
- 10.1k
3
votes
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
@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)...
2
votes
Approximating distributions from samples
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 $\...
- 419
2
votes
Accepted
Learning a discrete distribution in $\ell_r$ norm
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}...
- 7,090
2
votes
Accepted
Design a sampling process to select an element with probability proportional to its appear probability in a simulation
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:
...
- 10.5k
2
votes
Terminology and references for a learning model
The related work I know of is experimental, but a similar setup has been called Learning from Label Proportions: https://link.springer.com/article/10.1007/s13278-017-0478-6
2
votes
About learning a single Gaussian in total-variation distance
In Appendix B of [Ashtiani et al., Neurips 2018]. https://arxiv.org/pdf/1710.05209.pdf
- 163
2
votes
How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?
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....
- 10.1k
2
votes
Accepted
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well
Asymptotic for ...
- 224
2
votes
An (unusual?) risk bound
I believe a common name for what you describe as $\mathcal{N}(\mathcal{F},2n)$ is the "growth function".
For a concept class $\mathcal{F} = \{ h : X \to \{0,1\} \}$ and $S = (x_1,\dots,x_n) \...
- 121
2
votes
Accepted
Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$
Let us suppose that $H$ shatters some $k$ points $(x_i,y_i)$, $i\in[k]$.
That means that for all $b\in\{0,1\}^k$, there is an $f=f_b\in F$ such that $y_if(x_i)\le\gamma$ if $b_i=1$ and
$y_if(x_i)>\...
- 10.1k
1
vote
Accepted
Notation in proof for Asymptotic Equipartition Property
Your understanding is right, you just need to internalize it a bit more. $U^n$ is a random variable with a well-defined distribution. If you just write $U^n$, it has been defined exactly what you mean....
- 7,090
1
vote
Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$
If I understand right what "average volume" means here, I don't think this is correct. For example, let's say you map $n$-bit strings (under uniform distribution) to $n$-bit strings as follows: Given ...
- 4,011
1
vote
Why non-uniform learnability does not imply PAC learnability?
The following answer is based on chapter 6/7 of the book »Understanding Machine Learning: From Theory to Algorithms«, by Shalev-Shwartz and Ben-David (especially Example 7.1).
It states that the ...
- 111
1
vote
Accepted
Notation of sequences in rate distortion theory
In information theory notation, capital letters such as $X$ denote random variables, and lowercase letters such as $x$ mean their possible outcomes (i.e., fixed values). For example you can write the ...
- 4,011
Only top scored, non community-wiki answers of a minimum length are eligible