Skip to main content
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 $...
Yury's user avatar
  • 3,909
6 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-\...
Yuval Peres's user avatar
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 ...
Aryeh's user avatar
  • 10.6k
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\...
Clement C.'s user avatar
  • 4,481
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[...
Yuval Filmus's user avatar
  • 14.5k
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 ...
Clement C.'s user avatar
  • 4,481
5 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)...
James Melbourne's user avatar
5 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 $$ (...
Clement C.'s user avatar
  • 4,481
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 ...
Clement C.'s user avatar
  • 4,481
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=\...
Bjørn Kjos-Hanssen's user avatar
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'$. ...
Aryeh's user avatar
  • 10.6k
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 ...
Clement C.'s user avatar
  • 4,481
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. ...
Clement C.'s user avatar
  • 4,481
4 votes

Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?

Yes, (it is believed that) there are sequences that can't be learned by any ML model: cryptographic pseudorandom generators (see also here) are one good candidate. If a sequence fails some Diehard ...
D.W.'s user avatar
  • 12.3k
3 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 ...
Pedro Juan Soto's user avatar
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
Aryeh's user avatar
  • 10.6k
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}...
usul's user avatar
  • 7,615
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: ...
D.W.'s user avatar
  • 12.3k
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....
Aryeh's user avatar
  • 10.6k
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
Shlomo Engelson Argamon's 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
user43170's user avatar
  • 163
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) \...
Lockjaw's 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)>\...
Aryeh's user avatar
  • 10.6k
1 vote
Accepted

Differential privacy definition: subset of range of values vs. equals a value in the range

If you are working with discrete probability distributions, then for any subset $S$ of the range, you have $$ \Pr[\mathcal{M}(x)\in S] = \sum_{s\in S} \Pr[\mathcal{M}(x)=s] \leq \sum_{s\in S} e^\...
Clement C.'s user avatar
  • 4,481
1 vote

Examples of learning via exactly integrable gradient flows

How about the simple squared loss function used in linear regression? That is, let $\ell(w(t), z) = \frac{1}{2n} \sum_{i=1}^n (z_i^\top w(t) - y_i)^2$ for data vectors $z_i \in \mathbb{R}^d$ and $y\in ...
walkerbacker's user avatar
1 vote

Machine Learning: Calibrating SubGroups of Probability Predictions inside a Dataset which should sum to 100%

Let $p_i=\Pr[F_i]$ be the probability that flower $i$ is a daffodil, according to your model (without taking into account the group structure). Now you are given a group of 10 flowers, with ...
D.W.'s user avatar
  • 12.3k
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....
usul's user avatar
  • 7,615
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 ...
Mahdi Cheraghchi's 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 ...
user3389669's user avatar
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 ...
Mahdi Cheraghchi's user avatar

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