Skip to main content
Top

2015 | OriginalPaper | Chapter

13. Advanced properties of uniform order statistics

Authors : Gérard Biau, Luc Devroye

Published in: Lectures on the Nearest Neighbor Method

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Various properties of \(U_{(1)},\mathop{\ldots },U_{(n)}\), uniform [0, 1] order statistics, will be needed in the analysis that follows. These are collected in the present chapter. The first group of properties is directly related to U (i) (1 ≤ i ≤ n), while the second group deals with random linear combinations of them.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
go back to reference A. Antos, L. Devroye, L. Györfi, Lower bounds for Bayes error estimation. IEEE Trans. Pattern Anal. Mach. Intell. 21, 643–645 (1999)CrossRef A. Antos, L. Devroye, L. Györfi, Lower bounds for Bayes error estimation. IEEE Trans. Pattern Anal. Mach. Intell. 21, 643–645 (1999)CrossRef
go back to reference T. Bailey, A. Jain, A note on distance-weighted k-nearest neighbor rules. IEEE Trans. Syst. Man Cybern. 8, 311–313 (1978)MATHCrossRef T. Bailey, A. Jain, A note on distance-weighted k-nearest neighbor rules. IEEE Trans. Syst. Man Cybern. 8, 311–313 (1978)MATHCrossRef
go back to reference J. Beck, The exponential rate of convergence of error for k n -NN nonparametric regression and decision. Probl. Control Inf. Theory 8, 303–311 (1979)MathSciNetMATH J. Beck, The exponential rate of convergence of error for k n -NN nonparametric regression and decision. Probl. Control Inf. Theory 8, 303–311 (1979)MathSciNetMATH
go back to reference J. Beirlant, E.J. Dudewicz, L. Györfi, E.C. van der Meulen, Nonparametric entropy estimation: an overview. Int. J. Math. Stat. Sci. 6, 17–39 (1997)MathSciNetMATH J. Beirlant, E.J. Dudewicz, L. Györfi, E.C. van der Meulen, Nonparametric entropy estimation: an overview. Int. J. Math. Stat. Sci. 6, 17–39 (1997)MathSciNetMATH
go back to reference G. Bennett, Probability inequalities for the sum of independent random variables. J. Am. Stat. Assoc. 57, 33–45 (1962)MATHCrossRef G. Bennett, Probability inequalities for the sum of independent random variables. J. Am. Stat. Assoc. 57, 33–45 (1962)MATHCrossRef
go back to reference A. Berlinet, S. Levallois, Higher order analysis at Lebesgue points, in Asymptotics in Statistics and Probability, ed. by M.L. Puri. Papers in Honor of George Gregory Roussas (VSP, Utrecht, 2000), pp. 17–32. A. Berlinet, S. Levallois, Higher order analysis at Lebesgue points, in Asymptotics in Statistics and Probability, ed. by M.L. Puri. Papers in Honor of George Gregory Roussas (VSP, Utrecht, 2000), pp. 17–32.
go back to reference S.N. Bernstein, The Theory of Probabilities (Gastehizdat Publishing House, Moscow, 1946) S.N. Bernstein, The Theory of Probabilities (Gastehizdat Publishing House, Moscow, 1946)
go back to reference A.C. Berry, The accuracy of the Gaussian approximation to the sum of independent variates. Trans. Am. Math. Soc. 49, 122–136 (1941)MathSciNetMATHCrossRef A.C. Berry, The accuracy of the Gaussian approximation to the sum of independent variates. Trans. Am. Math. Soc. 49, 122–136 (1941)MathSciNetMATHCrossRef
go back to reference G. Biau, F. Cérou, A. Guyader, On the rate of convergence of the bagged nearest neighbor estimate. J. Mach. Learn. Res. 11, 687–712 (2010)MathSciNetMATH G. Biau, F. Cérou, A. Guyader, On the rate of convergence of the bagged nearest neighbor estimate. J. Mach. Learn. Res. 11, 687–712 (2010)MathSciNetMATH
go back to reference G. Biau, F. Chazal, L. Devroye, D. Cohen-Steiner, C. Rodríguez, A weighted k-nearest neighbor density estimate for geometric inference. Electron. J. Stat. 5, 204–237 (2011)MathSciNetMATHCrossRef G. Biau, F. Chazal, L. Devroye, D. Cohen-Steiner, C. Rodríguez, A weighted k-nearest neighbor density estimate for geometric inference. Electron. J. Stat. 5, 204–237 (2011)MathSciNetMATHCrossRef
go back to reference G. Biau, L. Devroye, V. Dujmović, A. Krzyżak, An affine invariant k-nearest neighbor regression estimate. J. Multivar. Anal. 112, 24–34 (2012)MathSciNetMATHCrossRef G. Biau, L. Devroye, V. Dujmović, A. Krzyżak, An affine invariant k-nearest neighbor regression estimate. J. Multivar. Anal. 112, 24–34 (2012)MathSciNetMATHCrossRef
go back to reference G. Biau, F. Cérou, A. Guyader, New insights into Approximate Bayesian Computation. Ann. Inst. Henri Poincaré (B) Probab. Stat. 51, 376–403 (2015)MathSciNetMATHCrossRef G. Biau, F. Cérou, A. Guyader, New insights into Approximate Bayesian Computation. Ann. Inst. Henri Poincaré (B) Probab. Stat. 51, 376–403 (2015)MathSciNetMATHCrossRef
go back to reference P.J. Bickel, L. Breiman, Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test. Ann. Probab. 11, 185–214 (1983)MathSciNetMATHCrossRef P.J. Bickel, L. Breiman, Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of fit test. Ann. Probab. 11, 185–214 (1983)MathSciNetMATHCrossRef
go back to reference P.J. Bickel, Y. Ritov, Estimating integrated squared density derivatives: sharp best order of convergence estimates. Sankhy\(\bar{\mathrm{a}}\) A 50, 381–393 (1988) P.J. Bickel, Y. Ritov, Estimating integrated squared density derivatives: sharp best order of convergence estimates. Sankhy\(\bar{\mathrm{a}}\) A 50, 381–393 (1988)
go back to reference P. Billingsley, Probability and Measure, 3rd edn. (Wiley, New York, 1995)MATH P. Billingsley, Probability and Measure, 3rd edn. (Wiley, New York, 1995)MATH
go back to reference N.H. Bingham, C.M. Goldie, J.L. Teugels, Regular Variation (Cambridge University Press, Cambridge, 1987)MATHCrossRef N.H. Bingham, C.M. Goldie, J.L. Teugels, Regular Variation (Cambridge University Press, Cambridge, 1987)MATHCrossRef
go back to reference K. Böröczky, Jr., Finite Packing and Covering (Cambridge University Press, Cambridge, 2004)MATHCrossRef K. Böröczky, Jr., Finite Packing and Covering (Cambridge University Press, Cambridge, 2004)MATHCrossRef
go back to reference K. Böröczky, Jr., G. Wintsche, Covering the sphere by equal balls, in Discrete and Computational Geometry: The Goodman-Pollack Festschrift, ed. by B. Aronov, S. Basu, J. Pach, M. Sharir (Springer, Berlin, 2003), pp. 235–251CrossRef K. Böröczky, Jr., G. Wintsche, Covering the sphere by equal balls, in Discrete and Computational Geometry: The Goodman-Pollack Festschrift, ed. by B. Aronov, S. Basu, J. Pach, M. Sharir (Springer, Berlin, 2003), pp. 235–251CrossRef
go back to reference S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, Oxford, 2013)MATHCrossRef S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, Oxford, 2013)MATHCrossRef
go back to reference L. Breiman, W. Meisel, E. Purcell, Variable kernel estimates of multivariate densities. Technometrics 19, 135–144 (1977)MATHCrossRef L. Breiman, W. Meisel, E. Purcell, Variable kernel estimates of multivariate densities. Technometrics 19, 135–144 (1977)MATHCrossRef
go back to reference T. Cacoullos, Estimation of a multivariate density. Ann. Inst. Stat. Math. 18, 178–189 (1966) T. Cacoullos, Estimation of a multivariate density. Ann. Inst. Stat. Math. 18, 178–189 (1966)
go back to reference H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–507 (1952)MathSciNetMATHCrossRef H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493–507 (1952)MathSciNetMATHCrossRef
go back to reference G. Collomb, Estimation de la régression par la méthode des k points les plus proches avec noyau: quelques propriétés de convergence ponctuelle, in Statistique non Paramétrique Asymptotique, ed. by J.-P. Raoult. Lecture Notes in Mathematics, vol. 821 (Springer, Berlin, 1980), pp. 159–175 G. Collomb, Estimation de la régression par la méthode des k points les plus proches avec noyau: quelques propriétés de convergence ponctuelle, in Statistique non Paramétrique Asymptotique, ed. by J.-P. Raoult. Lecture Notes in Mathematics, vol. 821 (Springer, Berlin, 1980), pp. 159–175
go back to reference G. Collomb, Estimation non paramétrique de la régression: Revue bibliographique. Int. Stat. Rev. 49, 75–93 (1981)MATHCrossRef G. Collomb, Estimation non paramétrique de la régression: Revue bibliographique. Int. Stat. Rev. 49, 75–93 (1981)MATHCrossRef
go back to reference T.M. Cover, Estimation by the nearest neighbor rule. IEEE Trans. Inf. Theory 14, 50–55 (1968)MATHCrossRef T.M. Cover, Estimation by the nearest neighbor rule. IEEE Trans. Inf. Theory 14, 50–55 (1968)MATHCrossRef
go back to reference T.M. Cover, P.E. Hart, Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13, 21–27 (1967)MATHCrossRef T.M. Cover, P.E. Hart, Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13, 21–27 (1967)MATHCrossRef
go back to reference T.M. Cover, J.A. Thomas, Elements of Information Theory, 2nd edn. (Wiley, Hoboken, 2006)MATH T.M. Cover, J.A. Thomas, Elements of Information Theory, 2nd edn. (Wiley, Hoboken, 2006)MATH
go back to reference T.M. Cover, J.M. Van Campenhout, On the possible orderings in the measurement selection problem. IEEE Trans. Syst. Man Cybern. 7, 657–661 (1977)MathSciNetMATHCrossRef T.M. Cover, J.M. Van Campenhout, On the possible orderings in the measurement selection problem. IEEE Trans. Syst. Man Cybern. 7, 657–661 (1977)MathSciNetMATHCrossRef
go back to reference B.V. Dasarathy, Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques (IEEE Computer Society Press, Los Alamitos, 1991) B.V. Dasarathy, Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques (IEEE Computer Society Press, Los Alamitos, 1991)
go back to reference M. de Guzmán, Differentiation of Integrals in \(\mathbb{R}^{n}\). Lecture Notes in Mathematics, vol. 481 (Springer, Berlin, 1975) M. de Guzmán, Differentiation of Integrals in \(\mathbb{R}^{n}\). Lecture Notes in Mathematics, vol. 481 (Springer, Berlin, 1975)
go back to reference P.A. Devijver, An overview of asymptotic properties of nearest neighbor rules, in Pattern Recognition in Practice, ed. by E.S. Gelsema, L.N. Kanal (North-Holland, Amsterdam, 1980), pp. 343–350 P.A. Devijver, An overview of asymptotic properties of nearest neighbor rules, in Pattern Recognition in Practice, ed. by E.S. Gelsema, L.N. Kanal (North-Holland, Amsterdam, 1980), pp. 343–350
go back to reference L. Devroye, On the inequality of Cover and Hart in nearest neighbor discrimination. IEEE Trans. Pattern Anal. Mach. Intell. 3, 75–78 (1981b)MATHCrossRef L. Devroye, On the inequality of Cover and Hart in nearest neighbor discrimination. IEEE Trans. Pattern Anal. Mach. Intell. 3, 75–78 (1981b)MATHCrossRef
go back to reference L. Devroye, Necessary and sufficient conditions for the pointwise convergence of nearest neighbor regression function estimates. Z. Warhscheinlichkeitstheorie Verwandte Geb. 61, 467–481 (1982)MathSciNetMATHCrossRef L. Devroye, Necessary and sufficient conditions for the pointwise convergence of nearest neighbor regression function estimates. Z. Warhscheinlichkeitstheorie Verwandte Geb. 61, 467–481 (1982)MathSciNetMATHCrossRef
go back to reference L. Devroye, A Course in Density Estimation (Birkhäuser, Boston, 1987)MATH L. Devroye, A Course in Density Estimation (Birkhäuser, Boston, 1987)MATH
go back to reference L. Devroye, Automatic pattern recognition: a study of the probability of error. IEEE Trans. Pattern Anal. Mach. Intell. 10, 530–543 (1988)MATHCrossRef L. Devroye, Automatic pattern recognition: a study of the probability of error. IEEE Trans. Pattern Anal. Mach. Intell. 10, 530–543 (1988)MATHCrossRef
go back to reference L. Devroye, Exponential inequalities in nonparametric estimation, in Nonparametric Functional Estimation and Related Topics, ed. by G. Roussas (Springer, Dordrecht, 1991a), pp. 31–44CrossRef L. Devroye, Exponential inequalities in nonparametric estimation, in Nonparametric Functional Estimation and Related Topics, ed. by G. Roussas (Springer, Dordrecht, 1991a), pp. 31–44CrossRef
go back to reference L. Devroye, A universal k-nearest neighbor procedure in discrimination, in Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, ed. by B.V. Dasarathy (IEEE Computer Society Press, Los Alamitos, 1991b), pp. 101–106 L. Devroye, A universal k-nearest neighbor procedure in discrimination, in Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, ed. by B.V. Dasarathy (IEEE Computer Society Press, Los Alamitos, 1991b), pp. 101–106
go back to reference L. Devroye, L. Györfi, Nonparametric Density Estimation: The L 1 View (Wiley, New York, 1985)MATH L. Devroye, L. Györfi, Nonparametric Density Estimation: The L 1 View (Wiley, New York, 1985)MATH
go back to reference L. Devroye, G. Lugosi, Combinatorial Methods in Density Estimation (Springer, New York, 2001)MATHCrossRef L. Devroye, G. Lugosi, Combinatorial Methods in Density Estimation (Springer, New York, 2001)MATHCrossRef
go back to reference L. Devroye, T.J. Wagner, Nearest neighbor methods in discrimination, in Handbook of Statistics, vol. 2, ed. by P.R. Krishnaiah, L.N. Kanal (North-Holland, Amsterdam, 1982), pp. 193–197 L. Devroye, T.J. Wagner, Nearest neighbor methods in discrimination, in Handbook of Statistics, vol. 2, ed. by P.R. Krishnaiah, L.N. Kanal (North-Holland, Amsterdam, 1982), pp. 193–197
go back to reference L. Devroye, L. Györfi, A. Krzyżak, G. Lugosi, On the strong universal consistency of nearest neighbor regression function estimates. Ann. Stat. 22, 1371–1385 (1994)MathSciNetMATHCrossRef L. Devroye, L. Györfi, A. Krzyżak, G. Lugosi, On the strong universal consistency of nearest neighbor regression function estimates. Ann. Stat. 22, 1371–1385 (1994)MathSciNetMATHCrossRef
go back to reference L. Devroye, L. Györfi, G. Lugosi, A Probabilistic Theory of Pattern Recognition (Springer, New York, 1996)MATHCrossRef L. Devroye, L. Györfi, G. Lugosi, A Probabilistic Theory of Pattern Recognition (Springer, New York, 1996)MATHCrossRef
go back to reference L. Devroye, L. Györfi, D. Schäfer, H. Walk, The estimation problem of minimum mean squared error. Stat. Decis. 21, 15–28 (2003)MathSciNetMATHCrossRef L. Devroye, L. Györfi, D. Schäfer, H. Walk, The estimation problem of minimum mean squared error. Stat. Decis. 21, 15–28 (2003)MathSciNetMATHCrossRef
go back to reference L.P. Devroye, The uniform convergence of nearest neighbor regression function estimators and their application in optimization. IEEE Trans. Inf. Theory 2, 142–151 (1978)MathSciNetMATHCrossRef L.P. Devroye, The uniform convergence of nearest neighbor regression function estimators and their application in optimization. IEEE Trans. Inf. Theory 2, 142–151 (1978)MathSciNetMATHCrossRef
go back to reference W. Doeblin, Exposé de la théorie des chaînes simples constantes de Markov à un nombre fini d’états. Rev. Math. Union Interbalkanique 2, 77–105 (1937) W. Doeblin, Exposé de la théorie des chaînes simples constantes de Markov à un nombre fini d’états. Rev. Math. Union Interbalkanique 2, 77–105 (1937)
go back to reference C.-G. Esseen, On the Liapunoff limit of error in the theory of probability. Arkiv Matematik Astronomi Fysik A28, 1–19 (1942)MathSciNetMATH C.-G. Esseen, On the Liapunoff limit of error in the theory of probability. Arkiv Matematik Astronomi Fysik A28, 1–19 (1942)MathSciNetMATH
go back to reference D. Evans, A.J. Jones, W.M. Schmidt, Asymptotic moments of near-neighbour distance distributions. Proc. R. Soc. A 458, 2839–2849 (2002)MathSciNetMATHCrossRef D. Evans, A.J. Jones, W.M. Schmidt, Asymptotic moments of near-neighbour distance distributions. Proc. R. Soc. A 458, 2839–2849 (2002)MathSciNetMATHCrossRef
go back to reference E. Fix, J.L. Hodges, Discriminatory analysis – Nonparametric discrimination: consistency properties. Project 21-49-004, Report Number 4 (USAF School of Aviation Medicine, Randolph Field, Texas, 1951), pp. 261–279 E. Fix, J.L. Hodges, Discriminatory analysis – Nonparametric discrimination: consistency properties. Project 21-49-004, Report Number 4 (USAF School of Aviation Medicine, Randolph Field, Texas, 1951), pp. 261–279
go back to reference E. Fix, J.L. Hodges, Discriminatory analysis – Nonparametric discrimination: small sample performance. Project 21-49-004, Report Number 11 (USAF School of Aviation Medicine, Randolph Field, Texas, 1952), pp. 280–322 E. Fix, J.L. Hodges, Discriminatory analysis – Nonparametric discrimination: small sample performance. Project 21-49-004, Report Number 11 (USAF School of Aviation Medicine, Randolph Field, Texas, 1952), pp. 280–322
go back to reference E. Fix, J.L. Hodges, Discriminatory analysis: nonparametric discrimination: consistency properties, in Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, ed. by B.V. Dasarathy (IEEE Computer Society Press, Los Alamitos, 1991a), pp. 32–39 E. Fix, J.L. Hodges, Discriminatory analysis: nonparametric discrimination: consistency properties, in Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, ed. by B.V. Dasarathy (IEEE Computer Society Press, Los Alamitos, 1991a), pp. 32–39
go back to reference E. Fix, J.L. Hodges, Discriminatory analysis: nonparametric discrimination: small sample performance, in Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, ed. by B.V. Dasarathy (IEEE Computer Society Press, Los Alamitos, 1991b), pp. 40–56 E. Fix, J.L. Hodges, Discriminatory analysis: nonparametric discrimination: small sample performance, in Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques, ed. by B.V. Dasarathy (IEEE Computer Society Press, Los Alamitos, 1991b), pp. 40–56
go back to reference J. Fritz, Distribution-free exponential error bound for nearest neighbor pattern classification. IEEE Trans. Inf. Theory 21, 552–557 (1975)MathSciNetMATHCrossRef J. Fritz, Distribution-free exponential error bound for nearest neighbor pattern classification. IEEE Trans. Inf. Theory 21, 552–557 (1975)MathSciNetMATHCrossRef
go back to reference S. Gada, T. Klein, C. Marteau, Classification with the nearest neighbor rule in general finite dimensional spaces. Ann. Stat. arXiv:1411.0894 (2015) S. Gada, T. Klein, C. Marteau, Classification with the nearest neighbor rule in general finite dimensional spaces. Ann. Stat. arXiv:1411.0894 (2015)
go back to reference J. Galambos, The Asymptotic Theory of Extreme Order Statistics (Wiley, New York, 1978)MATH J. Galambos, The Asymptotic Theory of Extreme Order Statistics (Wiley, New York, 1978)MATH
go back to reference M. Giaquinta, G. Modica, Mathematical Analysis: An Introduction to Functions of Several Variables (Birkhäuser, Boston, 2009)MATHCrossRef M. Giaquinta, G. Modica, Mathematical Analysis: An Introduction to Functions of Several Variables (Birkhäuser, Boston, 2009)MATHCrossRef
go back to reference G.R. Grimmett, D.R. Stirzaker, Probability and Random Processes, 3rd edn. (Oxford University Press, Oxford, 2001)MATH G.R. Grimmett, D.R. Stirzaker, Probability and Random Processes, 3rd edn. (Oxford University Press, Oxford, 2001)MATH
go back to reference I. Guyon, A. Elisseeff, An introduction to variable and feature selection. J. Mach. Learn. Res. 3, 1157–1182 (2003)MATH I. Guyon, A. Elisseeff, An introduction to variable and feature selection. J. Mach. Learn. Res. 3, 1157–1182 (2003)MATH
go back to reference L. Györfi, An upper bound of error probabilities for multihypothesis testing and its application in adaptive pattern recognition. Probl. Control Inf. Theory 5, 449–457 (1976)MATH L. Györfi, An upper bound of error probabilities for multihypothesis testing and its application in adaptive pattern recognition. Probl. Control Inf. Theory 5, 449–457 (1976)MATH
go back to reference L. Györfi, Z. Györfi, An upper bound on the asymptotic error probability of the k-nearest neighbor rule for multiple classes. IEEE Trans. Inf. Theory 24, 512–514 (1978)MathSciNetMATHCrossRef L. Györfi, Z. Györfi, An upper bound on the asymptotic error probability of the k-nearest neighbor rule for multiple classes. IEEE Trans. Inf. Theory 24, 512–514 (1978)MathSciNetMATHCrossRef
go back to reference L. Györfi, M. Kohler, A. Krzyżak, H. Walk, A Distribution-Free Theory of Nonparametric Regression (Springer, New York, 2002)MATHCrossRef L. Györfi, M. Kohler, A. Krzyżak, H. Walk, A Distribution-Free Theory of Nonparametric Regression (Springer, New York, 2002)MATHCrossRef
go back to reference T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. (Springer, New York, 2009)MATHCrossRef T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd edn. (Springer, New York, 2009)MATHCrossRef
go back to reference R.M. Karp, Probabilistic Analysis of Algorithms. Class Notes (University of California, Berkeley, 1988) R.M. Karp, Probabilistic Analysis of Algorithms. Class Notes (University of California, Berkeley, 1988)
go back to reference J.D. Kečkić, P.M. Vasić, Some inequalities for the gamma function. Publ. Inst. Math. 11, 107–114 (1971)MathSciNetMATH J.D. Kečkić, P.M. Vasić, Some inequalities for the gamma function. Publ. Inst. Math. 11, 107–114 (1971)MathSciNetMATH
go back to reference J. Kiefer, Iterated logarithm analogues for sample quantiles when p n ↓ 0, in Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, ed. by L.M. Le Cam, J. Neyman, E.L. Scott. Theory of Statistics, vol. 1 (University of California Press, Berkeley, 1972), pp. 227–244 J. Kiefer, Iterated logarithm analogues for sample quantiles when p n 0, in Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, ed. by L.M. Le Cam, J. Neyman, E.L. Scott. Theory of Statistics, vol. 1 (University of California Press, Berkeley, 1972), pp. 227–244
go back to reference B.K. Kim, J. Van Ryzin, Uniform consistency of a histogram density estimator and modal estimation. Commun. Stat. 4, 303–315 (1975)MathSciNetMATHCrossRef B.K. Kim, J. Van Ryzin, Uniform consistency of a histogram density estimator and modal estimation. Commun. Stat. 4, 303–315 (1975)MathSciNetMATHCrossRef
go back to reference R. Kohavi, G.H. John, Wrappers for feature subset selection. Artif. Intell. 97, 273–324 (1997)MATHCrossRef R. Kohavi, G.H. John, Wrappers for feature subset selection. Artif. Intell. 97, 273–324 (1997)MATHCrossRef
go back to reference M. Kohler, A. Krzyżak, On the rate of convergence of local averaging plug-in classification rules under a margin condition. IEEE Trans. Inf. Theory 53, 1735–1742 (2007)MathSciNetMATHCrossRef M. Kohler, A. Krzyżak, On the rate of convergence of local averaging plug-in classification rules under a margin condition. IEEE Trans. Inf. Theory 53, 1735–1742 (2007)MathSciNetMATHCrossRef
go back to reference M. Kohler, A. Krzyżak, H. Walk, Rates of convergence for partitioning and nearest neighbor regression estimates with unbounded data. J. Multivar. Anal. 97, 311–323 (2006)MathSciNetMATHCrossRef M. Kohler, A. Krzyżak, H. Walk, Rates of convergence for partitioning and nearest neighbor regression estimates with unbounded data. J. Multivar. Anal. 97, 311–323 (2006)MathSciNetMATHCrossRef
go back to reference L.F. Kozachenko, N.N. Leonenko, Sample estimate of the entropy of a random vector. Probl. Inf. Transm. 23, 95–101 (1987)MATH L.F. Kozachenko, N.N. Leonenko, Sample estimate of the entropy of a random vector. Probl. Inf. Transm. 23, 95–101 (1987)MATH
go back to reference S.R. Kulkarni, S.E. Posner, Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Trans. Inf. Theory 41, 1028–1039 (1995)MathSciNetMATHCrossRef S.R. Kulkarni, S.E. Posner, Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Trans. Inf. Theory 41, 1028–1039 (1995)MathSciNetMATHCrossRef
go back to reference V. Kumar, S. Minz, Feature selection: a literature review. Smart Comput. Rev. 4, 211–229 (2014)CrossRef V. Kumar, S. Minz, Feature selection: a literature review. Smart Comput. Rev. 4, 211–229 (2014)CrossRef
go back to reference S.L. Lai, Large Sample Properties of k-Nearest Neighbor Procedures. Ph.D. Thesis, University of California, Los Angeles, 1977 S.L. Lai, Large Sample Properties of k-Nearest Neighbor Procedures. Ph.D. Thesis, University of California, Los Angeles, 1977
go back to reference N. Leonenko, L. Pronzato, V. Savani, A class of Rényi information estimators for multidimensional densities. Ann. Stat. 36, 2153–2182 (2008)MATHCrossRef N. Leonenko, L. Pronzato, V. Savani, A class of Rényi information estimators for multidimensional densities. Ann. Stat. 36, 2153–2182 (2008)MATHCrossRef
go back to reference E. Liitiäinen, A. Lendasse, F. Corona, Non-parametric residual variance estimation in supervised learning, in Computational and Ambient Intelligence: 9th International Work-Conference on Artificial Neural Networks, ed. by F. Sandoval, A. Prieto, J. Cabestany, M. Graña (Springer, Berlin, 2007), pp. 63–71CrossRef E. Liitiäinen, A. Lendasse, F. Corona, Non-parametric residual variance estimation in supervised learning, in Computational and Ambient Intelligence: 9th International Work-Conference on Artificial Neural Networks, ed. by F. Sandoval, A. Prieto, J. Cabestany, M. Graña (Springer, Berlin, 2007), pp. 63–71CrossRef
go back to reference E. Liitiäinen, A. Lendasse, F. Corona, Bounds on the mean power-weighted nearest neighbour distance. Proc. R. Soc. A 464, 2293–2301 (2008a)MathSciNetMATHCrossRef E. Liitiäinen, A. Lendasse, F. Corona, Bounds on the mean power-weighted nearest neighbour distance. Proc. R. Soc. A 464, 2293–2301 (2008a)MathSciNetMATHCrossRef
go back to reference E. Liitiäinen, A. Lendasse, F. Corona, On nonparametric residual variance estimation. Neural Process. Lett. 28, 155–167 (2008b)MATHCrossRef E. Liitiäinen, A. Lendasse, F. Corona, On nonparametric residual variance estimation. Neural Process. Lett. 28, 155–167 (2008b)MATHCrossRef
go back to reference E. Liitiäinen, F. Corona, A. Lendasse, Residual variance estimation using a nearest neighbor statistic. J. Multivar. Anal. 101, 811–823 (2010)MathSciNetMATHCrossRef E. Liitiäinen, F. Corona, A. Lendasse, Residual variance estimation using a nearest neighbor statistic. J. Multivar. Anal. 101, 811–823 (2010)MathSciNetMATHCrossRef
go back to reference J.W. Lindeberg, Über das Exponentialgesetz in der Wahrscheinlichkeitsrechnung. Ann. Acad. Sci. Fenn. 16, 1–23 (1920)MATH J.W. Lindeberg, Über das Exponentialgesetz in der Wahrscheinlichkeitsrechnung. Ann. Acad. Sci. Fenn. 16, 1–23 (1920)MATH
go back to reference D.O. Loftsgaarden, C.P. Quesenberry, A nonparametric estimate of a multivariate density function. Ann. Math. Stat. 36, 1049–1051 (1965)MathSciNetMATHCrossRef D.O. Loftsgaarden, C.P. Quesenberry, A nonparametric estimate of a multivariate density function. Ann. Math. Stat. 36, 1049–1051 (1965)MathSciNetMATHCrossRef
go back to reference Y.P. Mack, Asymptotic normality of multivariate k-NN density estimates. Sankhy\(\bar{\mathrm{a}}\) A 42, 53–63 (1980) Y.P. Mack, Asymptotic normality of multivariate k-NN density estimates. Sankhy\(\bar{\mathrm{a}}\) A 42, 53–63 (1980)
go back to reference J. Marcinkiewicz, A. Zygmund, Sur les fonctions indépendantes. Fundam. Math. 29, 60–90 (1937)MATH J. Marcinkiewicz, A. Zygmund, Sur les fonctions indépendantes. Fundam. Math. 29, 60–90 (1937)MATH
go back to reference A.W. Marshall, I. Olkin, Inequalities: Theory of Majorization and Its Applications (Academic Press, New York, 1979)MATH A.W. Marshall, I. Olkin, Inequalities: Theory of Majorization and Its Applications (Academic Press, New York, 1979)MATH
go back to reference P. Massart, Concentration Inequalities and Model Selection (Springer, Berlin, 2007)MATH P. Massart, Concentration Inequalities and Model Selection (Springer, Berlin, 2007)MATH
go back to reference J. Matous̆ek, Lectures on Discrete Geometry (Springer, New York, 2002) J. Matous̆ek, Lectures on Discrete Geometry (Springer, New York, 2002)
go back to reference C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, ed. by J. Siemons. London Mathematical Society Lecture Note Series, vol. 141 (Cambridge University Press, Cambridge, 1989), pp. 148–188 C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, ed. by J. Siemons. London Mathematical Society Lecture Note Series, vol. 141 (Cambridge University Press, Cambridge, 1989), pp. 148–188
go back to reference J.V. Michalowicz, J.M. Nichols, F. Bucholtz, Handbook of Differential Entropy (CRC, Boca Raton, 2014)MATH J.V. Michalowicz, J.M. Nichols, F. Bucholtz, Handbook of Differential Entropy (CRC, Boca Raton, 2014)MATH
go back to reference K.S. Miller, Multidimensional Gaussian Distributions (Wiley, New York, 1964)MATH K.S. Miller, Multidimensional Gaussian Distributions (Wiley, New York, 1964)MATH
go back to reference J.W. Milnor, On the Betti numbers of real algebraic varieties. Proc. Am. Math. Soc. 15, 275–280 (1964)MATHCrossRef J.W. Milnor, On the Betti numbers of real algebraic varieties. Proc. Am. Math. Soc. 15, 275–280 (1964)MATHCrossRef
go back to reference D.S. Moore, J.W. Yackel, Large sample properties of nearest neighbor density function estimators, in Statistical Decision Theory and Related Topics II: Proceedings of a Symposium Held at Purdue University, May 17–19, 1976, ed. by S.S. Gupta, D.S. Moore (Academic Press, New York, 1977a), pp. 269–279CrossRef D.S. Moore, J.W. Yackel, Large sample properties of nearest neighbor density function estimators, in Statistical Decision Theory and Related Topics II: Proceedings of a Symposium Held at Purdue University, May 17–19, 1976, ed. by S.S. Gupta, D.S. Moore (Academic Press, New York, 1977a), pp. 269–279CrossRef
go back to reference C. Mortici, C.-P. Chen, New sharp double inequalities for bounding the gamma and digamma function. Analele Universităţii de Vest din Timişoara, Seria Matematică-Informatică 49, 69–75 (2011)MathSciNetMATH C. Mortici, C.-P. Chen, New sharp double inequalities for bounding the gamma and digamma function. Analele Universităţii de Vest din Timişoara, Seria Matematică-Informatică 49, 69–75 (2011)MathSciNetMATH
go back to reference E.A. Nadaraya, On nonparametric estimates of density functions and regression curves. Theory Probab. Appl. 10, 186–190 (1965)MATHCrossRef E.A. Nadaraya, On nonparametric estimates of density functions and regression curves. Theory Probab. Appl. 10, 186–190 (1965)MATHCrossRef
go back to reference R. Olshen, Discussion on a paper by C.J. Stone. Ann. Stat. 5, 632–633 (1977) R. Olshen, Discussion on a paper by C.J. Stone. Ann. Stat. 5, 632–633 (1977)
go back to reference M.D. Penrose, J.E. Yukich, Laws of large numbers and nearest neighbor distances, in Advances in Directional and Linear Statistics: A Festschrift for Sreenivasa Rao Jammalamadaka, ed. by M.T. Wells, A. SenGupta (Physica, Heidelberg, 2011), pp. 189–199CrossRef M.D. Penrose, J.E. Yukich, Laws of large numbers and nearest neighbor distances, in Advances in Directional and Linear Statistics: A Festschrift for Sreenivasa Rao Jammalamadaka, ed. by M.T. Wells, A. SenGupta (Physica, Heidelberg, 2011), pp. 189–199CrossRef
go back to reference I.G. Petrovskiĭ, O.A. Oleĭnik, On the topology of real algebraic surfaces. Am. Math. Soc. Translat. 70 (1952) I.G. Petrovskiĭ, O.A. Oleĭnik, On the topology of real algebraic surfaces. Am. Math. Soc. Translat. 70 (1952)
go back to reference R. Pollack, M.-F. Roy, On the number of cells defined by a set of polynomials. Comp. R. Acad. Sci. Sér. 1: Math. 316, 573–577 (1993) R. Pollack, M.-F. Roy, On the number of cells defined by a set of polynomials. Comp. R. Acad. Sci. Sér. 1: Math. 316, 573–577 (1993)
go back to reference S.T. Rachev, L. Rüschendorf, Mass Transportation Problems. Volume I: Theory (Springer, New York, 1998) S.T. Rachev, L. Rüschendorf, Mass Transportation Problems. Volume I: Theory (Springer, New York, 1998)
go back to reference B.L.S. Prakasa Rao, Nonparametric Functional Estimation (Academic Press, Orlando, 1983)MATH B.L.S. Prakasa Rao, Nonparametric Functional Estimation (Academic Press, Orlando, 1983)MATH
go back to reference A. Rényi, On measures of entropy and information, in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability. Contributions to the Theory of Statistics, vol. 1 (University of California Press, Berkeley, 1961), pp. 547–561 A. Rényi, On measures of entropy and information, in Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability. Contributions to the Theory of Statistics, vol. 1 (University of California Press, Berkeley, 1961), pp. 547–561
go back to reference A. Rényi, Probability Theory (North-Holland, Amsterdam, 1970)MATH A. Rényi, Probability Theory (North-Holland, Amsterdam, 1970)MATH
go back to reference C.C. Rodríguez, On a new class of density estimators. Technical Report (Department of Mathematics and Statistics, University at Albany, Albany, 1986) C.C. Rodríguez, On a new class of density estimators. Technical Report (Department of Mathematics and Statistics, University at Albany, Albany, 1986)
go back to reference C.C. Rodríguez, Optimal recovery of local truth, in Bayesian Inference and Maximum Entropy Methods in Science and Engineering: 19th International Workshop, vol. 567, ed. by J.T. Rychert, G.J. Erickson, C.R. Smith (American Institute of Physics Conference Proceedings, Melville, 2001), pp. 89–115 C.C. Rodríguez, Optimal recovery of local truth, in Bayesian Inference and Maximum Entropy Methods in Science and Engineering: 19th International Workshop, vol. 567, ed. by J.T. Rychert, G.J. Erickson, C.R. Smith (American Institute of Physics Conference Proceedings, Melville, 2001), pp. 89–115
go back to reference R.M. Royall, A class of non-parametric estimates of a smooth regression function. Technical Report No. 14 (Department of Statistics, Stanford University, Stanford, 1966) R.M. Royall, A class of non-parametric estimates of a smooth regression function. Technical Report No. 14 (Department of Statistics, Stanford University, Stanford, 1966)
go back to reference D.W. Scott, Multivariate Density Estimation: Theory, Practice, and Visualization (Wiley, New York, 1992)MATHCrossRef D.W. Scott, Multivariate Density Estimation: Theory, Practice, and Visualization (Wiley, New York, 1992)MATHCrossRef
go back to reference B.W. Silverman, Density Estimation for Statistics and Data Analysis (Chapman & Hall, London, 1986)MATHCrossRef B.W. Silverman, Density Estimation for Statistics and Data Analysis (Chapman & Hall, London, 1986)MATHCrossRef
go back to reference J.M. Steele, An Efron-Stein inequality for nonparametric statistics. Ann. Stat. 14, 753–758 (1986)MATHCrossRef J.M. Steele, An Efron-Stein inequality for nonparametric statistics. Ann. Stat. 14, 753–758 (1986)MATHCrossRef
go back to reference E.M. Stein, Singular Integrals and Differentiability Properties of Functions (Princeton University Press, Princeton, 1970)MATH E.M. Stein, Singular Integrals and Differentiability Properties of Functions (Princeton University Press, Princeton, 1970)MATH
go back to reference C.J. Stone, Consistent nonparametric regression (with discussion). Ann. Stat. 5, 595–645 (1977)MATHCrossRef C.J. Stone, Consistent nonparametric regression (with discussion). Ann. Stat. 5, 595–645 (1977)MATHCrossRef
go back to reference G.R. Terrell, Mathematical Statistics: A Unified Introduction (Springer, New York, 1999)MATH G.R. Terrell, Mathematical Statistics: A Unified Introduction (Springer, New York, 1999)MATH
go back to reference R. Thom, On the homology of real algebraic varieties, in Differential and Combinatorial Topology, ed. by S.S. Cairns (Princeton University Press, Princeton, 1965, in French) R. Thom, On the homology of real algebraic varieties, in Differential and Combinatorial Topology, ed. by S.S. Cairns (Princeton University Press, Princeton, 1965, in French)
go back to reference Y.L. Tong, Probability Inequalities in Multivariate Distributions (Academic Press, New York, 1980)MATH Y.L. Tong, Probability Inequalities in Multivariate Distributions (Academic Press, New York, 1980)MATH
go back to reference A.B. Tsybakov, Introduction to Nonparametric Estimation (Springer, New York, 2008)MATH A.B. Tsybakov, Introduction to Nonparametric Estimation (Springer, New York, 2008)MATH
go back to reference A.B. Tsybakov, E.C. van der Meulen, Root-n consistent estimators of entropy for densities with unbounded support. Scand. J. Stat. 23, 75–83 (1996)MathSciNetMATH A.B. Tsybakov, E.C. van der Meulen, Root-n consistent estimators of entropy for densities with unbounded support. Scand. J. Stat. 23, 75–83 (1996)MathSciNetMATH
go back to reference L.R. Turner, Inverse of the Vandermonde matrix with applications. NASA Technical Note D-3547 (Washington, 1966) L.R. Turner, Inverse of the Vandermonde matrix with applications. NASA Technical Note D-3547 (Washington, 1966)
go back to reference J. Van Ryzin, Bayes risk consistency of classification procedures using density estimation. Sankhy\(\bar{\mathrm{a}}\) A 28, 161–170 (1966) J. Van Ryzin, Bayes risk consistency of classification procedures using density estimation. Sankhy\(\bar{\mathrm{a}}\) A 28, 161–170 (1966)
go back to reference V.N. Vapnik, A.Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264–280 (1971)MATHCrossRef V.N. Vapnik, A.Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 264–280 (1971)MATHCrossRef
go back to reference T.J. Wagner, Strong consistency of a nonparametric estimate of a density function. IEEE Trans. Syst. Man Cybern. 3, 289–290 (1973)MathSciNetMATH T.J. Wagner, Strong consistency of a nonparametric estimate of a density function. IEEE Trans. Syst. Man Cybern. 3, 289–290 (1973)MathSciNetMATH
go back to reference H. Walk, A universal strong law of large numbers for conditional expectations via nearest neighbors. J. Multivar. Anal. 99, 1035–1050 (2008)MathSciNetMATHCrossRef H. Walk, A universal strong law of large numbers for conditional expectations via nearest neighbors. J. Multivar. Anal. 99, 1035–1050 (2008)MathSciNetMATHCrossRef
go back to reference G.S. Watson, Smooth regression analysis. Sankhy\(\bar{\mathrm{a}}\) A 26, 359–372 (1964) G.S. Watson, Smooth regression analysis. Sankhy\(\bar{\mathrm{a}}\) A 26, 359–372 (1964)
go back to reference G.S. Watson, M.R. Leadbetter, On the estimation of the probability density. Ann. Math. Stat. 34, 480–491 (1963)MATHCrossRef G.S. Watson, M.R. Leadbetter, On the estimation of the probability density. Ann. Math. Stat. 34, 480–491 (1963)MATHCrossRef
go back to reference R.L. Wheeden, A. Zygmund, Measure and Integral: An Introduction to Real Analysis (Marcel Dekker, New York, 1977)MATH R.L. Wheeden, A. Zygmund, Measure and Integral: An Introduction to Real Analysis (Marcel Dekker, New York, 1977)MATH
go back to reference P. Whittle, On the smoothing of probability density functions. J. R. Stat. Soc. B 20, 334–343 (1958)MathSciNetMATH P. Whittle, On the smoothing of probability density functions. J. R. Stat. Soc. B 20, 334–343 (1958)MathSciNetMATH
go back to reference C.T. Wolverton, T.J. Wagner, Asymptotically optimal discriminant functions for pattern classification. IEEE Trans. Inf. Theory 15, 258–265 (1969)MathSciNetMATHCrossRef C.T. Wolverton, T.J. Wagner, Asymptotically optimal discriminant functions for pattern classification. IEEE Trans. Inf. Theory 15, 258–265 (1969)MathSciNetMATHCrossRef
go back to reference L.C. Zhao, Exponential bounds of mean error for the nearest neighbor estimates of regression functions. J. Multivar. Anal. 21, 168–178 (1987)MathSciNetMATHCrossRef L.C. Zhao, Exponential bounds of mean error for the nearest neighbor estimates of regression functions. J. Multivar. Anal. 21, 168–178 (1987)MathSciNetMATHCrossRef
Metadata
Title
Advanced properties of uniform order statistics
Authors
Gérard Biau
Luc Devroye
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-25388-6_13