# About lower bounding the sample complexity of a distribution

• Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" as in the minimum number of samples required of the observables for the full joint distribution to be recoverable with some given accuracy? (when possible)

More precisely think of being given a distribution $D$ and constants $\epsilon, \delta >0$ and let there be some parameter say $p(D)$ that one is trying to learn. Now lets say that by taking $N$ samples (denoted as $\{N\}$) from $D$ by using some algorithm $A$, one is able to estimate $p(D)$ as $p'(D,N,A)$. Now I would think that a natural notion of "sample complexity" would be to look for this number,

$$min_{N} [ \{ N \vert Pr_{\{N\}} [ \vert p(D) - p'(D,N,A) \vert \leq \epsilon ] ] \geq 1- \delta \} ]$$

Has such a thing been defined or computed or studied? (...maybe one would very optimistically also want to put in a $min_A$" over the whole expression if in any restricted scenario that too is possible to account for and hence making the quantity truly intrinsic to $D$!..)

(..I can imagine such a question coming up with say "topic modelling" where one can sample only the "word" random variables (the "views") and under certain conditions one can recover the joint distribution of the topics and the views..)

• I would be equally happy to know if there above kind of notion of "sample complexity" has been studied in situations when either all the random variables are observable or when few or all of the random variables have a continuum range.

• Can someone kindly link me to some pedagogic reference about how one proves lower bounds on such a notion of sample complexity of learning a joint distribution?

The closest thing I have found in this regard are things like Theorem 1 (page 12) , Theorem 2 and Theorem 3 (page 14) in this paper, http://newport.eecs.uci.edu/anandkumar/pubs/AltTensorDecomp_Part2LVMs.pdf But then I am not understanding as to why these would be called "sample complexity" because these theorems don't seem to tell me any lower bounds on the number of samples needed to learn the tensors they are looking at. What one can do at best is to take the RHS of the equations proved in these three theorems and ask for that to be upper-bounded by some error tolerance and hence invert that to get a lower-bound on the number of samples needed.

But this is a-priori not the same thing as finding out the minimal number of samples needed to get that accuracy. Am I missing something?

• Your first question seems obviously impossible. If the joint distribution is on $(X,Y)$, and we observe only $X$, it seems obviously impossible to recover the joint distribution, no matter how many observations of $X$ we make. What makes you think your notion of sample complexity is even meaningful? – D.W. Mar 28 '16 at 3:51
• I didn't say that its always possible! With certain other conditions it can be. Like say the "linear independence of views" condition allows for topic models to be recoverable. – Anirbit Mar 28 '16 at 4:07