Empirical approximation of the Gaussian distribution in \(\mathbb{R}^d\).(English)Zbl 07966472
Summary: Let \(G_1, \dots, G_m\) be independent copies of the standard gaussian random vector in \(\mathbb{R}^d\). We show that there is an absolute constant \(c\) such that for any \(A \subset S^{d - 1}\), with probability at least \(1 - 2 \exp(- c \Delta m)\), for every \(t \in \mathbb{R}\),\[\sup_{x \in A} \left | \frac{1}{m} \sum_{i = 1}^m 1_{\{\langle G_i, x \rangle \leq t\}} - \mathbb{P} (\langle G, x \rangle \leq t) \right | \leq \Delta + \sigma(t) \sqrt{\Delta}.\]Here \(\sigma(t)\) is the variance of \(1_{\{\langle G, x \rangle \leq t\}}\) and \(\Delta \geq \Delta_0\), where \(\Delta_0\) is determined by an unexpected complexity parameter of \(A\) that captures the set’s geometry (Talagrand’s \(\gamma_1\) functional). The bound, the probability estimate, and the value of \(\Delta_0\) are all (almost) optimal.
We use this fact to show that if \(\Gamma = \sum_{i = 1}^m \langle G_i, x \rangle e_i\) is the random matrix that has \(G_1, \dots, G_m\) as its rows, then the structure of \(\Gamma(A) = \{\Gamma x : x \in A\}\) is far more rigid and well-prescribed than was previously expected.
We use this fact to show that if \(\Gamma = \sum_{i = 1}^m \langle G_i, x \rangle e_i\) is the random matrix that has \(G_1, \dots, G_m\) as its rows, then the structure of \(\Gamma(A) = \{\Gamma x : x \in A\}\) is far more rigid and well-prescribed than was previously expected.
Keywords:
Gaussian distribution;empirical distribution;Dvoretzky-Kiefer-Wolfowitz inequality;Wasserstein distance;random matrices;generic chainingCite
References:
| [1] | Adamczak, R.; Litvak, A.; Pajor, A.; Tomczak-Jaegermann, N., Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, J. Am. Math. Soc., 23, 2, 535-561, 2010 ·Zbl 1206.60006 |
| [2] | Alexander, K. S., The central limit theorem for weighted empirical processes indexed by sets, J. Multivar. Anal., 22, 2, 313-339, 1987 ·Zbl 0624.60051 |
| [3] | Alexander, K. S., Rates of growth and sample moduli for weighted empirical processes indexed by sets, Probab. Theory Relat. Fields, 75, 3, 379-423, 1987 ·Zbl 0596.60029 |
| [4] | Artstein-Avidan, S.; Giannopoulos, A.; Milman, V. D., Asymptotic Geometric Analysis, Part I, vol. 202, 2015, American Mathematical Society ·Zbl 1337.52001 |
| [5] | Bartl, D.; Mendelson, S., A uniform Dvoretzky-Kiefer-Wolfowitz inequality, 2023, arXiv preprint |
| [6] | Bartl, D.; Mendelson, S., Random embeddings with an almost Gaussian distortion, Adv. Math., 400, Article 108261 pp., 2022 ·Zbl 1501.46010 |
| [7] | Bartl, D.; Mendelson, S., Structure preservation via the Wasserstein distance, 2022, arXiv preprint |
| [8] | Bartl, D.; Mendelson, S., On a variance dependent Dvoretzky-Kiefer-Wolfowitz inequality, 2023, arXiv preprint |
| [9] | Bobkov, S.; Ledoux, M., One-Dimensional Empirical Measures, Order Statistics, and Kantorovich Transport Distances, vol. 261, 2019, American Mathematical Society ·Zbl 1454.60007 |
| [10] | Bobkov, S. G.; Houdré, C., Isoperimetric constants for product probability measures, Ann. Probab., 25, 1, 184-205, 1997 ·Zbl 0878.60013 |
| [11] | Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities: A Nonasymptotic Theory of Independence, 2013, Oxford University Press ·Zbl 1279.60005 |
| [12] | Csiszár, I.; Körner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, 2011, Cambridge University Press ·Zbl 1256.94002 |
| [13] | Dvoretzky, A.; Kiefer, J.; Wolfowitz, J., Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator, Ann. Math. Stat., 642-669, 1956 ·Zbl 0073.14603 |
| [14] | Figalli, A.; Glaudo, F., An Invitation to Optimal Transport, Wasserstein Distances, and Gradient Flows, EMS Textbooks in Mathematics, 2021 ·Zbl 1472.49001 |
| [15] | Feller, W., An Introduction to Probability Theory and Its Applications, vol. 81, 1991, John Wiley & Sons |
| [16] | Giné, E.; Koltchinskii, V., Concentration inequalities and asymptotic results for ratio type empirical processes, Ann. Probab., 34, 1143-1216, 2006 ·Zbl 1152.60021 |
| [17] | Giné, E.; Koltchinskii, V.; Wellner, J. A., Ratio limit theorems for empirical processes, (Stochastic Inequalities and Applications, 2003, Springer), 249-278 ·Zbl 1055.60019 |
| [18] | Giné, E.; Zinn, J., Some limit theorems for empirical processes, Ann. Probab., 929-989, 1984 ·Zbl 0553.60037 |
| [19] | Hitczenko, P., Domination inequality for martingale transforms of a Rademacher sequence, Isr. J. Math., 84, 1, 161-178, 1993 ·Zbl 0781.60037 |
| [20] | Kannan, R.; Lovász, L.; Simonovits, M., Isoperimetric problems for convex bodies and a localization lemma, Discrete Comput. Geom., 13, 3, 541-559, 1995 ·Zbl 0824.52012 |
| [21] | Koltchinskii, V., Bounds on margin distributions in learning problems, Ann. Inst. Henri Poincaré Probab. Stat., 39, 6, 943-978, 2003 ·Zbl 1031.60017 |
| [22] | Koltchinskii, V.; Panchenko, D., Empirical margin distributions and bounding the generalization error of combined classifiers, Ann. Stat., 30, 1, 1-50, 2002 ·Zbl 1012.62004 |
| [23] | Latała, R., Sudakov-type minoration for log-concave vectors, Stud. Math., 3, 251-274, 2014 ·Zbl 1321.60031 |
| [24] | Ledoux, M.; Talagrand, M., Probability in Banach Spaces: Isoperimetry and Processes, vol. 23, 1991, Springer Science & Business Media ·Zbl 0748.60004 |
| [25] | Lugosi, G.; Mendelson, S., Multivariate mean estimation with direction-dependent accuracy, J. Eur. Math. Soc., 26, 6, 2211-2247, 2024 ·Zbl 07855544 |
| [26] | Massart, P., The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality, Ann. Probab., 1269-1283, 1990 ·Zbl 0713.62021 |
| [27] | Mendelson, S., Empirical processes with a bounded \(\psi_1\) diameter, Geom. Funct. Anal., 20, 4, 988-1027, 2010 ·Zbl 1204.60042 |
| [28] | Mendelson, S., Approximating Lp unit balls via random sampling, Adv. Math., 386, Article 107829 pp., 2021 ·Zbl 1469.46012 |
| [29] | Mendelson, S.; Milman, E.; Paouris, G., Generalized Sudakov via dimension reduction - a program, Stud. Math., 244, 159-202, 2019 ·Zbl 1431.52009 |
| [30] | Mendelson, S.; Paouris, G., On generic chaining and the smallest singular value of random matrices with heavy tails, J. Funct. Anal., 262, 9, 3775-3811, 2012 ·Zbl 1242.60008 |
| [31] | Mendelson, S.; Paouris, G., On the singular values of random matrices, J. Eur. Math. Soc., 16, 4, 823-834, 2014 ·Zbl 1290.60006 |
| [32] | Rüschendorf, L., The Wasserstein distance and approximation theorems, Probab. Theory Relat. Fields, 70, 1, 117-129, 1985 ·Zbl 0554.60024 |
| [33] | Talagrand, M., Upper and Lower Bounds for Stochastic Processes: Decomposition Theorems, vol. 60, 2022, Springer Nature |
| [34] | Tikhomirov, K., Sample covariance matrices of heavy-tailed distributions, Int. Math. Res. Not., 2018, 20, 6254-6289, 2018 ·Zbl 1462.62330 |
| [35] | Villani, C., Topics in Optimal Transportation, vol. 58, 2021, American Mathematical Soc. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
