{'fraction_non_alphanumeric': 0.023980815347721823, 'fraction_numerical': 0.00047961630695443646, 'mean_word_length': 4.778393351800554, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Agnostic Distribution Learning via Compression

We study sample-efficient distribution learning, where a learner is given an i.i.d. sample from an unknown target distribution, and aims to approximate that distribution. Assuming the target distribution can be approximated by a member of some predetermined class of distributions, we analyze how large should a sample be, and how should the learner use the sample, in order to be able to find a distribution that is close to the target in total variation distance. Determining the sample complexity of such learning with respect to an arbitrary class of distributions is a fundamental open problem. In this work, we introduce a novel method for distribution learning via a form of compression. Having a large-enough sample from a target distribution, can one compress that sample set – by picking only a few instances from it – in a way that allows recovery of (an approximation to) the target distribution from the compressed set? We prove that if this is the case for all members of a class of distributions, then there is a sample-efficient way of distribution learning for this class. As an application of our approach, we provide a sample-efficient method for agnostic distribution learning with respect to the class of mixtures of k axis-aligned Gaussian distributions over Rn. This method uses only Õ(kn/ǫ2) samples (to guarantee with high probability an error of at most ǫ). This is the first sample complexity upper bound that is tight in k, n, and ǫ up to logarithmic factors. Along the way, we prove several properties of compression schemes. Namely, we prove that if there is a compression scheme for a base class of distributions, then there is a compression scheme for the class of mixtures as well as the products of that base class. These closure properties make compression schemes a powerful tool. For example, the problem of learning mixtures of axis-aligned Gaussians reduces to that of “robustly” compressing one-dimensional Gaussian distributions, which we show is possible using a compressed set of constant size.