|
On two approaches to concentration for sampling without replacement
I. O. Tolstikhin Max Planck Institute for Intelligent Systems
Abstract:
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 Bobkov [Ann. Probab., 32 (2004), pp. 2884–2907] for functions defined on a slice of the discrete cube. The second approach proposed by Hoeffding [J. Amer. Statist. Assoc., 58 (1963), pp. 13–30] reduces the problem to studying a sample of independent random variables.
Keywords:
concentration inequalities, empirical processes, choice without replacement.
DOI:
https://doi.org/10.4213/tvp5069
Full text:
PDF file (322 kB)
References:
PDF file
HTML file
English version:
Theory of Probability and its Applications, 2017, 61:3, 462–481
Bibliographic databases:
Received: 26.01.2014
Citation:
I. O. Tolstikhin, “On two approaches to concentration for sampling without replacement”, Teor. Veroyatnost. i Primenen., 61:3 (2016), 464–488; Theory Probab. Appl., 61:3 (2017), 462–481
Citation in format AMSBIB
\Bibitem{Tol16}
\by I.~O.~Tolstikhin
\paper On two approaches to concentration for sampling without replacement
\jour Teor. Veroyatnost. i Primenen.
\yr 2016
\vol 61
\issue 3
\pages 464--488
\mathnet{http://mi.mathnet.ru/tvp5069}
\crossref{https://doi.org/10.4213/tvp5069}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3626458}
\zmath{https://zbmath.org/?q=an:1376.60047}
\elib{https://elibrary.ru/item.asp?id=27485081}
\transl
\jour Theory Probab. Appl.
\yr 2017
\vol 61
\issue 3
\pages 462--481
\crossref{https://doi.org/10.1137/S0040585X97T988277}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000412117600006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85030319068}
Linking options:
http://mi.mathnet.ru/eng/tvp5069https://doi.org/10.4213/tvp5069 http://mi.mathnet.ru/eng/tvp/v61/i3/p464
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Number of views: |
This page: | 353 | Full text: | 29 | References: | 50 | First page: | 16 |
|