On the Statistical Complexity of Sample Amplification

Consider the following problem of manufacturing more data: an amplifier is given $n$ samples drawn i.i.d. from an unknown distribution $P$, and the goal is to generate a larger set of $n+m$ samples which are indistinguishable from $n+m$ i.i.d. samples from $P$. How large can $m$ be as a function of $n$ and the distribution class in question? Are there sound and systematic ways to generate a larger set of samples? Is this task strictly easier than the learning task, in the sense that the number of samples required for generating $n+1$ samples is smaller than that required for learning $P$?

In our preliminary work [AGSV20], we formalized this problem as the sample amplification problem, considering total variation (TV) as the measure for indistinguishability.

An equivalent formulation to view Definition 1.1 is as a game between two parties: an amplifier and a verifier. The amplifier gets $n$ samples drawn i.i.d. from the unknown distribution $P$ in the class $\mathcal{P}$, and her goal is to generate a larger dataset of $n+m$ samples which must be accepted with good probability by any verifier that also accepts a real dataset of $n+m$ i.i.d. samples from $P$ with good probability. Here, the verifier is computationally unbounded and knows the distribution $P$, but does not observe the amplifier’s original set of $n$ samples.

Along with being a natural statistical task, the sample amplification framework is also relevant from a practical standpoint. Currently, there is an enormous trend in the machine learning community to train models on datasets that have been enlarged in various ways. There are relatively transparent and classical approaches to achieve this, such as leveraging known invariances such as rotation or translation invariance to augment the dataset by including transformed versions of each original datapoint [SSP⁺03, KSH12, CZM⁺19, SK19, CZSL20]. More recently, deep generative models have been used to both directly enlarge training data and construct larger datasets consisting of samples with properties that are rare in naturally occurring datasets [ASE17, CMST17, FADK⁺18, MMKSM18, YSH18, SYPS19, CPS⁺19, YWB19, HRA⁺19, CMV⁺21, LSM⁺22, CQZ⁺22, LSW⁺23, BKK⁺22]. More opaque approaches such as MixUp [ZCDLP18] and related techniques [TUH18, YHO⁺19, VLB⁺19, HMC⁺20] which add a significant fraction of new datapoints that are explicitly not supported in the true data distribution are also very popular since they seem to improve the performance of the trained models. Given this current zoo of widely implemented approaches to enlarging datasets, there is a clear motivation for bringing a more principled statistical understanding to such approaches. One natural starting point is the statistical setting we consider that asks the extent to which datasets can be enlarged in a perfect sense—where it is not possible to distinguish the enlarged dataset from a set of i.i.d. draws. Moreover, this work lays a foundation for the ambitious broader goal of understanding how various amplification techniques interact with downstream learning algorithms and statistical estimators, and developing amplification techniques that are optimal for certain classes of such algorithms and estimators.

In [AGSV20], a subset of the authors introduced the sample amplification problem, and studied two classes of distributions: the Gaussian location model and discrete distribution model. For these examples, they characterized the statistical complexity of sample amplification and showed that it is strictly smaller than that of learning. In this paper, we work towards a general understanding of the statistical complexity of the sample amplification problem, and its relationship with learning. The main contributions of this paper are as follows:

1. 1.

   Amplification via sufficiency. Our first contribution is a simple yet powerful procedure for sample amplification, i.e. apply the sample amplification map only to sufficient statistics. Specifically, the learner computes a sufficient statistic $T_{n}$ from $X^{n}$, maps $T_{n}$ properly to some $T_{n+m}$, and generates new samples $\widehat{X}^{n+m}$ from some conditional distribution conditioned on $T_{n+m}$. Surprisingly, this simple idea leads to a much cleaner procedure than [AGSV20] under Gaussian location models which is also exactly optimal (cf. Theorem 6.2). The range of applicability also extends to general exponential families, with rate-optimal sample amplification performances. Specifically, for general $d$-dimensional exponential families with a mild moment condition, the sufficiency-based procedure achieves an $(n,n+O(n\varepsilon/\sqrt{d}),\varepsilon)$ sample amplification for large enough $n$, which by our matching lower bounds in Section 6 is asymptotically minimax rate-optimal.

2. 2.

   Amplification via learning. Our second contribution is another general sample amplification procedure that does not require the existence of a sufficient statistic, and also sheds light on the relationship between learning and sample amplification. This procedure essentially draws new samples from a rate-optimal estimate of the true distribution, and outputs a random permutation of the old and new samples. The procedure achieves an $(n,n+O(\varepsilon\sqrt{n/r_{\chi^{2}}(\mathcal{P},n)}),\varepsilon)$ sample amplification, where $r_{\chi^{2}}(\mathcal{P},n)$ denotes the minimax risk for learning $P\in\mathcal{P}$ under the expected $\chi^{2}$ divergence given $n$ samples. This shows that learning $P$ to $\chi^{2}$ divergence $O(n/\varepsilon^{2})$ is sufficient for non-trivial sample amplification.

   In addition, we show that for the special case of product distributions, it is important that the permutation step be applied coordinatewise to achieve the optimal sample amplification. Specifically, if $\mathcal{P}=\prod_{j=1}^{d}\mathcal{P}_{j}$, this procedure achieves a better sample amplification

   $\displaystyle\left(n,n+O\left(\varepsilon\sqrt{\frac{n}{\sum_{j=1}^{d}r_{\chi^{2}}(\mathcal{P}_{j},n)}}\right),\varepsilon\right).$

   We have summarized several examples in Table 1 where the sufficiency and/or learning based sample amplification procedures are optimal. Note that there is no golden rule for choosing one idea over the other, and there exists an example where the above two ideas must be combined.

3. 3.

   Minimax lower bounds. Complementing our sample amplification procedures, we provide a general recipe for proving lower bounds for sample amplification. This recipe is intrinsically different from the standard techniques of proving lower bounds for hypothesis testing, for the sample amplification problem differs significantly from an estimation problem. In particular, specializing our recipe to product models shows that, for essentially all $d$-dimensional product models, an $(n,n+Cn\varepsilon/\sqrt{d},\varepsilon)$ sample amplification is impossible for some absolute constant $C<\infty$ independent of the product model.

   For non-product models, the above powerful result does not directly apply, but proper applications of the general recipe could still lead to tight lower bounds for sample amplification. Specifically, we obtain matching lower bounds for all examples listed in Table 1, including the non-product examples.

We now provide several numerical simulations to suggest the potential utility of sample amplification. Recall that a practical motivation of sample amplification is to produce an enlarged dataset that can be fed into a distribution-agnostic algorithm in downstream applications. Here, we consider the following basic experiments in that vein:

• •

  Fourth moment estimation for one-dimensional Gaussian: here we observe $X_{1},\cdots,X_{n}\sim{\mathcal{N}}(\mu,1)$ with $n=100$ and $\mu=1$, and we consider three estimators. The empirical estimator operates in a distribution-agnostic fashion and is simply the empirical fourth moment $n^{-1}\sum_{i=1}^{n}X_{i}^{4}$. The plug-in estimator uses the knowledge of Gaussianity: it first estimates $\widehat{\mu}=\bar{X}$ and then uses $\mathbb{E}_{X\sim{\mathcal{N}}(\widehat{\mu},1)}[X^{4}]=\widehat{\mu}^{4}+6\widehat{\mu}^{2}+3$. The amplified estimator first amplifies the sample $X^{n}$ into $Y^{n+m}$ via sufficiency (cf. Example 4.1), and then uses the empirical estimator $(n+m)^{-1}\sum_{j=1}^{n+m}Y_{j}^{4}$ based on the enlarged sample $Y^{n+m}$. The plots of the mean absolute errors (MAEs) are displayed in Figure 1(a). We observe that although the empirical estimator based on the original sample $X^{n}$ has a large MAE, its performance is improved based on the amplified sample $Y^{n+m}$.

• •

  Squared $L_{2}$ norm estimation for high-dimensional Gaussian: here we observe $X_{1},\cdots,X_{n}\sim{\mathcal{N}}(\mu,I_{d})$ with $n=50,d=100$ and $\mu={\bf 1}/\sqrt{d}$, and we again consider three estimators for $\mathbb{E}[\|X\|_{2}^{2}]$. As before, the empirical estimator is simply $n^{-1}\sum_{i=1}^{n}\|X_{i}\|_{2}^{2}$, and the plug-in estimator uses the knowledge $\mathbb{E}_{X\sim{\mathcal{N}}(\widehat{\mu},I_{d})}[\|X\|_{2}^{2}]=\|\widehat{\mu}\|_{2}^{2}+d$ and estimates $\widehat{\mu}=\bar{X}$. As for the amplified estimator, it first amplifies the sample $X^{n}$ into $Y^{n+m}$ via sufficiency (cf. Example 4.1), and then uses the empirical estimator based on $Y^{n+m}$. The plots of the mean absolute errors are displayed in Figure 1(b). Here the empirical estimator outperforms the plug-in estimator due to a smaller bias, while the sample amplification further reduces the MAE as long as the size of amplification $m$ is not too large. This could be explained by the bias-variance tradeoff, where the amplified estimator interpolates between the empirical estimator (with no bias) and the plug-in estimator (with the smallest asymptotic variance).

• •

  Binary classification: here we observe two clusters of covariates $X_{1},\cdots,X_{n/2}\sim{\mathcal{N}}(e_{1},I_{d})$ (with label $1$) and $X_{n/2+1},\cdots,X_{n}\sim{\mathcal{N}}(-e_{1},I_{d})$ (with label $-1$), with $n=50,d=10$ and $e_{1}$ being the first basis vector. The target is to train a classifier with a high classification accuracy on the test data with the same distribution. The standard classifier is via logistic regression, which does not use the knowledge of Gaussianity. To apply sample amplification, we first amplify the sample in each class via either sufficiency (cf. Example 4.1) or learning (cf. Example A.8), and then run logistic regression on the amplified datasets. Figure 1(c) displays the classification errors of all three approaches, and shows that both amplification procedures help reduce the classification error even for small values of $m$.

The above experiments demonstrate the potential for sample amplification to leverage knowledge of the data distribution to produce a larger dataset that is then fed into downstream distribution-agnostic algorithms. Some experiments (e.g. Figure 1(b)) also suggest a limit beyond which the amplification procedure alters the data distribution too much. We believe that rigorously examining amplification through the lens of the performance of downstream estimators and algorithms, including those illustrated in our numerical simulations, would be a fruitful direction for future work.

As discussed above, it is commonplace in machine learning to increase the size of datasets using various heuristics, often resulting in large gains in downstream learning performance. However, a clear statistical understanding of when this is possible and what techniques are useful for this is missing. A natural starting point to get a better understanding is the formulation we consider that asks the extent to which datasets can be amplified in a perfect sense—where any verifier who knows the true distribution is not able to distinguish the amplified dataset from a set of i.i.d. draws.

A limitation of the sample amplification formulation described above is that the additive amplification factor $m$ is rather small (e.g., $O(n\varepsilon/\sqrt{d})$ for $d$-dimensional exponential families). Moreover, we show matching lower bounds demonstrating that this factor cannot be improved even when $n$ is large enough to learn the distribution to non-trivial accuracy. However, it might be possible to achieve larger amplification factors with restricted verifiers, for instance, the class of verifiers corresponding to learning algorithms used for downstream tasks (see [AGSV20] for other possible classes of verifiers). Investigating the sample amplification problem with such restricted verifiers may be a practically fruitful future direction.

Despite this limitation, the sample amplification formulation does yield high-level insights that can inform the way datasets are amplified in practice. For instance, from the results in this paper, we know that sample amplification is possible for a broad class of distributions even when learning is not possible. Moreover, both our sufficiency or learning based approaches modify the original data points in general, conforming to the lower bound in [AGSV20] that optimal amplification may be impossible if the amplifier returns a superset of the input dataset. These observations show that the folklore way of enlarging datasets by learning the data distribution and adding more samples from the learned distribution can be far from optimal.

Connections with other statistical notions. An equivalent view of Definition 1.1 is through Le Cam’s distance [LC72], a classical concept in statistics. The formal definition of Le Cam’s distance $\Delta(\mathcal{M},\mathcal{N})$ is summarized in Definition 3.1; roughly speaking, it measures the fundamental difference in power in the statistical models $\mathcal{M}$ and $\mathcal{N}$, without resorting to specific estimation procedures. The sample amplification problem is equivalent to the study of Le Cam’s distance $\Delta(\mathcal{P}^{\otimes n},\mathcal{P}^{\otimes(n+m)})$ between product models, where (1) is precisely equivalent to $\Delta(\mathcal{P}^{\otimes n},\mathcal{P}^{\otimes(n+m)})\leq\varepsilon$. However, in the statistics literature, Le Cam’s distance was mainly used to study the asymptotic equivalence, where a typical target is to show that $\lim_{n\to\infty}\Delta({\mathcal{M}}_{n},{\mathcal{N}}_{n})=0$ for certain sequences of statistical models. For example, showing that localized regular statistical models converge to Gaussian location models is the fundamental idea behind the Hájek–Le Cam asymptotic statistics; see [LC72, LC86, LCY90] and [VdV00, Chapter 9]. In nonparametric statistics, there is also a rich line of research [BL96, BCLZ02, BCLZ04, RSH19] establishing asymptotic (non-)equivalences, based on Le Cam’s distance, between density models, regression models, and Gaussian white noise models. In the above lines of work, only asymptotic results were typically obtained with a fixed dimension and possibly slow convergence rate. In contrast, we aim to obtain a non-asymptotic characterization of $\Delta(\mathcal{P}^{\otimes n},\mathcal{P}^{\otimes(n+m)})$ in $(n,m)$ and the dimension of the problem, a task which is largely underexplored in the literature.

Another related angle is from reductions between statistical models. Over the past decade there has been a growing interest in constructing polynomial-time reductions between various statistical models (typically from the planted clique) to prove statistical-computational gaps, see, e.g. [BR13, MW15, BB19, BB20]. The sample amplification falls into the reduction framework, and aims to perform reductions from a product model $\mathcal{P}^{\otimes n}$ to another product model $\mathcal{P}^{\otimes(n+m)}$. While previous reduction techniques were mainly constructive and employed to prove computational lower bounds, in this paper we also develop general tools to prove limitations of all possible reductions purely from the statistical perspective.

Organization. The rest of this paper is organized as follows. Section 3 lists some notations and preliminaries for this paper, and in particular introduces the concept of Le Cam’s distance. Section 4 introduces a sufficiency-based procedure for sample amplification, with asymptotic properties for general exponential families and non-asymptotic performances in several specific examples. Section 5 is devoted to a learning-based procedure for sample amplification, with a general relationship between sample amplification and the $\chi^{2}$ estimation error, as well as its applications in several examples. Section 6 presents the general idea of establishing lower bounds for sample amplification, with a universal result specializing to product models. Section 7 discusses more examples in sample amplification and learning, and shows that these tasks are in general non-comparable. More concrete examples of both the upper and lower bounds, auxiliary lemmas, and proofs are relegated to the appendices.

We use the following notations throughout this paper. For a random variable $X$, let ${\mathcal{L}}(X)$ be the law (i.e. probability distribution) of $X$. For a probability distribution $P$ on a probability space $\Omega$ and a measurable map $T:\Omega\to\Omega^{\prime}$, let $P\circ T^{-1}$ denotes the pushforward probability measure, i.e. ${\mathcal{L}}(T(X))$ with ${\mathcal{L}}(X)=P$. For a probability measure $P$, let $P^{\otimes n}$ be the $n$-fold product measure. For a positive integer $n$, let $[n]\triangleq\{1,\cdots,n\}$, and $x^{n}\triangleq(x_{1},\cdots,x_{n})$. We adopt the following asymptotic notations: for two non-negative sequences $(a_{n})$ and $(b_{n})$, we use $a_{n}=O(b_{n})$ to denote that $\limsup_{n\to\infty}a_{n}/b_{n}<\infty$, and $a_{n}=\Omega(b_{n})$ to denote $b_{n}=O(a_{n})$, and $a_{n}=\Theta(b_{n})$ to denote both $a_{n}=O(b_{n})$ and $b_{n}=O(a_{n})$. We also use the notations $O_{c},\Omega_{c},\Theta_{c}$ to denote the respective meanings with hidden constants depending on $c$. For probability measures $P,Q$ defined on the same probability space, the total variation (TV) distance, Hellinger distance, Kullback–Leibler (KL) divergence, and the chi-squared divergence are defined as follows:

We will frequently use the following inequalities between the above quantities [Tsy09, Chapter 2]:

Next we define several quantities related to Definition 1.1. For a given distribution class $\mathcal{P}$ and sample sizes $n$ and $m$, the minimax error of sample amplification is defined as

where the infimum is over all (possibly randomized) measurable mappings $T:{\mathcal{X}}^{n}\to{\mathcal{X}}^{n+m}$. For a given error level $\varepsilon$, the maximum size of sample amplification is the largest $m$ such that there exists an $(n,n+m,\varepsilon)$ sample amplification, i.e.

For the ease of presentation, we often choose $\varepsilon$ to be a small constant (say $0.1$) and abbreviate the above quantity as $m^{\star}({\mathcal{P}},n)$; we remark that all our results work for a generic $\varepsilon\in(0,1)$. Finally, we also define the sample amplification complexity as the smallest $n$ such that an amplification from $n$ to $n+1$ samples is possible:

Note that all the above notions are instance-wise in the distribution class ${\mathcal{P}}$.

The minimax error of sample amplification (4) is precisely known as the Le Cam’s distance in the statistics literature. We adopt the standard framework of statistical decision theory [Wal50]. A statistical model (or experiment) ${\mathcal{M}}$ is a tuple $({\mathcal{X}},(P_{\theta})_{\theta\in\Theta})$ where an observation $X\sim P_{\theta}$ is drawn for some $\theta\in\Theta$. A decision rule $\delta$ is a regular conditional probability kernel from ${\mathcal{X}}$ to the family of probability distributions on a general action space ${\mathcal{A}}$, and there is a (measurable) loss function $L:\Theta\times{\mathcal{A}}\to\mathbb{R}_{+}$. The risk function of a given decision rule $\delta$ is defined as

Based on the definition of risk functions, we are ready to define a metric, known as Le Cam’s distance, between statistical models.

In the language of model deficiency introduced in [LC64], Le Cam’s distance is the smallest $\varepsilon>0$ such that the model ${\mathcal{M}}$ is $\varepsilon$-deficient to the model ${\mathcal{N}}$, and ${\mathcal{N}}$ is also $\varepsilon$-deficient to ${\mathcal{M}}$. In the sample amplification problem, $(P_{\theta})_{\theta\in\Theta}=\{P^{\otimes n}:P\in{\mathcal{P}}\},(Q_{\theta})_{\theta\in\Theta}=\{P^{\otimes(n+m)}:P\in{\mathcal{P}}\}$. Here, choosing $T_{2}(x^{n+m})=x^{n}$ in Definition 3.1 shows that ${\mathcal{N}}$ is $0$-deficient to ${\mathcal{M}}$, and the remaining quantity involving $T_{1}$ exactly reduces to the minimax error of sample amplification in (4). Therefore, studying the complexity of sample amplification is equivalent to the characterization of the quantity $\Delta({\mathcal{P}}^{\otimes n},{\mathcal{P}}^{\otimes(n+m)})$.

The first idea we present for sample amplification is the classical idea of reduction by sufficiency. Albeit simple, the sufficiency-based idea reduces the problem of generating multiple random vectors to a simpler problem of generating only a few vectors, achieves the optimal complexity of sample amplification in many examples, and is easy to implement.

The sufficiency-based approach of sample amplification is not always desirable. First, models outside the exponential family typically do not admit non-trivial sufficient statistics, and therefore the reduction by sufficiency may not be very helpful. Second, the identity map applied to the sufficient statistics only works for continuous models, and incurs a too large TV distance when the underlying model is discrete. Third, previous approaches are not directly related to learning the model, so a general relationship between learning and sample amplification is largely missing. In this section, we propose another sample amplification approach, and show that how a good learner helps to obtain a good sample amplifier.