Toward Understanding Generative Data Augmentation
Authors: Chenyu Zheng
Guoqiang Wu
Chongxuan Li
Venue: NeurIPS 2023 poster (2023)
Keywords: generative data augmentation
algorithmic stability
non-i.i.d. learning
TL;DR: Towards understanding modern generative data augmentation techniques.

Abstract: Generative data augmentation, which scales datasets by obtaining fake labeled examples from a trained conditional generative model, boosts classification performance in various learning tasks including (semi-)supervised learning, few-shot learning, and adversarially robust learning. However, little work has theoretically investigated the effect of generative data augmentation. To fill this gap, we establish a general stability bound in this not independently and identically
distributed (non-i.i.d.) setting, where the learned distribution is dependent on the original train set and generally not the same as the true distribution. Our theoretical result includes the divergence between the learned distribution and the true distribution. It shows that generative data augmentation can enjoy a faster learning rate when the order of divergence term is $o(\max\left( \log(m)\beta_m, 1 / \sqrt{m})\right)$, where $m$ is the train set size and $\beta_m$ is the corresponding stability constant. We further specify the learning setup to the Gaussian mixture model and generative adversarial nets. We prove that in both cases, though generative data augmentation does not enjoy a faster learning rate, it can improve the learning guarantees at a constant level when the train set is small, which is significant when the awful overfitting occurs. Simulation results on the Gaussian mixture model and empirical results on generative adversarial nets support our theoretical conclusions.

Toward Understanding Generative Data Augmentation
Chenyu Zheng!?, Guoqiang Wu², Chongxuan Li
Gaolling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China School of Software, Shandong University, Shandong, China guoqiangru90)@gmmm Sgmaall com; chongxuanli@ruc edu. cn
Abstract
Generative data augmentation, which scales datasets by obtaining fake labeled examples from a trained conditional generative model, boosts classification per- formance in various learning tasks including (semi-) jeeperisuper learning, few-shot learning, and adversarially robust learning. However, little work has theoretically investigated the effect of generative data augmentation. To fill this gap, we estab- lish a general stability bound in this not independently and identically distributed (non-i.i.d.) setting, where the learned distribution dependent train set and generally not the same as the true distribution. Our theoretical result includes the divergence between the learned distribution and the true distribution. It shows that generative data augmentation can enjoy faster learning rate when the order of divergence set size and Sm. is the corresponding stability constant. We further specify the learning setup to the Gaussian mixture model and generative adversarial nets. We prove that in both cases, though generative data augmentation does not enjoy a faster learning rate, can improve the learning guarantees at a constant level when the train set is small, which is significant when the awful overfitting occurs. Simulation results on the Gaussian mixture model and empirical results on genera- tive adversarial nets support our theoretical conclusions. Our code is available at httpp://giia...ooomMM../////eent
the original
is of max (log(m)33m. 1/
1/ym)), where m is the train
Introduction
Deep generative models 222 3
have achieved great success in many fields, including computer in the
vision 55 6. natural language processing 7 g 9. and cross-modal learning [10] 11 12
recent years. promising usage built upon them is generative data augmentation (GDA) 13 14 13), which scales the train set by producing synthetic examples with labels based on advanced conditional generative models. Empirically, it has been observed that GDA can improve classification performance in lots of settings, including supervised learning [16] 17 semi-supervised learning [18
19 20
few-shot learning 21 zero-shot learning 22] adversarial robust learning 23 24]. etc.
Although promising algorithms and applications GDA emerge in different learning setups, our experiments in Section 4 show that GDA does not always work, such in the with rich train set or standard augmentation methods (c.g.. flip). Besides, the number of augmented data has a significant impact on the performance while is often tuned manually. These phenomena motivate to study the effect of GDA. Unfortunately, little work has investigated this technique from a theoretical perspective. Therefore, in this paper, take first step towards understanding it. Specially, consider the supervised classification setting, and try to answer the following questions rigorously:
Can we establish learning guarantees for GDA and explain when it works precisely?
*Conespondence to Chongxuan Li.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

. Can we obtain theoretical insights on hyperparameters like the number of augmented data?
Our first main contribution is to propose general algorithmic stability bound for GDA in Section 3.1 The main technical challenge is that GDA breaks the primary i.i.d. assumption of the classical results [25 26 because the distribution learned by the generative model is dependent on the sampled train set and generally not the same as the true distribution. Besides, it is unclear whether the existing general non-i.i.d. stability bounds (27 28 29 are suitable to derive meaningful guarantees for GDA.
Informally, our result (Theorem 3.1 can be presented as follows:
Gen-errorl X distributions' divergence + generalization error w.r.t. mixed distribution,
where Gen-error means the generalization error of GDA, and S b means a = O The distributions' divergence term on the right hand is caused by the divergence between the distribution learned by the generative model and the true distribution. In addition, the remaining generalization error w.r.t mixed distribution vanishes as we increase the augmentation size. Comparing this bound to the classical result without GDA (Theorem 2.1), we can obtain an exact condition for GDA to be effective: GDA can enjoy a faster learning rate when the order of divergence term is o(max (log(m)33m) 1/mm)) where m is the train set size and B. is the corresponding uniform stability constant. This means the performance of the chosen generative model matters a lot.
Our second main contribution is to particularize the general results to the binary Gaussian mixture model (bGMM) and generative adversarial nets (GANs) 2 in Section 3.2 and Section 3.3] respec- tively. Our theoretical results (Theorems 3.2 and 3.3) show that, in both cases, the order of the 1/ /mm) Therefore, when the train set size is large enough, it is hopeless to use GDA to boost the classification performance by large margin. Worse still, GDA may damage the generalization of the learning algorithm. However, when the train set size is small and awful overfitting happens, GDA can improve the learning guaran- tee at a constant level, which significant in this situation. These theoretical implications show the promise of GDA in real-world problems with limited data.
divergence term in the obtained upper bound is 92 (max (log(m)),mm
Finally, experiments presented in Section 4 validate our theoretical findings. In particular, in the bGMM setting, experimental results show that our generalization bound (Theorem 3.2 predicts the order and trend of true generalization error well. Besides, in our empirical study on the real image dataset, we find that GANs can not boost the test performance obviously and even damage the generalization when standard data augmentation methods are used to approximate the case with a large train set. In contrast, GANs improve the performance by large margin when the train set size is small and terrible overfitting occurs. All these experimental results support our theoretical implications in Section[3] 3 Furthermore, we also conduct experiments with the state-of-the ooee--o--he-rrr art diffusion model [30]. Empirical results show the promise of the diffusion model in GDA and suggest it could have a faster learning rate than GAN.
Preliminaries
2.1 Notations
Let X C .dd be the input space and y C R be the label space. We denote by 'D the population
distribution over 2 = X x y. The Lp norm of a random variable X is denoted as ||X] 1|p = (E) (=))
Given set 5 = {z), 22. }. we define 5 as the set after removing the i-th data point in the set
S, and S' as the set after replacing the i-th data point with zi in the set S. Let [m] = {1, 2,
m
then for every set V C [r)]. we define Sv = {z. i E VJ. In addition, for some function f = S(S). denote its conditional L,p norm with respect Sy by llll. (Sv) (E(1)/II Sv))). Besides, we denote the total variation distance by Drv and KL divergence by DKL. respectively.
We let (y)x be the set of all measurable functions from X to y. A be a learning algorithm and A(S) E (y)x* be the hypothesis learned on the dataset S. Given a learned hypothesis A(S) and a loss function é (y)x² x Z RR,, the true error Ry (A(S)) with respect to the data distribution D is defined as R (E(A(()) 2)]. ). In addition, the corresponding empirical error (A()S) is defined as 1 ETh ((A(S))) z.).

---

2.2 Generative data augmentation
In this part, we describe the process of GDA in mathematical way. Given a training set S with my i.i.d. examples from D, we can train conditional generative model G, and denote the model distribution by (S). We note that the randomness from training the generative model is ignored in this paper. In addition, we define the expectation of the model distribution with regard to as De = [s
Based on the trained generative model, we can then obtain a new dataset SG with my i..d samples from (G()), where mg is hyperparameter. Typically, we consider the case that ma (mm)) if GDA is utilized. We denote the total number of the data points in augmented set S = S U Sa by mr- Besides, we define the mixed distribution after augmentation as D(S) ms D + my (S)) As result, hypothesis A(S) can be learned on the mey
augmented dataset 5. To understand the effect of GDA, we are interested in the generalization error [Ry (AA()) Rg(A(S)) with regard to the learned hypothesis A(S). For convenience, we denote by Gen-error in the remaining paper. Technically, we establish bounds for Gen-error using the algorithmic stability introduced in the next subsection. As far know, this is the first work to investigate the learning guarantees for GDA.
2.3 Generalization via algorithmic stability
Algorithmic stability analysis is important tool to provide guarantees for the generalization of machine learning models. A key advantage of stability analysis is that exploits particular properties of the algorithm and provides algorithn-dependen bounds. Different notations of stability have
been proposed and used establish high probability bounds for generalization error (25 31 32
33 Among them, uniform stability is the most widely used and has been utilized to analyze the generalization of many learning algorithms, including regularized empirical risk minimization (ERM)
algorithms [25) and stochastic gradient descent (SGD) (32 35). The uniform stability is defined as the following.
Definition 2.1 (Uniform stability). Algorithm A is uniformly Bm -ttable with respect to the loss function if the following holds
VS E 2m Vz E 2i E sm].sup ((A(S), -(AA(S)) z) S Pm.
Given a fm -table learning algorithm, the milestone work (25) provides a high probability gener- alization bound that converges when 3m = o(1/ (m). This condition may fail to hold in some modern machine learning settings [36]. which leads to meaningless guarantees. In recent years, some works 37 38 26) improved the classical bound by establishing novel and tighter concentration inequalities. Especially, (26] proposed a moment bound and obtained a nearly optimal generalization guarantee, which only requires 8m o(1/ log m) to converge. It is listed in the next theorem.
Theorem 2.1 (Corollary 8, (26). Assume that A is a Bm -table learning algorithm and the loss function l is bounded by M. Given training set S with m i.i.d. examples sampled from the distribution D, then any 8 E (0, 1). with probability at least - it holds that
( - (sss))))(((AS))) ((((S)) S Bm log (
+ DM
log m
(52
We note that all generalization bounds mentioned above require primary condition: data points are drawn i.i.d. according to the population distribution D. However, it no longer holds the setting of GDA. On the one hand, the distribution DDr(S) learned by the generative model is generally not the same as the true distribution D. On the other hand, the learned (S) is heavily dependent on sampled dataset S. This property brings obstacles to the derivation of the generalization bound for
GDA. Furthermore, though there exists some non-i.i.d stability bounds (27 28 29], it is still unclear whether these techniques suitable in the GDA setting.
3 Main theoretical results
In this section, we present our main theoretical results. Section 3.1 we establish a general
generalization bound (Theorem 3.I for GDA. Built upon the general learning guarantee, we then
3

---

particularize the learning setup to the bGMM introduced in Section 3.2.1 and derive a specified generalization bound (Theorem 3.2p. Finally, we discuss our theoretical implications on GANs in
real-world problems (Theorem 3.3 Notably, to the best of our knowledge, this is the first work to investigate the generalization guarantee of GDA.
3.1 General generalization bound
To understand GDA, we are interested in studying the generalization error of the hypothesis A()) learned on the dataset S after augmentation. Formally, we need to bound [Ry (AAS)) R (A()),, which has been defined as Gen-error in Section 2.2 2.2 Recall that D(S) has been defined the mixed
distribution after augmentation, to derive such a bound, we first decomposed Gen-error as
Gen-error
R& (A(()) (s)) (A((5)
Riss (A(()) -3 Rs()
Distributions divergence
Generaliztion ervor w.E.L. mixed distribution
The first term on the right hand can be bounded by the divergence (c.g., Drv, DKL) between the mixed distribution (SS) and the true distribution D. It is heavily dependent on the ability of the chosen generative model. For the second term, we note that classical stability bounds (e.g. Theorem 2.1 can not be used directly, because points in S are drawn non-i.i.d.. We mainly use a core property of S, that is, S satisfies the i.i.d. assumption, and SG satisfies the conditional i.i.d. assumption when S is fixed. Inspired by this property, we furthermore decompose this term and utilize sharp moment obtain an upper bound. Finally, we conclude with the following result.
inequalities 33 26
Theorem 3.1 (Generalization bound for GDA, proof in Appendix B.I. Assume that A is a 9m stable learning algorithm and the loss function f is bounded by M. Given an set S augmented as described in Section 2.2 then for any 8 E (0, 1), with probability at least 8, holds that
M ([mms- + vmc) + ms / mm
[Gen-error|
x m1
MDTv (D, (D.Do(S)) +
log
M&
Distribations divergence
BuT (ms logms mg + mg log ma) + mg log my MT(ms,
log 5
m&
where J(ms, ma) = sup; Drv (D (S), D (S*)).
Remark. Tightness of the proposed upper bound. Let mc = we observe that Theorem 3.1 degenerates to Theorem 2.1 Therefore, our stability bound includes the i.i.d. setting as a special case and benefits from the same nearly optimal guarantee shown by (26). Further analysis of the tightness of our guarantce when ma > 0 is left to future work.
Remark. Comparison with the existing non-i.i.d. stability bounds. Detailed introduction for non-i.idd stability bounds is placed in Section 5 We note that previous results (2 28 29 are
proposed for the general non-i.i.d. case. Therefore, they may fail to give awesome guarantees in this
special case. In Appendix C we show that it is hard to derive a better bound than Theorem 3.1 by using the existing non-i.i.d. stability results directly.
Remark. Stability of the learned distribution Dc((). T(ms, ma) in Theorem 3.1 reflects the stability of the learned distribution with regard to changing one data point in the training set received by the generative model. Our bound suggests that the more stable the model distribution is, the better performance can be achieved by GDA. As far as we know, though uniformly stability of some generative learning algorithms has been studied 40, the new notation T J(ms, mG) emerging in our bound has not been studied yet.
Remark. Selection of augmentation size. We first consider the order of the upper bound with respect to mg. Observing Theorem [31]] we find that the distributions' divergence term can not be controlled by increasing mg while the remaining generalization eгror w.r.t. mixed distribution will vanish. We note that there exists a trade-off between the fast learning rate and augmentation consumption. Typically, the augmentation consumption is caused by additional sampling, training, and storage. When the order of the divergence term smaller than that of the remains, increasing ma can induce faster convergence. Otherwise, increasing mg not lead to faster convergence but larger

---

consumption. Therefore, an efficient augmentation size Gorder with regard to the order of ms can be defined as follows:
orddrr = inf {generalization error w.r.t. mixed distribution S distributions' divergence). mG
Furthermore, without considering the cost, the optimal augmentation number m can be achieved by minimizing the upper bound directly. Unfortunately. is difficult to calculate an explicit form of or, and ma here due to the ignorance of fmr and T(ms, ma)- We will discuss them more concretely in the specified cases.
Remark. Sufficient conditions for GDA with (no) faster learning rate. We still consider the order of the learning guarantee with respect to my here. Let mg m orddrr it can found that
divergence Drv (D, (S)) plays an important role in deciding whether GDA can enjoy faster learning rate. Comparing Theorem with Theorem 2.1 (without augmentation), we can conclude sufficient conditions as follows.
Corollary 3.1. Assume that the loss function is bounded by M, we have
Drv (D, DG(()) maxx (log(m) 1/ m/m))) then GDA enjoys a faster learning rate.
Df (D, (D)) Ω (max (log(m))3m 1/ m/\m)) then GDA can not enjoy a faster
learning rate.
Notably, will present in Section 3.2 and 3.3 though GDA not enjoy faster learning rate in both special case, it is possible to improve the generalization guarantee at a constant level when my small, which is important when awful overfitting happens.
3.2
Theoretical results on bGMM
The bGMM is a classical but non-trivial setting, which has been widely studied in literature 41 In this section, we investigated it in the context of GDA. Simulations will be conducted in Section to verify these results.
42 4
3.2.1 Setting of bGMM
In this part, we introduce the data distribution configuration in the bGMM, as well as the corresponding linear classifier and conditional generative model. Similar setups of distribution and classifier have been adopted by many previous works
45 46
Distribution setting. We consider binary task where = 1), Given vector μ E I 1) and noise variance o² O, we assume that the distribution satisfies y ~ f-1, and a² T2). Besides, similarly to [47] assume that the distribution of y is known, which is satisfied conditional learning with labels.
N(yu,,
Simple linear classifier. We consider linear classifier parameterized by 0 E Rd in the form of prediction ÿ = s0 T x). Given m samples, learned by performing ERM with respect to the negative log- likeiioed loss function, that is,
1(0, (x, v))
20 (x - (xyyy) [0) (x-y0).
As result, this learning algorithm will return Ø 1 Σm v; which satisfies E(O) μ.
Conditional generative model. We consider a simple generative model parameterized by My of where y E 1) and & E [d]. It learns the parameters of Gaussian mixture distribution directly. Given m data points, let my be the number of samples class y, it returns
Σ Σy.=y my
my Σ my (IiR Fyy
Fy
m
my
which are unbiased estimators of +1 and a², respectively. Based on the learned parameters, can perform GDA by generating new samples from the distribution ~ uniform(-1, 1}. A (p E), where Σ diag(o?....,
5

---

3.2.2 Theoretical results
In this section, we establish the generalization bound for bGMM based the general bound proposed
Theorem 3.1 To derive such a bound, the main task is to bound terms M, 3m DTv (D, Pc()))
and J(mg, mG) in Theorem 3.1 For M (Lemma B.5) and Bmr (Lemma B.6 we mainly use the
concentration property of the multivariate Gaussian variable (L.emma [.4). In addition, inspired by previous works on naïve Bayes 48), we bound Drv (D, (S)) (Lemma B.7p 7 by discussing the distance between the estimated parameters and the true parameters of bGMM. Besides, the concentration property of J mG) (Lemma B.9 can be induced by the preceding discussion. Finally, we can obtain the following results.
Theorem 3.2 (Generalization bound for bGMM, proof in Appendix B.2
Consider the setting introduced in Section 3.2.7 Given a set S with my i..d samples from the bGMM distribution and an augmented set Sq with ma i.i.d. samples drawn from the learned Gaussian mixture distribution. then with high probability at least
holds that
(mg))
if fix d and ma = 0,
Vms log (mg)
if fix d and me (ms))
Geen-errrr S
(2)
log(mgg Vmg d
if fix d and me mogooder
fix ms.
Remark. Explicit upper bound of generalization error. 19 in Appendix B.2 gives us an explicit form to predict the generalization error in the bGMM setting. In Section 4.1 we will see that (19) predicts the order and trend of true generalization error well, which verifies the correctness of the proposed learning guarantee in the bGMM setting.
Remark. Negative learning rate of GDA. Even though we estimate the sufficient statistics of the Gaussian mixture distribution (1z and σ²) directly in this special case, we can not hope enjoy better learning rate. Things could be worse when we model the distribution in reality (e.g., images, texts), which suggests that when original samples are abundant, further performing GDA based on existing generative models can not improve the generalization. Theorem 3.3 supports this viewpoint. Remark. Improvement at constant level matters a lot when overfitting happens. From (2) we know that when my is small and d is large, the curse of dimensionality happens, which leads to an awful generalization error. In this case, though GDA can only improve it at a constant level by controlling the generalization error w.r.t. mixed distribution, the effect is obvious due to the large scale of d. We note that it is challenging to obtain explicit form of the constant-level improvement due to the complexity of the generalization bound. Therefore, we clarify this more clearly by comparing the cases where mc (without GDA) and me toc in Corollary of Appendix B.2
3.3 Implications on deep generative models
Nowadays, data augmentation with deep generative models is widely used and received lots of attention. Therefore, benefiting from the recent advances in the generative adversarial network (GAN) 49] and SGD [0]. we discuss implications of our theory on real problems, which will be verified by the empirical experiments in Section 4.2
3.3.1 Learning setup
We consider the general binary classification task in the deep learning era. In this part, we introduce the setup of data distribution, deep neural classifier, learning algorithm, and deep generative model.
Distribution setting. We assume that input space satisfies X C |0, 1]d, and our analysis can be easily extended to any bounded input space. This assumption generally holds in many practical problems, for example, image data satisfies X [0, 255]d. Similarly to bGMM, we let (-1,,) 1) and assume that the distribution of y is known.
Deep neural classifier. We consider general L-layer multi-layer perception (MLP) or convolutional neural network (CNN) /(w,,) 2 - IR, where w denotes its weights and w, denotes the weights in the 1-th layer. Its abstract architecture is consistent with that in [50), and details can be found

---

in Appendix A.1 In addition, we suppose the deep neural classifier satisfies smoothness and boundedness assumptions, which are adopted by many previous works (34 35 50 ST].
Assumption 3.1 (Smoothness). We assume that f(w, .) is 1-smooth with respect to w, that is,
(V ff(,, 7/|lw W2ll2 for any W1 and W2-
Assumption 3.2 (Boundedness). We assume that for all I e [L], there exists constant W₁, which
satisfies | 2| S W/
Learning algorithm for the deep neural classifier. The setting of the learning algorithm is conformed to the practice. We assume that the loss function is the binary cross-entropy loss &(f, (x. v)) = log(1 + exp(-yf (w))) and it is optimized by SGD. For the t-th step, we set the step size as .f
for some positive constant c. Besides, we assume that the total iteration number T= (mr). These configurations are adopted by past works on the stability of SGD 34 35
Deep generative model. We choose GAN as our deep generative model, which is parameterized by MIP. Its abstract architecture the same as that in Theorem 19 of [49], and details are placed in Appendix A.2] Besides, due to the lack of conditional generative model theory, we make a naive approximation here by assuming that each category is learned by a GAN, respectively.
3.3.2 Theoretical results
Similarly to the bGMM setting, we establish a generalization bound for the deep learning setup. To reach this goal, we bound terms M, Smy. and Dry (D, Ds)))) based on the recent results on GAN 449 and SGD 29 50). First, boundedness and Lipschitzness of classifier f can be induced from Assumption 3.2 (Lemma B. Second, the boundedness of f directly implies the upper bound for M because the binary cross-entropy loss is I-Lipschitz with respect to f. Third, by combining the Lipschitzness and smoothness of f. we can bound 3my for SGD (Lemma B. 11 Finally, Dr (D, (D()) can be bounded by the result in 49 (Lemma B.
Theorem 3.3 (Generalization bound for GAN, proof in Appendix Consider the setup introduced
in (.3tlion3.3.1 Given set S with ms i.i.d. samples from any distribution 'D and augmented set So with ma i..dd examples sampled from the distribution Da(S) learned by GANs, then any
fixed 6 E (0, 1), with probability at least 1 - 8, it holds that
if W, L, d, let ma 0. fix W, L d, let mg = (ms)),
ymg
7
log(ms)) mg
log (m mc)
max
EJ Gen-erro
V2
1/
lug(ms)) ms
if fix W, L, let mg me.order
d.t.2
(TL [ell2)
2
ffx ms-
Remark. Slow learning rate with GDA. Upper bounds in Theorem 3.3 3.3 show that when we perform GDA, the order with regard to my strictly becomes worse. Therefore, implies that when my is large enough, is hopeless to boost the performance obviously by augmenting the train set based on GANs. On the contrary, GDA may make the generalization worse.
Remark. GDA matters lot when overfitting happens. From Theorem 3.3 the data dimension and model capacity become larger, the deep neural classifier trained with SGD becomes easier overfit the train set and gain terrible generalization performance. In this case, constant-level improvement of generalization caused by GDA will be significant. Similarly to the bGMM setting, clarify the constant-level improvement by comparing the cases where ma (without GDA) and mG - +oo in Corollary B.2 of Appendix B.3
know that as
4 Experiments
In this section, we conduct experiments to verify the results in Section 3 which are two-folded:
We conduct simulations in the setting of bGMM and validate the results in Theorem 3.2
We empirically study the effect of GDA on the real CIFAR-10 dataset our theoretical implications on GANs.
which supports
7

---

Y-00
0.002
0.10
Gen Broor
0.08
0.94
0092
0.00
100
250
300
400
500
20
40
100
20
40
60
100
Training set size
(a) 1, truth
(b) (d, my)) = (1, 40), truth
(c) (d. ms) = (1,4 prediction
190
Gmn Emrrr
120
100
5.0
2.5
90
1.5
100
Limession
V
V
(d) ms 10, truth
(c) (d, ms) (50, 10), truth (d, ms) (50, 10), prediction
Figure 1: Simulations results on the bGMM setting, We do not integrate the truths and predictions due to the difference between their y-axis scale.
4.1 Simulations on bGMM
let μ = (1/vd,..., 1/V/) to satisfy || o² 0.6², and randomly generate 10,000 samples according to the Gaussian mixture distribution the test set. We approximate the Gen-error by the gap between the training error and the test error. To eliminate randomness, we average over 1,000 random runs and report the mean results. We denote 7 mg/ms in this section.
First, we investigate the case that data dimension d fixed. To verify the order is near to 0 m (log m can be ignored with respect to /m,g), we fix d 1, and change mg from 20 to 500. For each selected ms, we adjust yy from 0 to to generate new samples in different levels. The result presented in Figure la which shows that the generalization error decreases in near O(1/ O(L//ms) /ms) order. Besides, generalization error without GDA is always (near) optimal, which empirically proves that GDA is ineffective when ms is large enough.
Second, we conduct simulations in the case that mg is fixed as small constant. To verify the order is (d). we fix ms 10, and change d from 2 to 100. For each selected d, we also adjust from 0 to 50. The result is displayed in Figure Id which shows that the generalization error increases in (d) order. In addition, when d is large (e.g.. 100) and the curse of dimensionality happens, generalization error with larger y is better by big margin, which suggests that though GDA could only enhance at constant level, the effect is significant when overfitting occurs.
Third, we design experiments validate whether the upper bound in Theorem 3.2 can predict the trend of generalization error well. Similarly to previous theoretical works (e.g. [53]), we find an approximation of (19) in Appendix as our prediction by replacing log(a/6) with log(a) if a of else 1. We plot the ground truths and predictions in the case that (d, m.) = (1, 40) and (50, 10), respectively. Results in Figure show that our bound predicts the trend of generalization error well. Therefore, an approximation of the optimal augmentation size m can be found by minimizing (19).
4.2 Empirical results on CIFAR-10
In this part, we conduct experiments on the real CIFAR- dataset with ResNets (44 and various deep generative models, including conditional DCGAN (cDCGAN) (55] StyleGAN2-ADA [56] and elucidating diffusion model (EDM) 30). Details of experiments (e.g. motivation, model architecture,
training) be found in Appendix D
To validate our theoretical implications in Section 3.3
we are supposed to discuss two cases, where one mg is small and the other m, is large. The two cases can be approximated by whether performing another data augmentation. We additionally use the standard data augmentation (44 to approximate the case with large m.s Then, for each selected ResNet and generative model, set my from 0 to

---

Table Accuracy the CIFAR-10 test set, where S.A. denotes standard augmentation.
GDA (mc)
Generator
Classifier
S.A.
0
100k
300k
500k
700k
1M
X
85.76
86.8
87.83
87.59
87.52
86.47
ResNet18
V
94.4
93.92
93.41
93.81
93.01
92.6
85
86.9
87.93
87.56
87.17
86.28
cDCGAN 15
ResNet34
V
94.59
94.83
94.21
93.64
93.69
93.18
82.85
87.49
88.59
86.67
86.3
85.2
ResNet50
94.69
94.43
93.86
93.74
93.12
92.63
85.76
90.22
91.33
91.37
91.25
91.38
ResNet18
94.4
94.68
94.46
94.4
94.11
94.12
85
90.24
91.23
91.45
91.56
90.91
StyleGAN2-ADA
56
ResNet34
V
94.59
95.05
94.9
94.4
94.43
94.21
82.85
90.85
92.29
92.29
92.29
91.61
ResNet50
94.69
94.74
95.04
94.56
94.76
94.28
85.76
92.8
94.87
95.43
96.24
96.28
R
94.4
96.15
96.74
97.09
97.28
97.5
85
93.42
94.93
95.59
96.14
96.44
EDM
30
ResNet34
V
94.59
96.47
96.96
97.36
97.53
97.51
82.85
93.29
95.29
95.95
96.1
96.64
ResNet50
V
94.69
96.09
96.87
97.28
97.6
97.74
IM and record the accuracy of the trained classifier on the CIFAR-10 test set. Results are presented in Table [ We further empirically verify our theory by estimating the generalization definition, given a trained neural classifier, the generalization error of Theorem 3.3 can be estimated by the absolute gap between the mean cross-entropy loss the training set (with generated data) and the mean cross-entropy loss on the test set. We place the results and analysis with this estimator at Table in Appendix D.7 In the following, we interpret our experimental results.
directly. By
GANs improve the test performance of classifiers when overfitting occurs. When standard augmentation is not used, ResNets trained the train set consistently suffer from overfitting. However, this can be relieved by data augmentation based on GANs, though cDCGAN can not generate high-quality images. This phenomenon supports the implications from Theorem 3.3
We can not have an obvious improvement by using GANs when my approximately large. When standard augmentation is used, deep neural classifiers trained on the CIFAR- 10 dataset achieve non-trivial performance. this case, GDA with cDCGAN always damages the generalization ability. Though use StyleGAN2-ADA, which achieves state-of-the-an conditional image generation performance on the CIFAR-I0 10 dataset, we can not boost the performance of classifiers obviously, and even consistently obtain worse test accuracy when mg is 500k IM.
Diffusion probabilistic models are promising for GDA. diffusion models show their excellent ability on image generation, a natural question emerges: are diffusion models more suitable for GDA? We choose the EDM that achieves state-of-the-art FID scores as the generator. Table in Appendix D.7 shows that EDM improves the test accuracy obviously, even though the standard augmentatron has been utilized. This suggests that diffusion models enjoy DrV (D, Da(()) with faster convergence rate than GANs, and shows the promise of diffusion models in GDA.

---

5 Related work
Data augmentation practice and theory. Data augmentation 157 58
is a universal method
to improve the generalization ability of deep neural networks in the case of insufficient training data. Classical data augmentation methods include geometric transformations [54], color space
transformations [59], kernel filters (60), mixing images [6]], random erasing [62] feature space
augmentation 63 etc. There are also many theoretical works studying the effect of classical data
augmentation methods from different perspectives 664
65
66
67 (68)
With the advance of deep generative models, GDA becomes novel and promising data augmentation technique. For example, [16] shows that augmenting the ImageNet training set [69] with samples from the conditional diffusion models significantly improves the classification accuracy. However, little work has investigated the theory of GDA. Both empirical success and theoretical opening encourage us to study the role of GDA.
Algorithmic stability theory. Classical results 22 26 introduced detailedly in Section 2 has various extensions. Prominent work (4 focuses on the uniform stability of SGD and derive generalization bounds for it. (35 improves the results in 34 and obtains tight guarantees for the stability of SGD,
which is used in Theorem 3.3
Establishing stability bounds under non-i..d. settings has also received a surge of interest in recent years. A major line models the dependencies by mixing models 170, [T] and derives stability bounds with mixing coefficients [27] (72.. However, it is usually difficult to estimate the mixing coefficients quantitatively. To avoid this problem, another line qualitatively models the dependencies by graphs. Recently, [29] derive general stability bound for dependent settings characterized by forest complexity of the dependency graph. However, is hard to use these techniques to derive a better bound than Theorem 3.1 for GDA, which is discussed detailedly in Appendix C
Convergence of deep generative models. addition to the bound for Drv (DS) with respect to GANs [4] we used in Theorem 3.3 there are attempts to derive such bound for diffusion models 73 74
75 [66. Informally, they mainly assume that estimation error of score function is bounded, then with an appropriate choice of step size and iteration number, diffusion models output a distribution which is close to the true distribution. However, is still unclear how to derive learning guarantees with respect to the train set size ms directly. Once such learning guarantees established, we can directly analyze the effect of GDA with diffusion models by Theorem 3.1
Impacts and limitations
This paper is mainly a theoretical work and first step towards understanding the GDA, and it can give some insights to the practice. Theorem [3.1 implies that improving the distribution approximation performance of the generative models is important for the GDA, which motivates people to design better generative models. Besides, it shows that stabilizing the training of the generative models can bring benefits to the GDA, which motivates us to improve the stability of the training of generative models (e.g. GAN). Furthermore, it implies that if we can estimate terms in the bound, then the optimal augmentation size can be approximated. With the emergence of more advanced theory, our results can be extended to other settings (e.g., diffusion models, self-supervised learning) and give more guidance to the practice. One limitation is that our results do not enjoy tightness guarantees, though they benefit from the same nearly optimal guarantee shown by 226 when mG = The derivation of lower bounds can be left to future work.
immplee
7 Conclusion
In this paper, we attempt to understand modern GDA techniques. To realize this goal, we first establish a general algorithmic stability bound in this non-i.i.d setting. suggests that GDA enjoys a faster learning rate when the divergence term Drv (D. (G)))) o(max (log(m)3m- 1/ /m)) Second, We specify the learning guarantee to the bGMM and GANs settings. Theoretical results show that, in both cases, though GDA can not enjoy a faster learning rate, it is effective when terrible overfitting happens, which suggests its promise in learning with limited data. Finally, experimental results support our theoretical conclusions and further show the promise of diffusion models in GDA.
10

---

Acknowledgement
This work was supported by NSF of China (Nos. 62076145, 62206159); Beijing Outstanding Young Scientist Program (No. (0NZZYHH00001100002200000
Shandong Provincial Natural Science Foundation (No. ZR2022QF117); Major Innovation Planning Interdisciplinary Platform for the "Double-First Class" Initiative, Renmin University of China; the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University China (No. 22XNKJ13); Fundamental Research Funds of Shandong University. C. Li was also sponsored by Beijing Nova Program (No. 20220484044).
References
[1] Diederik Kingma and Max Welling. Auto-encoding variational bayes. In ICLR, 2014.
[2] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(1 1):139-144, 2020.
[3] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In NeurlPS, 2020.
[4] Yang Song, Jascha Ben Poole. Score-based generative modeling through stochastic differential equations. In ICLR, 2021.
Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and
[5] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In ICML, pages 8821-8831, 2021.
[6] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer. High- resolution image synthesis with latent diffusion models. In CVPR. pages 10684-10695, 2022.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. NeurIPS, 33:1877-1901 2020.
[8] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(1):5485-554 2020.
[9] Christoph Leiter, Ran Zhang, Yanran Chen, Jonas Belouadi, Daniil Larionov, Vivian Fresen, and Steffen Eger. Chatgpt: A meta aneal-analysi after 2.5 months. CoRR, a3s/2200..13795, 2023.
[10] Wenhui Wang, Hangbo Bao, Li Dong, Johan Bjorck, Zhiliang Peng, Qiang Liu, Kriti Aggarwal, Owais Khan Mohammed, Saksham Singhal, Subhojit Som, and Furu Wei. Image as foreign language: Beit pretraining for all vision and vision-language tasks. CoRR, abs/2208. 10442, 2022.
[11] Fan Bao, Shen Nie, Kaiwen Xue, Chongxuan Li, Shi Pu, Yaole Wang, Gang Yue, Yue Cao, Hang Su, and Jun Zhu. One transformer fits all distributions in multi-modal diffusion at scale. CoRR, abs/2303.06555, 2023.
[12] OpenAl. GPT-4 technical report. CoRR, abs/2303.08772 2023.
[13] Konstantin Shmelkov, Cordelia Schmid, and Karteek Alahari. How good is my gan? In ECCV, volume 11206, pages 218-234, 2018.
[14] Toan Tran, Trung Pham, Gustavo Carneiro, Lyle J. Palmer, and Ian D. Reid. A bayesian data augmentation approach for learning deep models. In NIPS, pages 2797-2806, 2017.
[15] Shin'y ya Yamaguchi, Sekitoshi Kanai, and Takeharu Eda. Effective data augmentation with multi-domain learning gans. In AAAI, pages 6566-6574, 2020.
11

---

[16] Shekoofeh Azizi, Simon Kornblith, Chitwan Saharia, Mohammad Norouzi, and David J. Fleet. Synthetic data from diffusion models improves imagenet classification. CoRR, abs/2304.08466, 2023.
[17] Victor Besnier, Himalaya Jain, Andrei Bursue, Matthieu Cord, and Patrick Pérez. This dataset does not exist: Training models from generated images. In ICASSP, pages 1-5, 2020.
[18] Diederik P. Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi- supervised learning with deep generative models. In NIPS, pages 3581-3589, 2014.
[19] Chongxuan Li, Taufik Xu, Jun Zhu, and Bo Zhang. Triple generative adversarial nets. In NIPS, pages 4088 4098, 2017.
[20] Zebin You, Yong Zhong, Fan Bao, Jiacheng Sun, Chongxuan Li, and Jun Zhu. Diffusion models and semi-supervised learners benefit mutually with few labels. CoRR, abs/2302. 10586, 2023.
[21] Brandon Trabucco, Kyle Doherty, Max Gurinas, and Ruslan Salakhutdinov. Effective data augmentation with diffusion models. CoRR, abs/2302.07944, 2023.
[22] Ruifei He, Shuyang Sun, Xin Yu, Chuhui Xue, Wenqing Zhang, Philip H. S. Torr, Song Bai, and Xiaojuan Qi. synthetic data from generative models ready for image recognition? CoRR, abs/2210.07574, 2022.
[23] Sylvestre-AIvis Rebuffi, Sven Gowal, Dan A. Calian, Florian Stimberg, Olivia Wiles, and Timothy A. Mann. Fixing data augmentation to improve adversarial robustness. CoRR, abs/2103.01944 2021.
[24] Zekai Wang. Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. CoRR, abs/2302.04638, 2023.
[25] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526 2002.
[26] Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In COLT, volume 125, pages 610-626, 2020.
[27] Mehryar Mohri and Afshin Rostamizadeh. Stability bounds for non-i.idd processes. In John C. Platt, Daphne Koller, Yoram Singer, and Sam T. Roweis, editors, NIPS, pages 1025-1032, 2007.
[28] Mehryar Mohri and Afshin Rostamizadch. Stability bounds for stationary phi-mixing and beta-mixing processes. Journal of Machine Learning Research, 11:789-814, 2010.
[29] Rui Ray Zhang, Xingwu Liu, Yuyi Wang, and Liwei Wang. Mcdiarmid-type inequaaliies for graph-dependent variables and stability bounds. NeurIPS, pages 10889-10899, 2019.
[30] Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of 2022.
diffusion-based generative models. CoRR,
[31] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11 11:2635-2670, 2010.
[32] Ilja Kuzborskij and Christoph H. Lampert. Data-dependent stability of stochastic gradient descent. In ICML, volume 80, pages 2820-2829, 2018.
[33] Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In ICML, volume 70, pages 2159-2167, 2017.
[34] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In ICML,, volume 48, pages 1225-1234, 2016.
[35] Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of SGD: tightness analysis and improved bounds. In UAI, volume 180, pages 2364- 2373, 2022.
12

---

[36] Yue Xing. Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. In NeurIPS. pages 26523-26533 26535, 2021.
[37] Vitaly Feldman and Jan Vondrák. Generalization bounds for uniformly stable algorithms. In NeurIPS, pages 9770-9780, 2018.
[38] Vitaly Feldman and Jan Vondrák. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In COLT, volume 99, pages 1270-1279, 2019.
[39] Stéphane Boucheron, Gābor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[40] Farzan Farnia and Asuman E. Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In ICML, volume 139, pages 3174-3185, 2021.
[41] Vittorio Castelli and Thomas M. Cover. The relative value of labeled and unlabeled samples in pattern recognition with unknown mixing parameter. IEEE Trans. Inf. Theory, 42(6):2102-
2117, 1996.
[42] Shotaro Akaho and Hilbert J. Kappen. Nonmonotonic generalization bias of gaussian mixture models. Neural Comput., 12(6): 141::1411 2000.
[43] Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting, and regularization. SIAM Journal Mathematics of Data Science, 4 4(1):260-284, 2022.
[44] Haiyun He, Hanshu Yan, and Vincent YF Tan. Information-theoreiic characterization of the generalization error for iterative supe-supe learning. Journal of Machine Learning Research, 23:1-52, 2022.
[45] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry, Adversarially robust generalization requires more data. In NeurIPS, pages 5019-5031, 2018.
[46] Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stanforth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? In NeurIPS, pages 12192-12202, 2019.
[47] Fan Bao, Chongxuan Li, Jiacheng Sun, and Jun Zhu. Why are conditional generative models better than unconditional ones? CoRR, abs/2212.00362, 2022.
[48] Andrew Y. Ng and Michael I. Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. In NIPS, pages 841-848, 2001.
[49] Tengyuan Liang. How well generative adversarial networks learn distributions. Journal of Machine Learning Research, 22:228:1-228:: 2021.
[50] Mingze Wang and Chao Ma. Generalization enror bounds for deep neural networks trained by SGD. CoRR, 0tss/2206.03299 2022.
[51] Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. In NIPS, pages 6240-6249, 2017.
[52] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Canadian Institute for Advanced Research, Toronto, ON, Canada, 2009.
[53] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine Learning, 19(1-2) 2010.
[54] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[55] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. In ICLR, 2016.
13

---

[56] Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. In NeurIPS, 2020.
[57] Connor Shorten and Taghi M. Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6:60, 2019.
[58] Connor Shorten, Taghi M. Khoshgoftaar, and Borko Furht. Text data augmentation for deep learning. Journal of Big Data, 8(1):101, 2021.
[59] Aranzazu Jurio, Miguel Pagola, Mikel Galar, Carlos Lopez-Molina, and Daniel Paternain. comparison study of different color spaces in clustering based image segmentation. In Information Processing and Management of Uncertainty in Knowledge- Based Systems., pages 532-541. Springer, 2010.
[60] Guoliang Kang. Xuanyi Dong, Liang Zheng, and Yi Yang. Patchshuffle regularization. CoRR, abs/1707.07103, 2017.
[61] Hiroshi Inoue. Data augmentation by pairing samples for images classification. CoRR, abs/1801 0.029,, 2018.
[62] Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data augmentation. In AAAI, volume 34, pages 13001-13008, 2020.
[63] Terrance VeVei and Graham W. Taylor. Dataset augmentation in feature space. In ICLR Workshop Track Proceedings, 2017.
[64] Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. A kernel theory of modern data augmentation. In ICML, volume 97 of Proceedings of Machine Learning Research, pages 1528-15377 2019.
[65] Sen Wu, Hongyang R. Zhang, Gregory Valiant, and Christopher Ré. On the generalization effects of linear transformations in data augmentation. In ICML, volume 119, pages 10410- 10420, 2020.
[66] Boris Hanin and Yi Sun. How data augmentation affects optimization for linear regression. In NeurlPS, pages 8095 8105, 2021.
[67] Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation feature manipula- tion. In ICML, volume 162, pages 19808, 2022.
[68] Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. The benefits of mixup for feature learning. CoRR, abs/2303.08433, 2023.
[69] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In CVPR, pages 248-255, 2009.
[70] Murray Rosenblatt. central limit theorem and strong mixing condition. Proceedings the national Academy of Sciences, 42(1):43-47, 1956.
[71] VA Volkonskii and Yu A Rozanov. Some limit theorems for random functions. i. Theory of Probability & Its Applications, 4(2):178-119, 1959.
[72] Fangchao He, Ling Zuo, and Hong Chen. Stability analysis for ranking with stationary m-mixing samples. Nenrocomputing, 171:1556-1562, 2016.
[73] Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R. Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. CoRR, abs/2209.11211 1215, 2022.
[74] Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In ALT, volume 201, pages 946-985, 2023.
[75] Xingehao Liu, Lemeng Wu, Mao Ye, and Qiang Liu. Let us build bridges: Understanding and extending diffusion generative models. CoRR, abs/2208. 14699, 2022.
14

---

[76] Valentin De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. CoRR. abs/2208.05314, 2022.
[77] Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. CoRR, fes/1505.00880 2015.
[78] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[79] Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Trans. Inf. Theory, 69(11))5973-
6006, 2016.
[80] Chenyu Zheng, Guoqiang Wu, Fan Bao, Yue Cao, Chongxuan Li, and Jun Zhu. Revisiting discriminative vs. generative classifiers: Theory and implications. CoRR, abs/2302.02334, 2023,
[81] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, regh-performance deep learning library. In NeurlPS, pages 8024 8035, 2019.
15


Reviews:
[{"review_id": "OoUAgK7VoI", "reviewer": "Reviewer_SG4V", "summary": "In this work the authors present new theoretical results for generative data augmentation. In particular, the authors introduce a new result that gives a bound on the generalization error of a model trained with data augmentation provided by a generative model. The authors use this bound to illustrate when GDA may or may not help in generalization performance. The authors then provide specific examples of applications of this bound to common models for generative augmentation; a binary Gaussian mixture and a deep generative model (GAN). For each the authors derive a more specialized bound and perform empirical experiments to validation the theory.", "questions": "- I was very confused by the usage of the term \"learning rate\" in the context here. I think I now understand it to refer to rate at which the generalization bound shrinks as a function of the amount of data, but given that the paper also discusses SGD, where the term has a different meaning it's hard to follow. Or is there some connection that I'm not appreciating?\n- I'm similarly a bit confused by what is meant by \"augmentation consumption\" on line 166. Can you elaborate on this?\n- I found the overloading of $d$ as both the data dimension and as a way to denote a divergence confusing, particularly for theorem 3.2.\n- Can you offer further any insight into when and why GDA does help in practice?", "limitations": "The authors discuss limitations.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This work provides useful theoretical insight into the strengths and limitations of generative data augmentation. The authors present novel results that, to my knowledge, are the first results bounding the generalization error for models trained with the aid of generative data augmentation. \n- I have not checked proofs in the appendix, but the theory as presented in the main text seems sound.\n- The applications to both the binary Gaussian mixture and GAN setting are helpful for illustrating and expanding upon the main theoretical results.\n- The experimental results do support the theoretical results presented and the results on DGM showing the re-affirming the promise of diffusion models for this purpose are interesting.\n- The results presented could be a useful foundation for future work.", "weaknesses": "- The deep generative model results presented are narrow in scope, applying to GANs trained in a class-separated manner and to fully-supervised learning, rather than potentially semi-supervised learning or transfer learning via generative models. \n- As mentioned by the authors, they do not investigate the tightness of the proposed bounds.\n- I'm not sure this type of data augmentation approach is widely used enough for this analysis to be immediately impactful, though it does appear to be gaining traction.\n- The clarity of the writing could be improved in places.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer SG4V\n\nWe thank Reviewer SG4V for the positive score and valuable comments.\n\n## Weakness 1: Scope of  Theorem 3.3\n\nThanks for the helpful suggestion. Though we choose specified GANs and supervised learning in Theorem 3.3, **our general framework (Theorem 3.1) is a foundation and can be extended to other generative models and training methods**.\n\n* \"GAN\". The proposed framework (Theorem 3.1) can also be used to analyze other generative models, as long as we can estimate the  $d_{TV}(D, D_G(S))$, and $\\mathscr{T}(m_S, m_G)$ in the concrete case.\n* \"Class-separated manner\". Deriving the generalization bound ($d_{TV}(D, D_G(S))$) for the conditional generative models is still challenging in the literature. As a preliminary work to understand the GDA, we assume the \"class-separated manner\" to simplify the analysis. With the emergence of better analysis for the conditional generative models, our results can also be further improved.\n* \"Fully-supervised learning\".  As a first step towards understanding the GDA, it is reasonable to investigate the basic supervised classification setting. Besides, the non-i.i.d. result of supervised learning is a starting point, which can inspire the derivation of other training methods (e.g. semi-supervised learning).\n\nWe will clarify these more clearly in the final version.\n\n## Weakness 2: Tightness of our bounds\n\nThanks for the suggestion. In general, finding the lower bounds for the stability generalization bounds is still an open topic (e.g., see [23]).  In this paper, **our results are tighter than using the existing non-i.i.d. bounds directly** (see Appendix C). The lower bounds can be left to future works. We will discuss this more detailedly in the Limitations section.\n\n## Weakness 3: Conditional data augmentation\n\nThanks for the nice suggestion. **Class-conditional generative data augmentation has been widely used**, and can empirically improve performance in lots of settings, including supervised learning [13, 14], semi-supervised learning [15, 16, 17], few-shot learning [18], zero-shot learning [19], adversarial robust learning [20, 21], etc (see line 25-26).\n\n## Weakness 4: Clarity of the writing\n\nThanks for the helpful suggestion. We will try our best to improve the clarity of the writing in the final version.\n\n## Q1: \"Learning rate\"\n\nThanks for the helpful advice. Yes, in this paper **except line 258**, it refers to the rate at which the generalization bound shrinks as a function of the amount of data ($m_S$ in this paper). On line 258, it means the step size of the SGD. We will avoid this ambiguity in the final version by **replacing the \"learning rate\" on line 258 with \"step size\"**.\n\n## Q2: \"Augmentation consumption\"\n\nThanks for the suggestion. The consumption can be divided into three parts. First, **sampling consumption**. Sampling more data will need more computation. Second, **store consumption**. More sampled data will need more memory to store. Third, **training consumption**. Given more generated data, if we fix the number of training epochs, the training of the downstream tasks will take more time. We will clarify this definition in the final version.\n\n## Q3: Overloading of $d$\n\nThanks for the suggestion. We will avoid the ambiguity in the final version by **using $\\mathcal{D}$ to denote the divergence**.\n\n## Q4:  When and why GDA does help in practice?\n\nThanks for the suggestion. It can be divided into two cases, one with large $m_S$ and the other with small $m_S$ (compared with other terms in the bound), detailed as follows.\n\n* Large $m_S$. In the Corollary 3.1, we conclude that if $d_{TV}(D, D_G(S)) = o \\left(\\max (\\log(m)\\beta_m, 1/ \\sqrt{m}) \\right)$, then using the GDA enjoys a lower generalization error than not using the GDA, which is because the generative model learns faster than the classifier. In both the bGMM and GANs settings, we prove that $d_{TV}(D, D_G(S)) = \\Omega \\left(\\max (\\log(m)\\beta_m, 1/ \\sqrt{m}) \\right)$, so the GDA (with arbitrary $m_G$) is ineffective when $m_S$ is enough (Theorem 3.2&3.3).\n* Small $m_S$. In this case, other terms (e.g. dimension) dominate the generalization bound, and awful overfitting happens. In the bGMM and GANs settings, we prove that GDA can bring a constant-level improvement to the generalization performance (Theorem 3.2&3.3). This is because more data are significant to relieving the overfitting.\n\nWe will discuss this more detailedly in the final version."}, {"review_id": "jxFCAadgsW", "reviewer": "Reviewer_Dxq5", "summary": "Generative data augmentation (GDA) aims to improve model performance by generating artificial labeled samples to enlarge the limited training dataset, but is also highly influenced by the size of training dataset, choices of augmentation methods and the number of augmented data. The paper seeks to develop a theoretical understanding to GDA by reproducing classical results built upon i.i.d. assumptions to the generatively augmented dataset, and establishes a general relationship between the stability bound and the learned distribution divergence besides the augmentation size. To further investigate and verify the proposed upper bound of generalization error, the paper also particularizes specific cases of bGMM and GAN, and provides insights to understand the theoretical results. Finally, empirical experiments on synthetic dataset and CIFAR10 are conducted to study the effect of different factors and validate discovered theoretical findings.", "questions": "1) In the paper the mixed distribution with augmentation is simply defined as a weighted combination of the training set distribution and the generative model distribution, is it a proper definition particularly when these two distributions are mutually dependent?\n2) Could the authors clarify the purpose of choosing DCGAN, StyleGAN and EDM for experiments since there are plenty of alternative choices such as classical variational autoencoder (VAE)? This part is unclear for me from the paper.\n3) The theoretical results and conclusions given by the paper are solid. But could the authors illuminate what can be inspired from these conclusions especially for utilizing generative data augmentation in practical applications?\n", "limitations": "see above", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1） Mathematical notations and theoretical assumptions are clearly exhibited and explained in the paper. Details required to understand the problem background and existing results are also provided.\n2） The theoretical results are novel and the related analysis seems to be solid and intuitive. The proposed theorems also build connection to previous results under i.i.d. assumption and empirical findings.\n3） The idea of extending classical generalization error theories to the generative data augmentation problem is novel and well-motivated.\n", "weaknesses": "1） Despite theoretical results and corresponding conclusions of this paper are easy to understand and conformable to our common intuition, too many separated compositions of remarks make the paper annoyingly disorganized, forcing the readers to jump around while reading. The paper has to be re-organized to make readers easier to access the content.\n\n2） Some figures (e.g. Figure 1a) are hard to recognize, and some are unnecessarily separated into parallel parts (e.g. Figure 1b and Figure 1c).\n\n3） My greatest concern about this work is that when talking about data augmentation, we are most interested in the difference of model performance trained with and without data augmentation. However, the paper only considers the case where the optimal augmentation number $m_G^*$ is adopted.\n\n4） According to Theorem 3.1, the generalization bound for GDA is composed of the distribution divergence and the generalization error with respect to the mixed distribution, where the former is determined by the model itself and the latter is controlled by the number of generative data. For a given model with fixed generative ability, what we can only do is to find a near optimal number of generative samples. However, the choice of this number is not inspiring in this paper in my opinion.\n\n5） Experiments on real-world dataset seem incomplete and not convincing enough. First, only a single dataset (CIFAR-10) is adopted which fails to evade possible influence by the nature of dataset. Second, the experimental results show limited information and connection to the proposed theories, since the generalization error is inestimable in this case. Moreover, it is unfair to take generative models with totally different architectures for comparison, but fair comparison can be made between the same generative model with different training degrees.\n\n6） The practical contribution of the paper may be limited since many conclusions are intuitive and show little help to practical application.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer Dxq5\nWe thank Reviewer Dxq5 for the valuable comments.\n## Weakness 1: Organization\nThanks for the advice. We will re-organize the separated remarks in a coherent and integrated manner. \n## Weakness 2: Figures\nWe will make the figures more recognizable by removing some unimportant lines. Besides, we will integrate Fig. 1b and Fig. 1c (similarly, Fig. 1e and Fig. 1f) into a double y-axis graph.\n## Weakness 3:  Difference between with and without GDA & Only considers the case with $m_G^*$\nThanks for the suggestion. We discuss two concerns respectively.\n### Difference between with and without GDA\nThis is one of the main questions we want to answer in this paper. It can be divided into two cases, one with large $m_S$ and the other with small $m_S$, detailed as follows.\n* Large $m_S$. In this case, $m_S$ dominates the generalization bound. In Corollary 3.1, we conclude that if $d_{TV}(D,D_G(S))=o (\\max(\\log(m)\\beta_m,1/\\sqrt{m}))$, then using the GDA enjoys a faster learning rate than not using the GDA. Besides, in both the bGMM and GANs setting (Theorem 3.2&3.3), we prove the precondition fails to hold, so the GDA is ineffective when $m_S$ is enough.\n* Small $m_S$. In this case, some terms (e.g. dimension) dominate the generalization bound, and awful overfitting happens. In the bGMM and GANs settings (Theorem 3.2&3.3), we prove that GDA can bring a constant-level improvement to the generalization performance.\n### Only considers the case with $m_G^*$\n**In fact, we do not only consider the case with $m_G^\\*$**. The choice of $m_G$ can be divided into 4 cases:\n* $m_G=0$. It means that the GDA is not used, which is the baseline we want to compare.\n* $m_G=\\Theta(m_S)$. It is the common case when people use the GDA.\n* $m_G=m_{G,order}^*$. It is the efficient augmentation size that achieves the fastest learning rate w.r.t. $m_S$.\n* $m_G=m_{G}^*$. It is the optimal augmentation size that minimizes the generalization bound in Theorem 3.1.\n \n**All the main theorems** in the paper include (Theorem 3.1) or highlight (Theorem 3.2&3.3) the first three settings. Besides, **all experiments** also mainly focus on the cases where $m_G=0$ or $m_G=\\Theta(m_S)$ ($m_G\\leq50m_S$ for the bGMM and $m_G\\leq20m_S$ for GANs).\n\nWe will discuss these more detailedly in the final version.\n## Weakness 4: Optimal augmentation size\nThanks for the suggestion. Our work serves as a theoretical foundation and gives insights to the optimal augmentation size. Please see details in our response to the common concern 1.\n## Weakness 5: Experimental design\nThanks for the advice. **We adopt the CIFAR-10 dataset to empirically verify our theory, where the generalization error can be estimated and no comparison exists between different generative models**. Our experimental results support the theoretical results, which is agreed by Reviewer SG4V and jB6r.\n* \"Only a single CIFAR-10 dataset is adopted\". CIFAR-10 is a widely used dataset and **we adopt it to empirically validate Theorem 3.3**. Combining the simulations in the bGMM setting, our theory is verified sufficiently.\n* \"The generalization error is inestimable in the CIFAR-10 dataset\". By definition, given a trained neural classifier, the generalization error of Theorem 3.3 can be estimated by the absolute gap between the mean cross-entropy loss on the training set (with generated data) and the mean cross-entropy loss on the test set. **We add the results of GANs with this estimator in the latest uploaded PDF (Table A)**. On the one hand, GANs decrease the generalization error when $m_S$ is small (without standard augmentation). On the other hand, GANs fail to boost the performance obviously and even hurts the error when $m_S$ is approximately large (with standard augmentation). **The results support Theorem 3.3 again**.\n* \"Unfair to take generative models with totally different architectures for comparison\". **The experiments are conducted to verify our Theorem 3.3, rather than comparing different generative models**. How these generative models verify our theory can be found in our response to Q2. **To reduce the confusion here, we will split Table 2 into three tables according to the generative models**.\nWe will clarify these more clearly in the final version.\n## Weakness 6:  Intuitive results show little help to practice\nThanks for the advice. Analyzing the intuitive phenomena contributes to the community. Please see details in our response to the common concern 2.\n## Q1: Definition of the mixed distribution\nYes, it is a proper definition no matter whether the $D_G(S)$ is dependent on the $D$. In fact, the convex combination of arbitrary distributions is still a distribution. Welcome to ask further questions if you still have confusion.\n## Q2: The purpose of choosing DCGAN, StyleGAN, and EDM\nThanks for the suggestion. **GANs are chosen to empirically validate Theorem 3.3 and the EDM is chosen to explore the ability of the diffusion model.** First, we choose a \"bad\" GAN (DCGAN) to empirically verify that GANs can improve the test performance when awful overfitting happens (without standard augmentation). Second, we choose a \"good\" GAN (StyleGANv2) to verify that GANs can not improve the test performance obviously when the $m_S$ is approximately large (with standard augmentation). Third, because diffusion models achieve good success in recent years, we conduct experiments on the EDM and suggest that diffusion models have a better $d_{TV}(D, D_G(S))$ than GANs. We will discuss these more detailedly in the final version.\n## Q3: Impact on the practice\nThis paper is a first step towards understanding the GDA, so it is difficult to guide the practice detailedly. However, our results can still give some insights to the practice. Please see details in our response to the common concern 3.\n\n**We think we have fully addressed the concerns of the reviewer. If the reviewer has any further questions, please feel free to contact us for a further discussion**."}, {"review_id": "ylY7xR4C6x", "reviewer": "Reviewer_jB6r", "summary": "This paper studies generative data augmentation (GDA), in which the samples from trained generative models are added to the training dataset for training discriminative models. There have been several empirical research reports on GDA, and it is known that GDA is unlikely to be effective when real learning data is abundant. However, there has been no theoretical analysis provided so far to explain this phenomenon. This study assumes a realistic setting in which the distribution imitated by the generative model and the real dataset distribution are different, and analyzes the generalization error bounds of GDA in the non-iid setting in three cases: (i) general case based on the existing algorithmic stability framework, (ii) a binary Gaussian mixture model (bGMM) and linear classifier, and (iii) a deep generative adversarial nets and deep neural classifier. The main findings from these theorems are (a) the divergence between the distribution imitated by the generated model and the true distribution is important for the generalization error, (b) increasing the number of generated samples does not lead to a faster learning rate, and (c) GDA does not achieve faster learning rate in situations affected by the curse of dimensionality. The paper provides simple experiments on bGMM and CIFAR-10 to test the theory, showing the similarity between the upper bound of the generalization error given by the theorem and the measured trends of the error, and the effectiveness of GDA in situations where the curse of dimensionality occurs. While this generalization error analysis is not perfect, as the paper states in the Limitation, this paper will have a significant impact on the research field of GDA, where no theoretical discussion existed.", "questions": "- **Q1** Can the theorems provided by the paper discuss GDA in the situation of transfer learning of generative models? We often apply transfer learning such as fine-tuning to compensate for the distribution approximation performance of the generative model in GDA. I understood that minimizing distribution's divergence by transfer learning is not matter because Theorem 3.1 makes no assumptions about training methods, is this correct?\n- **Q2** Why is GAN set as the generative model in Theorem 3.3? Is there any advantage in proving this theorem?\n- **Q3** This is mostly a comment, but I think that the experiments in Section 4.2 should be included in the main paper since the evaluation of GDA with diffusion models as well as GANs is a high-impact result.", "limitations": "This paper adequately discusses the limitation of the tightness of the theoretical guarantee.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "+ The paper is well organized and clearly states its arguments. Also, the paper is very readable, with careful notation and explanation of existing frameworks to explain the theory.\n+ The paper provides generalized error-bound analysis in three settings ranging from general to realistic settings, establishing a first step toward learning guarantees in GDA.\n+ The paper confirms the implications of the theorem through several experiments.", "weaknesses": "- **W1** Some parts of the explanation are difficult to interpret. In Theorem 3.2 and 3.3, the paper explains \"constant-level improvement\" by GDA, but it is not clear in which equation \"constant\" appears, making the argument difficult to understand. Further, in Eq. (2), most of the theorems depend on the explanation in the Appendix, and the paper is not self-contained in this respect.\n- **W2** The paper does not mention several important previous studies. For example, Shmelkov et al. [a] were the first to report that GDA with GANs degrades accuracy even in small training dataset settings. Subsequently, Tran et al. [b] and Yamaguchi et al. proposed methods to improve GDA by the principles of Bayesian neural networks and multi-task learning. Although these works use somewhat older generative models and there may be facts that partially contradict the claims of the paper, they are considered important milestones in explaining the motivation for your work. I recommend that the paper cites them appropriately.\n\n**Reference**\n- [a] Shmelkov, Konstantin, Cordelia Schmid, and Karteek Alahari. \"How good is my GAN?.\" Proceedings of the European conference on computer vision (ECCV). 2018.\n- [b] Tran, Toan, et al. \"A bayesian data augmentation approach for learning deep models.\" Advances in neural information processing systems 30 (2017).\n- [c] Yamaguchi, Shin'ya, Sekitoshi Kanai, and Takeharu Eda. \"Effective data augmentation with multi-domain learning gans.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer jB6r\n\nWe thank Reviewer jB6r for the acknowledgment to our contributions and insightful and constructive comments.\n\n## Weakness 1: Constant-level improvement\n\nThanks for the nice advice. In general, given a fixed $m_G$, it is challenging to obtain an explicit form of \"constant-level improvement\" due to the complexity of the generalization bound. However, **we can clarify the \"constant-level improvement\" more clearly by diving into the explicit bounds in Appendix** (e.g., Eq. (19)). We denote the generalization error bound by ${Error}(m_G)$, where $m_G$ is the augmentation size. We compare the cases where $m_G = 0$ (without GDA) and $m_G \\to +\\infty$, respectively. Then the following holds.\n\n* bGMM: when $d > m_S$, we have $Error(+\\infty) \\leq \\frac{1}{\\log(m_S)} Error(0)$.\n\n* GANs: when $\\sqrt{d} > m_S$, we have $Error(+\\infty) \\leq \\frac{1}{AL^2} Error(0)$, where $A = \\prod_{l} \\Vert W_l \\Vert$.\n\nThese results can be proved by plugging $m_G = 0$ and $m_G \\to +\\infty$ into the bounds in the proof of Theorem 3.2&3.3. **We will re-organize these theorems and add these results and discussion in the final version**. In addition, we visualized the explicit bound of bGMM setting in Figure 1 d&e&f, which empirically validates the \"constant-level improvement\".\n\n## Weakness 2: Need to cite some previous works\n\nThanks for the helpful suggestion. We will cite the mentioned papers in the final version.\n\n## Q1: Transfer learning of generative models\n\nThanks for the insightful comment. Yes, if we are interested in analyzing the case where some transfer learning techniques are used to improve the distribution approximation performance of the generative model (decreasing $d_{TV}(D, D_G(S))$), our results (Theorem 3.1) can be a theoretical foundation. By decreasing $d_{TV}(D, D_G(S))$, our results show that GDA can perform better when a suitable augmentation number is chosen. We will add more discussion to the conclusion in the final version.\n\n## Q2: Why does theorem 3.3 choose GAN\n\nThanks for the comment. In this paper, we use the existing results (Lemma B.12) of GANs [46] to bound the $d_{TV}(D, D_G(S))$ in Theorem 3.3. With the emergence of more advanced results of generative models, our results can be improved and extended further.\n\n## Q3: Some important results in Appendix\n\nThanks. We will move Table 2 to the main paper in the final version following your suggestion."}, {"review_id": "dfSqAymCa3", "reviewer": "Reviewer_hFUC", "summary": "The paper provides a theoretical analysis of the stability bound for generative data augmentation. The authors provide empirical evidence to validate the proposed theory on bGMM and GNAs.", "questions": "- How to use the stability bound to advance existing generative data augmentation methods in practice?", "limitations": "I find no negative societal impact in this work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Data augmentation plays an important role in deep learning. The paper provides a theoretical analysis of using generative models for data augmentation. Understanding generative data augmentation can potentially benefit machine learning tasks in low-data conditions.", "weaknesses": "- In Section 4.2, the authors use standard augmentation to approximate CIFAR-10 with larger $m_S$. The comparison of GDA on CIFAR-10 and augmented CIFAR-10 is unfair as the standard augmentations induce effective inductive bias in the dataset, e.g., flipping. A more proper way to approximate CIFAR-10 with different $m_S$ is to sample multiple subsets of CIFAR-10 data with different sizes.\n\n- Although the paper proposes a general stability bound on GDA, it is unclear how the stability bound can be utilized to advance existing baselines. The finding that GDA can improve test generalizations on small datasets, where awful overfitting occurs, is somewhat expected. It is still unclear how to set the hyperparameters, like the number of augmented samples given any new dataset.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer hFUC\n\nWe thank Reviewer hFUC for the valuable comments.\n\n## Weakness 1: Standard augmentation\n\nThanks for the helpful advice. **There is no comparison between the CIFAR-10 and the augmented CIFAR-10, and the standard augmentation is used to approximately verify our theory with large $m_S$**. Our experimental results support the theoretical results, which is agreed by Reviewer SG4V and jB6r.\n\n* \"Unfair comparison between CIFAR-10 and augmented CIFAR-10\". **We note there is no comparison between the CIFAR-10 and the augmented CIFAR-10**. They are two different cases where we want to verify Theorem 3.3, respectively.  First, when standard augmentation is not used, the $m_S$ is small. In this case, we validate that GANs can improve the test performance (see Remark on line 280). Second, when standard augmentation is approximately used, the $m_S$ is approximately large. In this case, we validate that GANs can not boost the test performance obviously and even damage it (see Remark on line 276).\n* \"Approximating CIFAR-10 with different $m_S$\". When $m_S \\leq 50,000$ (the size of the CIFAR-10 dataset), we agree that sampling the subset of the CIFAR-10 dataset is the correct method. However, in that case, we can only observe worse overfitting, **which fails to verify our theoretical results that GANs can not improve the test performance when $m_S$ is large**. Therefore, we must investigate the setting where $m_S > 50,000$. However, when $m_S > 50,000$, **simply oversampling will cause the repeat of many data points**, so we chose the common augmentation for CIFAR-10 [51] to approximate the large $m_S$.\n\nWe will discuss these in detail in the final version.\n\n## Weakness 2: Expected results on small dataset & Optimal augmentation size\n\nThanks for the suggestion. We discuss the \"expected results\" and the setting of hyperparameters respectively.\n\n### \"Expected results\"\n\n**Precisely analyzing the expected phenomena, in theory, contributes to the community**. These expected results empirically validate the proposed theoretical framework. Please see the details in our response to the common concern 2.\n\n### Setting of hyperparameters\n\nOur work serves as a theoretical foundation to be extended in the future, which is agreed by Reviewer SG4V and jB6r. It gives insight to the optimal augmentation size $m_G^*$. Please see details in our response to the common concern 1.\n\n\n## Q1: How to use the stability bound to advance existing generative data augmentation methods in practice\n\nThanks for the suggestion. This paper is mainly a theoretical work and a first step towards understanding the GDA, so it is hard to use it to guide the practice detailedly. However, our results can still give some insights to the practice. Please see details in our response to the common concern 3.\n\nWe will discuss the impact on the practice detailedly in the final version.\n\n**We think we have fully addressed the questions from the reviewer. If the reviewer has any further questions, please feel free to contact us for further discussion**."}, {"review_id": "MeSZ7n6daK", "reviewer": "Reviewer_sAdG", "summary": "The paper presents a theoretical study of the generalization properties of training when the training set is augmented with artificially generated data. The main result of the paper is a theorem which bounds the generalization error by two terms – one representing the divergence between the original training distribution and the augmented distribution, and one representing the generalization error of the mixed distribution. The authors presents two empirical contributions. Firstly they study a gaussian mixture model with synthetic data and find that their theoretical predictions match the measurements. Secondly they consider Resnets trained on cifar and find that generative models are useful when augmentations are not used, and that diffusion models but not GANs are useful with augmentations.\n\n\nEDIT: increased confidence from 2 to 3 after clarifications from the authors.", "questions": "1/ Can you comment on the assumption that  “ the distribution learned by the generative model is dependent on the sampled train set”. Is it realistic? What happens if it is removed?\n2. How does the experiments on cifar10 related to your theoretical results?\n3. How well does your theoretical results apply to deep neural networks?\n", "limitations": "n/a", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "\n* The topic is topical and potentially impactful.\n* The writing is very good.\n* The results of the theorem are natural and intuitive.\n", "weaknesses": "* It seems like a major assumption is that “because the distribution learned by the generative model is dependent on the sampled train set”. In practice, I don’t think this is necessarily true. If this assumption is removed, the theoretical results might be much easier to derive.\n* Gaussian mixture models are not really used in practice, so it’s not a very interesting experiment.\n* It doesn’t seem like the theoretical results will apply to deep neural networks.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer sAdG\n\nWe thank Reviewer sAdG for the positive score and valuable comments.\n\n## Weakness 1 & Q1:  Assumption \"distribution learned by the generative model is dependent on the sampled train set”\n\nThanks for the suggestion. **This is not an assumption but a main challenge we have to face to establish a theory that is conformed to reality**. This statement holds naturally because even when we change one data point of the input, a learning algorithm may output a very different result. The reviewer can refer to the algorithmic stability theory we summarized in the related work.\n\n## Weakness 2: bGMM experiment is not interesting\n\nThanks for the advice. **The bGMM experiments are conducted to clarify our theoretical results (Theorem 3.2) clearly and verify our framework (Theorem 3.1)**, rather than approximating the real-world problem. As a supplement, we design experiments on the CIFAR-10 dataset to show our implications on the practice.\n\n## Q2: How do the experiments on cifar10 related to the theoretical results\n\nThanks for the suggestion. The experiments conducted on the CIFAR-10 are used to verify Theorem 3.3.\n\n**The theoretical implications on the deep neural networks (Theorem 3.3) can be summarized as follows.**\n\n* When $m_S$ is large enough, it is hard to boost the performance by augmenting the train set based on GANs. GDA may even damage the generalization. (Remark on line 276)\n* When $m_S$ is small and awful overfitting happens, GANs can improve the test performance. (Remark on line 280)\n\n**To verify our results (Theorem 3.3)**, we designed the experiments on the CIFAR-10 dataset as follows.\n\n* When the $m_S$ is approximately large (with standard augmentation), we choose a \"good\" GAN (StyleGANv2) to verify that it is hard to use GANs to improve the test performance.\n* When $m_S$ is small and awful overfitting happens (without standard augmentation), we choose a \"bad\" GAN (DCGAN) to verify that GANs can improve the test performance.\n\nThe analysis of the experimental results can be found in the next section. We will clarify these more clearly in the final version.\n\n## Weakness 3 & Q3: How well do the theoretical results apply to deep neural networks\n\nThanks for the suggestion. Theorem 3.1 establishes a general framework to understand the GDA, and Theorem 3.3 particularizes it to deep neural networks (GANs). **The experimental results (please see Table 2) support our theory on the deep neural networks (Theorem 3.3)**, which is agreed by Reviewer SG4V and jB6r. The experimental results can be divided into two parts as follows.\n\n* GANs improve the test performance of classifiers when $m_S$ is small  (without standard augmentation) and awful overfitting occurs, though DCGAN can not generate high-quality images. This supports the Remark on line 280.\n* GANs can not boost the performance obviously and even damage it when $m_S$ is approximately large (with standard augmentation). GDA with DCGAN always hurts the generalization ability. Though we use StyleGAN2-ADA (a state-of-the-art GAN), we can not boost the performance of classifiers obviously, and even consistently obtain worse test accuracy when $m_G$ is 500k or 1M.  This supports the Remark on line 276.\n\nTherefore, our experiments support that the theoretical results apply well to deep neural networks. We will discuss these in detail in the final version."}]

Author rebuttal:
# Summary of the revision

We sincerely thank the reviewers for their valuable comments, which help to further improve the quality of our work. We have thoroughly addressed the detailed comments. and summarize the revision in the next version as follows:

## New results

* **We add the results of GANs with the estimated generalization error in the latest uploaded PDF (Table A)**.
* We add more theoretical results to clarify the constant-level improvement in Theorem 3.2&3.3.

## Writing

* We avoid the overloading of $d$ by using $\mathcal{D}$ to denote the divergence.
* We clarify the meaning of "augmentation consumption" on line 166.
* We replace the "learning rate" on line 258 with "step size" to avoid ambiguity.
* We make the figures more recognizable by removing some unimportant lines. Besides, we integrate Fig. 1b and Fig. 1c (similarly, Fig. 1e and Fig. 1f) into a double y-axis graph.
* We move Table 2 to the main paper.

## Discussion

* We will cite the papers mentioned by Reviewer jB6r.
* We add more discussion about the scope of the theoretical results.
* We add more discussion about the design of our experiments on the CIFAR-10 dataset and its relation with Theorem 3.3.
* We add more discussion about the impact of work on the practice.
* We discuss the tightness of our bounds more detailedly in the Limitations section.

# Common concerns from reviewers

We thank all reviewers for their valuable and constructive comments. We address the common concerns here and post a point-to-point response to each reviewer as well. We believe the quality of the paper has been improved following the reviewers' suggestions.

## Common concern 1:  Choice of  the optimal number of generated samples (from reviewer Dxq5 and hFUC)

Our work serves as a theoretical foundation to be extended in the future, which is agreed by Reviewer SG4V and jB6r. The optimal augmentation size $m_G^*$ can be decided when $d_{TV}(D, D_G(S))$, $\beta_m$ and $\mathscr{T}(m_S, m_G)$ are estimated in the concrete situation. With the emergence of more advanced theory for the generative models, $m_G^*$ will be estimated better in the future. The reviewers can refer to the response to Common concern 3 for a more detailed discussion of our impact on the practice.

## Common concern 2: Intuitive/expected results show little help to practical application (from reviewer Dxq5 and hFUC)

**Precisely analyzing the expected phenomena, in theory, contributes to the community**. These expected results are predicted well by our theoretical results, so they empirically validate the proposed framework. We also clarify things more clearly from a theoretical perspective. For example, we prove that the size of a "small dataset" is relative to the data dimension and that the improvement brought by the GDA is constant-level rather than order-level. The reviewers can refer to the response to Common concern 3 for a more detailed discussion of our impact on the practice.

## Common concern 3:  Impact on the practice (from reviewer Dxq5 and hFUC)

This paper is mainly a theoretical work and a first step towards understanding the GDA, so it is still difficult to use it to guide the practice detailedly. However, our results can still give some insights to the practice, detailed as follows.

* Theorem 3.1 implies that improving the distribution approximation performance of the generative models is important for the GDA, which decreases the generalization error by optimizing the $d_{TV}(D, D_G(S))$. This motivates people to design better generative models.
* Theorem 3.1 shows that stabilizing the training of the generative models can bring benefits to the GDA, which optimizing the term $\mathscr{T}(m_S, m_G)$ and thus reduce the generalization error. This motivates us to improve the stability of the training of generative models (e.g. GAN). Besides, some transfer learning techniques can be used to optimize the $d_{TV}(D, D_G(S))$, which is mentioned by Reviewer jB6r.
* Theorem 3.1 implies that if we can estimate $d_{TV}(D, D_G(S))$, $\beta_m$ and $\mathscr{T}(m_S, m_G)$ for the concrete case, then the optimal augmentation size can be decided. With the emergence of more advanced theory for the generative models, $m_G^*$ will be estimated better in the future.
* When $m_S$ dominates the generalization bound, Theorem 3.1 give us a sufficient condition on when GDA works. If $d_{TV}(D, D_G(S)) = o \left(\max (\log(m)\beta_m, 1/ \sqrt{m}) \right)$, then using the GDA enjoys a lower generalization error than not using the GDA. Specially, in both the bGMM and GANs setting (Theorem 3.2&3.3), we prove that $d_{TV}(D, D_G(S)) = \Omega \left(\max (\log(m)\beta_m, 1/ \sqrt{m}) \right)$, so the GDA (with arbitrary $m_G$) is ineffective when $m_S$ is enough or standard augmentation is used.
* When other terms (e.g. dimension) dominate the generalization bound, awful overfitting happens. In the bGMM and GANs settings (Theorem 3.2&3.3), we prove that GDA can bring an improvement to the generalization performance. Specially, we prove the improvement is constant-level rather than order-level.

With the emergence of more advanced theories, our results can be improved and give more guidance to the practice. We will discuss the impact on the practice more detailedly in the final version.

Meta-review: The paper presents a theoretical analysis of generative data augmentation (GDA), a technique that uses generative models to create synthetic data that is added to the training set to improve the generalization performance of machine learning models. The authors provide theoretical guarantees on the performance of GDA under different assumptions on the generative model and the data distribution. They also conducted experiments on the CIFAR-10 dataset to demonstrate the effectiveness of GDA.

The paper is well-written and the presentation is clear. The authors do a good job of explaining the technical details in a way that is accessible to a general audience. The experiments are well-designed and the results are convincing to the reviewers who all raised their grades after the rebutal.

Overall, the paper is a valuable contribution to the literature on generative data augmentation. It provides a theoretical understanding of the benefits of GDA and insights on how to choose the optimal augmentation size. 

Here are some specific points that I liked about the paper:

The authors provide a clear and concise overview of the GDA technique.
The theoretical analysis is rigorous and provides insights on the benefits of GDA.
The experiments are well-designed and the results are convincing.
The paper is well-written and the presentation is clear.
I would like to see the authors address the following points in the final version of the paper:

The authors could provide more discussion on the impact of GDA on the practice. For example, they could discuss how GDA can be used to improve the performance of machine learning models on different tasks.
The authors could also provide more discussion on the limitations of GDA. For example, they could discuss how the performance of GDA depends on the quality of the generative model.
Overall, I think this is a well-written and well-researched paper that makes a significant contribution to the literature on generative data augmentation. I recommend it for publication.
Decision: Accept (poster)