# Tag Info

Accepted

• 451
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.6k
Accepted

• 4,485
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.6k
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,481
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,481

### 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 ...
• 12.3k
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 ...
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.6k
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,615
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: ...
• 12.3k

### 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.6k

### 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

### 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

• 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^\...
• 4,481
1 vote

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 ... • 136 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 ... • 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.... • 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 ... • 4,031 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,031

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