Sample Amplification: Increasing Dataset Size even when Learning is Impossible

Given data drawn from an unknown distribution, D, to what extent is it possible to ``amplify'' this dataset and output an even larger set of samples that appear to have been drawn from D? We formalize this question as follows: an (n,m) amplification procedure takes as input n independent draws from an unknown distribution D, and outputs a set of m > n ``samples''. An amplification procedure is valid if no algorithm can distinguish the set of m samples produced by the amplifier from a set of m independent draws from D, with probability greater than 2/3. Perhaps surprisingly, in many settings, a valid amplification procedure exists, even when the size of the input dataset, n, is significantly less than what would be necessary to learn D to non-trivial accuracy. Specifically we consider two fundamental settings: the case where D is an arbitrary discrete distribution supported on ≤ k elements, and the case where D is a d-dimensional Gaussian with unknown mean, and fixed covariance. In the first case, we show that an left(n, n + Theta(fracn√k)right) amplifier exists. In particular, given n=O(√k) samples from D, one can output a set of m=n+1 datapoints, whose total variation distance from the distribution of m i.i.d. draws from D is a small constant, despite the fact that one would need quadratically more data, n=Theta(k), to learn D up to small constant total variation distance. In the Gaussian case, we show that an left(n,n+Theta(fracn√d )right) amplifier exists, even though learning the distribution to small constant total variation distance requires Theta(d) samples. In both the discrete and Gaussian settings, we show that these results are tight, to constant factors. Beyond these results, we formalize a number of curious directions for future research along this vein.