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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
  • 881
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 ...
user avatar
  • 4,331
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-\...
user avatar
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\...
user avatar
  • 4,331
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[...
user avatar
  • 14.1k
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 ...
user avatar
  • 10k
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'$. ...
user avatar
  • 10k
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 ...
user avatar
  • 4,331
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=\...
user avatar
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 ...
user avatar
  • 4,331
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. ...
user avatar
  • 4,331
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
user avatar
  • 10k
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)...
user avatar
3 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 $$ (...
user avatar
  • 4,331
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 $\...
user avatar
  • 419
2 votes

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

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$, ...
user avatar
  • 7,022
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: ...
user avatar
  • 10.3k
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
user avatar
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
user avatar
  • 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....
user avatar
  • 10k
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}...
user avatar
  • 7,022
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 ...
user avatar
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) \...
user avatar
  • 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)>\...
user avatar
  • 10k
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....
user avatar
  • 7,022
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 ...
user avatar
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible