{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T17:55:34Z","timestamp":1791395734086,"version":"4.3.3"},"reference-count":57,"publisher":"Institute of Mathematical Statistics","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2024,12,1]]},"abstract":"The \u201csample amplification\u201d problem formalizes the following question: Given n i.i.d. samples drawn from an unknown distribution P, when is it possible to produce a larger set of n+m samples which cannot be distinguished from n+m i.i.d. samples drawn from P? In this work, we provide a firm statistical foundation for this problem by deriving generally applicable amplification procedures, lower bound techniques and connections to existing statistical notions. Our techniques apply to a large class of distributions including the exponential family, and establish a rigorous connection between sample amplification and distribution learning.<\/jats:p>","DOI":"10.1214\/24-aos2444","type":"journal-article","created":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T01:23:07Z","timestamp":1734571387000},"page":"2767-2790","source":"Crossref","is-referenced-by-count":0,"title":["On the statistical complexity of sample amplification"],"prefix":"10.1214","volume":"52","author":[{"given":"Brian","family":"Axelrod","sequence":"first","affiliation":[{"name":"Department of Computer Science, Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shivam","family":"Garg","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanjun","family":"Han","sequence":"additional","affiliation":[{"name":"Courant Institute of Mathematical Sciences and Center for Data Science, New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vatsal","family":"Sharan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Southern California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gregory","family":"Valiant","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stanford University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"33","doi-asserted-by":"publisher","unstructured":"Le Cam, L.<\/small> (1986). Asymptotic Methods in Statistical Decision Theory<\/i>. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4612-4946-7"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Ma, Z.<\/small> and Wu, Y.<\/small> (2015). Computational barriers in minimax submatrix detection. Ann. Statist.<\/i> 43<\/b> 1089\u20131116.","DOI":"10.1214\/14-AOS1300"},{"key":"12","doi-asserted-by":"publisher","unstructured":"BHATTACHARYA, R. N.<\/small> and RAO, R. R.<\/small> (2010). Normal Approximation and Asymptotic Expansions<\/i>. Classics in Applied Mathematics<\/i> 64<\/b>. SIAM, Philadelphia, PA.","DOI":"10.1137\/1.9780898719895.ch1"},{"key":"52","unstructured":"Wald, A.<\/small> (1950). Statistical Decision Functions<\/i>. Wiley, New York."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.<\/small> (2004). Introductory Lectures on Convex Optimization<\/i>: A Basic Course<\/i>. Applied Optimization<\/i> 87<\/b>. Kluwer Academic, Boston, MA.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"50","doi-asserted-by":"publisher","unstructured":"van der Vaart, A. W.<\/small> (2000). Asymptotic Statistics<\/i>. Cambridge Series in Statistical and Probabilistic Mathematics<\/i> 3<\/b>. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/CBO9780511802256"},{"key":"15","unstructured":"BRENNAN, M.<\/small> and BRESLER, G.<\/small> (2020). Reducibility and statistical-computational gaps from secret leakage. In Conference on Learning Theory<\/i> 648\u2013847. PMLR."},{"key":"16","doi-asserted-by":"publisher","unstructured":"BROWN, L. D.<\/small>, CAI, T. T.<\/small>, LOW, M. G.<\/small> and ZHANG, C.-H.<\/small> (2002). Asymptotic equivalence theory for nonparametric regression with random design. Ann. Statist.<\/i> 30<\/b> 688\u2013707.","DOI":"10.1214\/aos\/1028674838"},{"key":"17","doi-asserted-by":"publisher","unstructured":"BROWN, L. D.<\/small>, CARTER, A. V.<\/small>, LOW, M. G.<\/small> and ZHANG, C.-H.<\/small> (2004). Equivalence theory for density estimation, Poisson processes and Gaussian white noise with drift. Ann. Statist.<\/i> 32<\/b> 2074\u20132097.","DOI":"10.1214\/009053604000000012"},{"key":"25","doi-asserted-by":"crossref","unstructured":"DIACONIS, P.<\/small> and YLVISAKER, D.<\/small> (1979). Conjugate priors for exponential families. Ann. Statist.<\/i> 7<\/b> 269\u2013281.","DOI":"10.1214\/aos\/1176344611"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Berthet, Q.<\/small> and Rigollet, P.<\/small> (2013). Optimal detection of sparse principal components in high dimension. Ann. Statist.<\/i> 41<\/b> 1780\u20131815.","DOI":"10.1214\/13-AOS1127"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Basu, D.<\/small> (1955). On statistics independent of a complete sufficient statistic. Sankhy\u0101<\/i> 15<\/b> 377\u2013380.","DOI":"10.1007\/978-1-4419-5825-9_14"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Basu, D.<\/small> (1959). The family of ancillary statistics. Sankhy\u0101<\/i> 21<\/b> 247\u2013256.","DOI":"10.1007\/978-1-4419-5825-9_18"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Lehmann, E. L.<\/small> and Scholz, F.-W.<\/small> (1992). Ancillarity. In Current Issues in Statistical Inference<\/i>: Essays in Honor of D. Basu<\/i>. Institute of Mathematical Statistics Lecture Notes\u2014Monograph Series<\/i> 17<\/b> 32\u201351. IMS, Hayward, CA.","DOI":"10.1214\/lnms\/1215458837"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Brown, L. D.<\/small> and Low, M. G.<\/small> (1996). Asymptotic equivalence of nonparametric regression and white noise. Ann. Statist.<\/i> 24<\/b> 2384\u20132398.","DOI":"10.1214\/aos\/1032181159"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Tsybakov, A. B.<\/small> (2009). Introduction to Nonparametric Estimation<\/i>. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/b13794"},{"key":"34","doi-asserted-by":"publisher","unstructured":"LE CAM, L.<\/small> and YANG, G. L.<\/small> (1990). Asymptotics in Statistics<\/i>: Some Basic Concepts<\/i>. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-1-4684-0377-0"},{"key":"14","unstructured":"BRENNAN, M.<\/small> and BRESLER, G.<\/small> (2019). Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness. In Conference on Learning Theory<\/i> 469\u2013470. PMLR."},{"key":"1","unstructured":"ANTONIOU, A.<\/small>, STORKEY, A.<\/small> and EDWARDS, H.<\/small> (2017). Data augmentation generative adversarial networks. Preprint. Available at arXiv:1711.04340<\/a>."},{"key":"2","doi-asserted-by":"crossref","unstructured":"AXELROD, B.<\/small>,GARG, S.<\/small>,HAN, Y.<\/small>,SHARAN, V.<\/small>,VALIANT, G.<\/small> (2024). Supplement to \u201cOn the statistical complexity of sample amplification.\u201d https:\/\/doi.org\/10.1214\/24-AOS2444SUPP<\/a>","DOI":"10.1214\/24-AOS2444SUPP"},{"key":"3","unstructured":"AXELROD, B.<\/small>, GARG, S.<\/small>, SHARAN, V.<\/small> and VALIANT, G.<\/small> (2020). Sample amplification: Increasing dataset size even when learning is impossible. In International Conference on Machine Learning<\/i> 442\u2013451. PMLR."},{"key":"4","unstructured":"BAI, Y.<\/small>, KADAVATH, S.<\/small>, KUNDU, S.<\/small>, ASKELL, A.<\/small>, KERNION, J.<\/small>, JONES, A.<\/small>, CHEN, A.<\/small>, GOLDIE, A.<\/small>, MIRHOSEINI, A.<\/small> et al. (2022). Constitutional AI: Harmlessness from AI feedback. Preprint. Available at arXiv:2212.08073<\/a>."},{"key":"5","doi-asserted-by":"publisher","unstructured":"BALLY, V.<\/small> and CARAMELLINO, L.<\/small> (2014). On the distances between probability density functions. Electron. J. Probab.<\/i> 19<\/b> no. 110, 33 pp.","DOI":"10.1214\/EJP.v19-3175"},{"key":"6","doi-asserted-by":"publisher","unstructured":"BALLY, V.<\/small> and CARAMELLINO, L.<\/small> (2016). Asymptotic development for the CLT in total variation distance. Bernoulli<\/i> 22<\/b> 2442\u20132485.","DOI":"10.3150\/15-BEJ734"},{"key":"7","doi-asserted-by":"crossref","unstructured":"BARRON, A. R.<\/small> (1986). Entropy and the central limit theorem. Ann. Probab.<\/i> 14<\/b> 336\u2013342.","DOI":"10.1214\/aop\/1176992632"},{"key":"9","doi-asserted-by":"publisher","unstructured":"BASU, D.<\/small> (1958). On statistics independent of sufficient statistics. Sankhy\u0101<\/i> 20<\/b> 223\u2013226.","DOI":"10.1007\/978-1-4419-5825-9_16"},{"key":"13","doi-asserted-by":"publisher","unstructured":"BOBKOV, S. G.<\/small>, CHISTYAKOV, G. P.<\/small> and G\u00d6TZE, F.<\/small> (2014). Berry\u2013Esseen bounds in the entropic central limit theorem. Probab. Theory Related Fields<\/i> 159<\/b> 435\u2013478.","DOI":"10.1007\/s00440-013-0510-3"},{"key":"19","doi-asserted-by":"crossref","unstructured":"CALIMERI, F.<\/small>, MARZULLO, A.<\/small>, STAMILE, C.<\/small> and TERRACINA, G.<\/small> (2017). Biomedical data augmentation using generative adversarial neural networks. In International Conference on Artificial Neural Networks<\/i> 626\u2013634. Springer, Berlin.","DOI":"10.1007\/978-3-319-68612-7_71"},{"key":"20","doi-asserted-by":"crossref","unstructured":"CHATZIAGAPI, A.<\/small>, PARASKEVOPOULOS, G.<\/small>, SGOUROPOULOS, D.<\/small>, PANTAZOPOULOS, G.<\/small>, NIKANDROU, M.<\/small>, GIANNAKOPOULOS, T.<\/small>, KATSAMANIS, A.<\/small>, POTAMIANOS, A.<\/small> and NARAYANAN, S.<\/small> (2019). Data augmentation using GANs for speech emotion recognition. In Interspeech<\/i> 171\u2013175.","DOI":"10.21437\/Interspeech.2019-2561"},{"key":"21","unstructured":"CHEN, D.<\/small>, QI, X.<\/small>, ZHENG, Y.<\/small>, LU, Y.<\/small> and LI, Z.<\/small> (2022). Deep data augmentation for weed recognition enhancement: A diffusion probabilistic model and transfer learning based approach. Preprint. Available at arXiv:2210.09509<\/a>."},{"key":"22","doi-asserted-by":"publisher","unstructured":"CHLAP, P.<\/small>, MIN, H.<\/small>, VANDENBERG, N.<\/small>, DOWLING, J.<\/small>, HOLLOWAY, L.<\/small> and HAWORTH, A.<\/small> (2021). A review of medical image data augmentation techniques for deep learning applications. J. Med. Imag. Radiat. Oncol.<\/i> 65<\/b> 545\u2013563.","DOI":"10.1111\/1754-9485.13261"},{"key":"23","doi-asserted-by":"crossref","unstructured":"CUBUK, E. D.<\/small>, ZOPH, B.<\/small>, MANE, D.<\/small>, VASUDEVAN, V.<\/small> and LE, Q. V.<\/small> (2019). Autoaugment: Learning augmentation strategies from data. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition<\/i> 113\u2013123.","DOI":"10.1109\/CVPR.2019.00020"},{"key":"24","doi-asserted-by":"crossref","unstructured":"CUBUK, E. D.<\/small>, ZOPH, B.<\/small>, SHLENS, J.<\/small> and LE, Q. V.<\/small> (2020). Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition Workshops<\/i> 702\u2013703.","DOI":"10.1109\/CVPRW50498.2020.00359"},{"key":"26","doi-asserted-by":"crossref","unstructured":"FRID-ADAR, M.<\/small>, DIAMANT, I.<\/small>, KLANG, E.<\/small>, AMITAI, M.<\/small>, GOLDBERGER, J.<\/small> and GREENSPAN, H.<\/small> (2018). GAN-based synthetic medical image augmentation for increased CNN performance in liver lesion classification. Neurocomputing<\/i> 321<\/b> 321\u2013331.","DOI":"10.1016\/j.neucom.2018.09.013"},{"key":"27","doi-asserted-by":"crossref","unstructured":"HAN, C.<\/small>, RUNDO, L.<\/small>, ARAKI, R.<\/small>, NAGANO, Y.<\/small>, FURUKAWA, Y.<\/small>, MAURI, G.<\/small>, NAKAYAMA, H.<\/small> and HAYASHI, H.<\/small> (2019). Combining noise-to-image and image-to-image GANs: Brain MR image augmentation for tumor detection. IEEE Access<\/i> 7<\/b> 156966\u2013156977.","DOI":"10.1109\/ACCESS.2019.2947606"},{"key":"28","doi-asserted-by":"publisher","unstructured":"HAN, Y.<\/small>, JIAO, J.<\/small> and WEISSMAN, T.<\/small> (2015). Minimax estimation of discrete distributions under \u2113<\/mi><\/mrow>1<\/mn><\/mrow><\/msub><\/math> loss. IEEE Trans. Inf. Theory<\/i> 61<\/b> 6343\u20136354.","DOI":"10.1109\/TIT.2015.2478816"},{"key":"29","unstructured":"HENDRYCKS, D.<\/small>, MU, N.<\/small>, CUBUK, E. D.<\/small>, ZOPH, B.<\/small>, GILMER, J.<\/small> and LAKSHMINARAYANAN, B.<\/small> (2020). AugMix: A simple data processing method to improve robustness and uncertainty. In International Conference on Learning Representations<\/i>."},{"key":"30","unstructured":"KRIZHEVSKY, A.<\/small>, SUTSKEVER, I.<\/small> and HINTON, G. E.<\/small> (2012). Imagenet classification with deep convolutional neural networks. Adv. Neural Inf. Process. Syst.<\/i> 25<\/b>."},{"key":"31","doi-asserted-by":"publisher","unstructured":"LE CAM, L.<\/small> (1964). Sufficiency and approximate sufficiency. Ann. Math. Stat.<\/i> 35<\/b> 1419\u20131455.","DOI":"10.1214\/aoms\/1177700372"},{"key":"32","unstructured":"LE CAM, L.<\/small> (1972). Limits of experiments. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume<\/i> 1: Theory of Statistics<\/i> The Regents of the University of California."},{"key":"36","doi-asserted-by":"crossref","unstructured":"LIESE, F.<\/small> and MIESCKE, K.-J.<\/small> (2008). Statistical Decision Theory<\/i>: Estimation, Testing, and Selection<\/i>. Springer Series in Statistics<\/i>. Springer, New York.","DOI":"10.1007\/978-0-387-73194-0_3"},{"key":"37","unstructured":"LU, Y.<\/small>, SHEN, M.<\/small>, WANG, H.<\/small>, WANG, X.<\/small>, VAN RECHEM, C.<\/small> and WEI, W.<\/small> (2023). Machine learning for synthetic data generation: A review. Preprint. Available at arXiv:2302.04062<\/a>."},{"key":"38","unstructured":"LUZI, L.<\/small>, SIAHKOOHI, A.<\/small>, MAYER, P. M.<\/small>, CASCO-RODRIGUEZ, J.<\/small> and BARANIUK, R.<\/small> (2022). Boomerang: Local sampling on image manifolds using diffusion models. Preprint. Available at arXiv:2210.12100<\/a>."},{"key":"40","unstructured":"MADANI, A.<\/small>, MORADI, M.<\/small>, KARARGYRIS, A.<\/small> and SYEDA-MAHMOOD, T.<\/small> (2018). Chest X-ray generation and data augmentation for cardiovascular abnormality classification. In Medical Imaging<\/i> 2018: Image Processing<\/i> 10574<\/b> 415\u2013420. SPIE."},{"key":"42","unstructured":"PROKHOROV, Y. V.<\/small> (1952). A local theorem for densities. Dokl. Akad. Nauk SSSR<\/i> 83<\/b> 797\u2013800."},{"key":"43","doi-asserted-by":"publisher","unstructured":"RAY, K.<\/small> and SCHMIDT-HIEBER, J.<\/small> (2019). Asymptotic nonequivalence of density estimation and Gaussian white noise for small densities. Ann. Inst. Henri Poincar\u00e9 Probab. Stat.<\/i> 55<\/b> 2195\u20132208.","DOI":"10.1214\/18-AIHP946"},{"key":"44","doi-asserted-by":"crossref","unstructured":"SANDFORT, V.<\/small>, YAN, K.<\/small>, PICKHARDT, P. J.<\/small> and SUMMERS, R. M.<\/small> (2019). Data augmentation using generative adversarial networks (CycleGAN) to improve generalizability in CT segmentation tasks. Nat. Sci. Rep.<\/i> 9<\/b> 1\u20139.","DOI":"10.1038\/s41598-019-52737-x"},{"key":"45","doi-asserted-by":"crossref","unstructured":"SHORTEN, C.<\/small> and KHOSHGOFTAAR, T. M.<\/small> (2019). A survey on image data augmentation for deep learning. J. Big Data<\/i> 6<\/b> 1\u201348.","DOI":"10.1186\/s40537-019-0197-0"},{"key":"46","unstructured":"SIMARD, P. Y.<\/small>, STEINKRAUS, D.<\/small>, PLATT, J. C.<\/small> et al. (2003). Best practices for convolutional neural networks applied to visual document analysis. In Proceedings of International Conference on Document Analysis and Recognition<\/i> 3<\/b>. Edinburgh."},{"key":"47","doi-asserted-by":"crossref","unstructured":"SIRAZHDINOV, S. K.<\/small> and MAMATOV, M.<\/small> (1962). On convergence in the mean for densities. Theory Probab. Appl.<\/i> 7<\/b> 424\u2013428.","DOI":"10.1137\/1107039"},{"key":"48","doi-asserted-by":"crossref","unstructured":"TOKOZUME, Y.<\/small>, USHIKU, Y.<\/small> and HARADA, T.<\/small> (2018). Between-class learning for image classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition<\/i> 5486\u20135494.","DOI":"10.1109\/CVPR.2018.00575"},{"key":"51","unstructured":"VERMA, V.<\/small>, LAMB, A.<\/small>, BECKHAM, C.<\/small>, NAJAFI, A.<\/small>, MITLIAGKAS, I.<\/small>, LOPEZ-PAZ, D.<\/small> and BENGIO, Y.<\/small> (2019). Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning<\/i> 6438\u20136447. PMLR."},{"key":"53","doi-asserted-by":"crossref","unstructured":"WILLIAMS, E. J.<\/small> (1982). Some classes of conditional inference procedures. J. Appl. Probab.<\/i> 19<\/b> 293\u2013303.","DOI":"10.2307\/3213568"},{"key":"54","doi-asserted-by":"crossref","unstructured":"YI, W.<\/small>, SUN, Y.<\/small> and HE, S.<\/small> (2018). Data augmentation using conditional GANs for facial emotion recognition. In 2018 Progress in Electromagnetics Research Symposium<\/i> (PIERS-Toyama<\/i>) 710\u2013714. IEEE.","DOI":"10.23919\/PIERS.2018.8598226"},{"key":"55","doi-asserted-by":"publisher","unstructured":"YI, X.<\/small>, WALIA, E.<\/small> and BABYN, P.<\/small> (2019). Generative adversarial network in medical imaging: A review. Med. Image Anal.<\/i> 58<\/b> 101552.","DOI":"10.1016\/j.media.2019.101552"},{"key":"56","doi-asserted-by":"crossref","unstructured":"YUN, S.<\/small>, HAN, D.<\/small>, OH, S. J.<\/small>, CHUN, S.<\/small>, CHOE, J.<\/small> and YOO, Y.<\/small> (2019). Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of the IEEE\/CVF International Conference on Computer Vision<\/i> 6023\u20136032.","DOI":"10.1109\/ICCV.2019.00612"},{"key":"57","unstructured":"ZHANG, H.<\/small>, CISSE, M.<\/small>, DAUPHIN, Y. N.<\/small> and LOPEZ-PAZ, D.<\/small> (2018). Mixup: Beyond empirical risk minimization. In International Conference on Learning Representations<\/i>."}],"container-title":["The Annals of Statistics"],"original-title":[],"deposited":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T17:18:51Z","timestamp":1791393531000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-52\/issue-6\/On-the-statistical-complexity-of-sample-amplification\/10.1214\/24-AOS2444.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,1]]},"references-count":57,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2024,12,1]]}},"URL":"https:\/\/doi.org\/10.1214\/24-aos2444","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,1]]}}}