×

Concentration inequalities for samples without replacement. (English. Russian original) Zbl 1376.60047

Theory Probab. Appl. 61, No. 3, 462-481 (2017); translation from Teor. Veroyatn. Primen. 61, No. 3, 464-488 (2016).
Summary: This paper considers the concentration of values of functions of random variables sampled without replacement from a fixed finite set close to their expectations – a problem which is relevant to a variety of applications, including the transductive formulation of statistical learning theory. Apart from the review of known results, the paper studies two general approaches leading in many cases to sufficiently exact concentration inequalities. The first is based on the sub-Gaussian inequality of S. G. Bobkov [Ann. Probab. 32, No. 4, 2884–2907 (2004; Zbl 1065.60006)] for functions defined on a slice of the discrete cube. The second approach proposed by W. Hoeffding [J. Am. Stat. Assoc. 58, 13–30 (1963; Zbl 0127.10602)] reduces the problem to studying a sample of independent random variables.

MSC:

60E15 Inequalities; stochastic orderings
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI

References:

[1] V. N. Vapnik and A. Ya. Chervonenkis, {\it On the uniform convergence of relative frequencies of events to their probabilities}, Theory Probab. Appl., 16 (1971), pp. 264-280. · Zbl 0247.60005
[2] V. N. Vapnik and A. Ya. Chervonenkis, {\it Theory of Pattern Recognition}, Nauka, Moscow, 1974 (in Russian). · Zbl 0284.68070
[3] K. V. Vorontsov, {\it Combinatorial theory of overhitting results applications and open problems}, in Mathematical Methods of Pattern Recognitions: 15th Russian Conf., MAKS Press, Moscow, 2011, pp. 40-43 (in Russian).
[4] I. O. Tolstikhin, {\it Localized excess risk bound in combinatorial theory of overfitting}, Intern. Conf. IPR-9, 2012, pp. 54-57 (in Russian).
[5] R. Bardenet and O. A. Maillard, {\it Concentration inequalities for samples without replacement}, Bernoulli, 21 (2015), pp. 1361-1385. · Zbl 1388.60055
[6] P. Bartlett O. Bousquet and S. Mendelson, {\it Local Rademacher complexities}, Ann. Statist., 33 (2005), pp. 1497-1537. · Zbl 1083.62034
[7] A. Blum and J. Langford, {\it PAC-MDL bounds}, in Learning Theory and Kernel Machines, Lecture Notes in Comput. Sci. 2777, B. Schölkopf and M. K. Warmuth, eds., Springer, Berlin, 2003, pp. 344-357. · Zbl 1274.68293
[8] S. Bobkov, {\it Concentration of normalized sums and a central limit theorem for noncorrelated random variables}, Ann. Probab., 32 (2004), pp. 2884-2907. · Zbl 1065.60006
[9] S. Boucheron G. Lugosi and O. Bousquet, {\it Theory of classification A survey of recent advances}, ESAIM Probab. Stat., 9 (2005), pp. 323-375. · Zbl 1136.62355
[10] S. Boucheron G. Lugosi and P. Massart, {\it Concentration Inequalities A Nonasymptotic Theory of Independence}, Oxford University Press, Oxford, 2013. · Zbl 1279.60005
[11] O. Bousquet, {\it Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms}, Ph.D. thesis, Ecole Polytechnique, Paris, 2002.
[12] O. Bousquet S. Boucheron and G. Lugosi, {\it Introduction to statistical learning theory}, in Advanced Lectures on Machine Learning, Lecture Notes in Comput. Sci. 3176, O. Bousquet, U. von Luxburg, and G. Rätsch, Springer-Verlag, Berlin, 2004, pp. 169-207. · Zbl 1120.68428
[13] C. Cortes M. Mohri D. Pechyony and A. Rastogi, {\it Stability Analysis and Learning Bounds for Transductive Regression Algorithms}, preprint, arXiv:0904.0814, 2009.
[14] P. Derbeko R. El-Yaniv and R. Meir, {\it Explicit learning curves for transduction and application to clustering and compression algorithms}, J. Artific. Intell. Res., 22 (2004), pp. 117-142. · Zbl 1148.68430
[15] R. El-Yaniv and D. Pechyony, {\it Transductive Rademacher complexity and its applications}, J. Artific. Intell. Res., 35 (2009), pp. 193-234. · Zbl 1192.68515
[16] D. Gross and V. Nesme, {\it Note on Sampling without Replacing from a Finite Collection of Matrices}, preprint, arXiv:1001.2738v2, 2010.
[17] W. Hoeffding, {\it Probability inequalities for sums of bounded random variables}, J. Amer. Statist. Assoc., 58 (1963), pp. 13-30. · Zbl 0127.10602
[18] V. Koltchinskii, {\it Local Rademacher complexities and oracle inequalities in risk minimization}, Ann. Statist., 34 (2006), pp. 2593-2656. · Zbl 1118.62065
[19] V. Koltchinskii, {\it Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems}, Springer, Berlin, 2011. · Zbl 1223.91002
[20] V. Koltchinskii and D. Panchenko, {\it Rademacher processes and bounding the risk of function learning}, in High Dimensional Probability, II, D.E.Gine and J.Wellner, eds., Birkhäuser, Boston, 1999, pp. 443-457. · Zbl 1106.68385
[21] M. Pascal, {\it Rates of convergence in the central limit theorem for empirical processes}, Ann. Inst. H. Poincaré Ser. B, Probab. Statist., 22 (1986), pp. 381-423. · Zbl 0615.60032
[22] C. McDiarmid, {\it On the method of bounded differences}, in Surveys in Combinatorics, London Math. Soc. Lecture Notes Ser. 141, Cambridge University Press, Cambridge, 1989, pp. 148-188. · Zbl 0712.05012
[23] R. J. Serfling, {\it Probability inequalities for the sum in samples without replacement}, Ann. Statist., 1 (1974), pp. 39-48. · Zbl 0288.62005
[24] M. Talagrand, {\it New concentration inequalities in product spaces}, Invent. Math., 126 (1996), pp. 505-563. · Zbl 0893.60001
[25] V. Vapnik, {\it Statistical Learning Theory}, Wiley, New York, 1998. · Zbl 0935.62007
[26] K. V. Vorontsov, {\it Exact combinatorial bounds on the probability of overfitting for empirical risk minimization}, Pattern Recogn. Image Anal., 20 (2010), pp. 269-285.
[27] K. V. Vorontsov and A. A. Ivahnenko, {\it Tight combinatorial generalization bounds for threshold conjunction rules}, in Pattern Recognition and Machine Intelligence (PReMI ’11), S. O. Kuznetsov, D. P. Mandal, M. K. Kundu, and S. K. Pal, eds., Springer-Verlag, Berlin, 2011, pp. 66-73.
[28] K. V. Vorontsov A. I. Frey and E. A. Sokolov, {\it Computable combinatorial overfitting bounds}, Mach. Learn. Data Anal., 1 (2013), pp. 734-743.
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.