×

Concentration inequalities for bounded functionals via log-Sobolev-type inequalities. (English) Zbl 1472.60036

Summary: In this paper, we prove multilevel concentration inequalities for bounded functionals \(f = f(X_1, \dots , X_n)\) of random variables \(X_1, \dots , X_n\) that are either independent or satisfy certain logarithmic Sobolev inequalities. The constants in the tail estimates depend on the operator norms of \(k\)-tensors of higher order differences of \(f\). We provide applications for both dependent and independent random variables. This includes deviation inequalities for empirical processes \(f(X) = \sup_{g \in{\mathcal{F}}} {|g(X)|}\) and suprema of homogeneous chaos in bounded random variables in the Banach space case \(f(X) = \sup_t{\Vert \sum_{i_1 \ne \dots \ne i_d} t_{i_1 \dots i_d} X_{i_1} \cdots X_{i_d}\Vert }_{{\mathcal{B}}} \). The latter application is comparable to earlier results of Boucheron, Bousquet, Lugosi, and Massart and provides the upper tail bounds of Talagrand. In the case of Rademacher random variables, we give an interpretation of the results in terms of quantities familiar in Boolean analysis. Further applications are concentration inequalities for \(U\)-statistics with bounded kernels \(h\) and for the number of triangles in an exponential random graph model.

MSC:

60E15 Inequalities; stochastic orderings
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamczak, R., Moment inequalities for \(U\)-statistics, Ann. Probab., 34, 6, 2288-2314 (2006) · Zbl 1123.60009 · doi:10.1214/009117906000000476
[2] Adamczak, R., A note on the Hanson-Wright inequality for random vectors with dependencies, Electron. Commun. Probab., 20, 72, 13 (2015) · Zbl 1328.60050 · doi:10.1214/ECP.v20-3829
[3] Adamczak, R., Kotowski, M., Polaczyk, B., Strzelecki, M.: A note on concentration for polynomials in the Ising model. arXiv preprint (2018) · Zbl 1466.60029
[4] Adamczak, R., Latała, R., Meller, R.: Hanson-Wright inequality in Banach spaces. arXiv preprint (2018) · Zbl 1478.60068
[5] Adamczak, R.; Wolff, P., Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, Probab. Theory Relat. Fields, 162, 3-4, 531-586 (2015) · Zbl 1323.60033 · doi:10.1007/s00440-014-0579-3
[6] Aida, S.; Stroock, DW, Moment estimates derived from Poincaré and logarithmic Sobolev inequalities, Math. Res. Lett., 1, 1, 75-86 (1994) · Zbl 0862.60064 · doi:10.4310/MRL.1994.v1.n1.a9
[7] Ambrosio, L.; Gigli, N.; Savaré, G., Gradient Flows in Metric Spaces and in the Space of Probability Measures (2008), Basel: Birkhäuser Verlag, Basel · Zbl 1145.35001
[8] Arcones, MA; Giné, E., On decoupling, series expansions, and tail behavior of chaos processes, J. Theor. Probab., 6, 1, 101-122 (1993) · Zbl 0785.60023 · doi:10.1007/BF01046771
[9] Bobkov, SG; Chistyakov, GP; Götze, F., Second-order concentration on the sphere, Commun. Contemp. Math., 19, 5, 1650058 (2017) · Zbl 1373.60043 · doi:10.1142/S0219199716500589
[10] Bobkov, SG; Götze, F.; Sambale, H., Higher order concentration of measure, Commun. Contemp. Math., 21, 3, 1850043 (2019) · Zbl 1447.60049 · doi:10.1142/S0219199718500438
[11] Bobkov, SG; Ledoux, M., Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential distribution, Probab. Theory Relat. Fields, 107, 3, 383-400 (1997) · Zbl 0878.60014 · doi:10.1007/s004400050090
[12] Bobkov, SG; Tetali, P., Modified logarithmic Sobolev inequalities in discrete settings, J. Theor. Probab., 19, 2, 289-336 (2006) · Zbl 1113.60072 · doi:10.1007/s10959-006-0016-3
[13] Bonami, A., Ensembles \(\Lambda (p)\) dans le dual de \(D^{\infty }\), Ann. Inst. Fourier (Grenoble), 18, fasc. 2, 193-204 (1968) · Zbl 0175.44801 · doi:10.5802/aif.297
[14] Bonami, A., Étude des coefficients de Fourier des fonctions de \(L^p(G)\), Ann. Inst. Fourier (Grenoble), 20, facs. 2, 335-402 (1970) · Zbl 0195.42501 · doi:10.5802/aif.357
[15] Borell, C.: On the Taylor series of a Wiener polynomial. In: Seminar Notes on Multiple Stochastic Integration, Polynomial Chaos and their Integration. Case Western Reserve University, Cleveland (1984) · Zbl 0573.60067
[16] Boucheron, S.; Bousquet, O.; Lugosi, G.; Massart, P., Moment inequalities for functions of independent random variables, Ann. Probab., 33, 2, 514-560 (2005) · Zbl 1074.60018 · doi:10.1214/009117904000000856
[17] Boucheron, S.; Lugosi, G.; Massart, P., Concentration inequalities using the entropy method, Ann. Probab., 31, 3, 1583-1614 (2003) · Zbl 1051.60020 · doi:10.1214/aop/1055425791
[18] Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities (2013), Oxford: Oxford University Press, Oxford · Zbl 1337.60003 · doi:10.1093/acprof:oso/9780199535255.001.0001
[19] Bousquet, O., A Bennett concentration inequality and its application to suprema of empirical processes, C. R. Math. Acad. Sci. Paris, 334, 6, 495-500 (2002) · Zbl 1001.60021 · doi:10.1016/S1631-073X(02)02292-6
[20] Burk, FE, A Garden of Integrals, The Dolciani Mathematical Expositions (2007), Washington, DC: Mathematical Association of America, Washington, DC · Zbl 1127.26300 · doi:10.7135/UPO9781614442097
[21] Caputo, P.; Menz, G.; Tetali, P., Approximate tensorization of entropy at high temperature, Ann. Fac. Sci. Toulouse Math. (2015) · Zbl 1331.60038 · doi:10.5802/afst.1460
[22] Chafaï, D., Entropies, convexity, and functional inequalities: on \(\Phi \)-entropies and \(\Phi \)-Sobolev inequalities, J. Math. Kyoto Univ., 44, 2, 325-363 (2004) · Zbl 1079.26009 · doi:10.1215/kjm/1250283556
[23] Chatterjee, S.; Diaconis, P., Estimating and understanding exponential random graph models, Ann. Stat., 41, 5, 2428-2461 (2013) · Zbl 1293.62046 · doi:10.1214/13-AOS1155
[24] de la Peña, VH; Giné, E., Decoupling. Probability and its Applications (1999), New York: Springer, New York
[25] Dellacherie, C.; Meyer, PA, Probabilities and Potential (1978), Amsterdam: North-Holland Publishing Co., Amsterdam · Zbl 0494.60001
[26] Diaconis, P.; Saloff-Coste, L., Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6, 3, 695-750 (1996) · Zbl 0867.60043 · doi:10.1214/aoap/1034968224
[27] Efron, B.; Stein, CM, The jackknife estimate of variance, Ann. Stat., 9, 3, 586-596 (1981) · Zbl 0481.62035 · doi:10.1214/aos/1176345462
[28] Götze, F.; Sambale, H.; Sinulis, A., Higher order concentration for functions of weakly dependent random variables, Electron. J. Probab., 24, 85, 19 (2019) · Zbl 1451.60027
[29] Gross, L., Logarithmic Sobolev inequalities, Am. J. Math., 97, 4, 1061-1083 (1975) · Zbl 0318.46049 · doi:10.2307/2373688
[30] Hanson, DL; Wright, FT, A bound on tail probabilities for quadratic forms in independent random variables, Ann. Math. Stat., 42, 1079-1083 (1971) · Zbl 0216.22203 · doi:10.1214/aoms/1177693335
[31] Hewitt, E.; Stromberg, K., Real and Abstract Analysis (1975), New York: Springer, New York · Zbl 0307.28001
[32] Hsu, D.; Kakade, SM; Zhang, T., A tail inequality for quadratic forms of subgaussian random vectors, Electron. Commun. Probab., 17, 52, 6 (2012) · Zbl 1309.60017 · doi:10.1214/ECP.v17-2079
[33] Kim, JH; Vu, VH, Concentration of multivariate polynomials and its applications, Combinatorica, 20, 3, 417-434 (2000) · Zbl 0969.60013 · doi:10.1007/s004930070014
[34] Klein, T.; Rio, E., Concentration around the mean for maxima of empirical processes, Ann. Probab., 33, 3, 1060-1077 (2005) · Zbl 1066.60023 · doi:10.1214/009117905000000044
[35] Latała, R., Estimates of moments and tails of Gaussian chaoses, Ann. Probab., 34, 6, 2315-2331 (2006) · Zbl 1119.60015 · doi:10.1214/009117906000000421
[36] Latała, R., Oleszkiewicz, K.: Between Sobolev and Poincaré. In: Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1745, pp. 147-168. Springer, Berlin (2000). doi:10.1007/BFb0107213 · Zbl 0986.60017
[37] Ledoux, M., On Talagrand’s deviation inequalities for product measures, ESAIM Probab. Stat., 1, 63-87 (1997) · Zbl 0869.60013 · doi:10.1051/ps:1997103
[38] Ledoux, M., The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs (2001), Providence: American Mathematical Society, Providence · Zbl 0995.60002
[39] Marchina, A., Concentration inequalities for separately convex functions, Bernoulli, 24, 4, 2906-2933 (2018) · Zbl 1428.60037 · doi:10.3150/17-BEJ949
[40] Marton, K.: Logarithmic Sobolev Inequalities in Discrete Product Spaces: A Proof by a Transportation Cost Distance. arXiv preprint (2015)
[41] Massart, P., About the constants in Talagrand’s concentration inequalities for empirical processes, Ann. Probab., 28, 2, 863-884 (2000) · Zbl 1140.60310 · doi:10.1214/aop/1019160263
[42] Milman, VD; Schechtman, G., Asymptotic Theory of Finite-Dimensional Normed Spaces (1986), Berlin: Springer, Berlin · Zbl 0606.46013
[43] Nelson, E., The free Markoff field, J. Funct. Anal., 12, 211-227 (1973) · Zbl 0273.60079 · doi:10.1016/0022-1236(73)90025-6
[44] O’Donnell, R., Analysis of Boolean Functions (2014), New York: Cambridge University Press, New York · Zbl 1336.94096 · doi:10.1017/CBO9781139814782
[45] Raginsky, M.; Sason, I., Concentration of Measure Inequalities in Information Theory, Communications, and Coding (2014), Delft: Now Publishers Inc., Delft · Zbl 1278.94031
[46] Rio, E., Une inégalité de Bennett pour les maxima de processus empiriques, Ann. Inst. Henri Poincaré Probab. Stat., 38, 6, 1053-1057 (2002) · Zbl 1014.60011 · doi:10.1016/S0246-0203(02)01122-6
[47] Rudelson, M.; Vershynin, R., Hanson-Wright inequality and sub-Gaussian concentration, Electron. Commun. Probab., 18, 82, 9 (2013) · Zbl 1329.60056 · doi:10.1214/ECP.v18-2865
[48] Sambale, H.; Sinulis, A., Logarithmic Sobolev inequalities for finite spin systems and applications, Bernoulli, 26, 3, 1863-1890 (2020) · Zbl 1462.60034 · doi:10.3150/19-BEJ1172
[49] Samson, P-M, Infimum-convolution description of concentration properties of product probability measures, with applications, Ann. Inst. Henri Poincaré Probab. Stat., 43, 3, 321-338 (2007) · Zbl 1125.60018 · doi:10.1016/j.anihpb.2006.05.003
[50] Steele, JM, An Efron-Stein inequality for nonsymmetric statistics, Ann. Stat., 14, 2, 753-758 (1986) · Zbl 0604.62017 · doi:10.1214/aos/1176349952
[51] Talagrand, M.: A new isoperimetric inequality and the concentration of measure phenomenon. In: Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 1469, pp. 94-124. Springer, Berlin (1991). doi:10.1007/BFb0089217 · Zbl 0818.46047
[52] Talagrand, M., New concentration inequalities in product spaces, Invent. Math., 126, 3, 505-563 (1996) · Zbl 0893.60001 · doi:10.1007/s002220050108
[53] Talagrand, M.: Upper and lower bounds for stochastic processes. In: Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics, vol. 60. Springer, Heidelberg (2014) · Zbl 1293.60001
[54] van Handel, R.: Probability in high dimension. APC 550 Lecture Notes, Princeton University (2016). https://web.math.princeton.edu/ rvan/APC550.pdf
[55] Vu, VH; Wang, K., Random weighted projections, random quadratic forms and random eigenvectors, Random Struct. Algorithms, 47, 4, 792-821 (2015) · Zbl 1384.60029 · doi:10.1002/rsa.20561
[56] Wolff, P.: On some Gaussian concentration inequality for non-Lipschitz functions. In: High dimensional probability VI, Progress in Probability, vol. 66, pp. 103-110. Birkhäuser/Springer, Basel (2013) · Zbl 1271.60035
[57] Wright, F.T.: A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric. Ann. Probability 1(6), 1068-1070 (1973). https://projecteuclid.org/euclid.aop/1176996815 · Zbl 0271.60033
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.