Learning $k$-Modal Distributions via Testing

by Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio

Theory of Computing, Volume 10(20), pp. 535-570, 2014

Bibliography with links to cited articles

[1]   Guillermo Alvarez de Toledo and Julio M. Fernandez: Patch-clamp measurements reveal multimodal distribution of granule sizes in rat mast cells. J. Cell Biology, 110(4):1033–1039, 1990. [doi:10.1083/jcb.110.4.1033]

[2]   Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. In Proc. 36th STOC, pp. 381–390. ACM Press, 2004. [doi:10.1145/1007352.1007414]

[3]   Lucien Birgé: Estimating a density under order restrictions: Nonasymptotic minimax risk. Annals of Statistics, 15(3):995–1012, 1987. Available at JSTOR.

[4]   Lucien Birgé: On the risk of histograms for estimating decreasing densities. Annals of Statistics, 15(3):1013–1022, 1987. Available at JSTOR.

[5]   Lucien Birgé: Estimation of unimodal densities without smoothness assumptions. Annals of Statistics, 25(3):970–981, 1997. Available at JSTOR.

[6]   Kung-Sik Chan and Howell Tong: Testing for multimodality with dependent data. Biometrika, 91(1):113–123, 2004. [doi:10.1093/biomet/91.1.113]

[7]   Loren Cobb, Peter Koppstein, and Neng Hsin Chen: Estimation and moment recursion relations for multimodal distributions of the exponential family. J. American Statistical Association, 78(381):124–130, 1983. [doi:10.1080/01621459.1983.10477940]

[8]   Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio: Learning k-modal distributions via testing. In Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’12), pp. 1371–1385. ACM Press, 2012. Available at ACM DL.

[9]   Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio: Learning Poisson binomial distributions. In Proc. 44th STOC, pp. 709–728. ACM Press, 2012. [doi:10.1145/2213977.2214042, arXiv:1107.2702]

[10]   Luc Devroye and Gábor Lugosi: A universally acceptable smoothing factor for kernel density estimates. Annals of Statistics, 24(6):2499–2512, 1996. Available at JSTOR.

[11]   Luc Devroye and Gábor Lugosi: Nonasymptotic universal smoothing factors, kernel complexity and Yatracos classes. Annals of Statistics, 25(6):2626–2637, 1997. Available at JSTOR.

[12]   Luc Devroye and Gábor Lugosi: Combinatorial Methods in Density Estimation. Springer, 2001.

[13]   Francesco R. Ferraro, Barbara Paltrinieri, Flavio Fusi Pecci, Robert T. Rood, and Ben Dorman: Multimodal distributions along the horizontal branch. The Astrophysical Journal, 500(1):311–319, 1998. [doi:10.1086/305712]

[14]   Oded Goldreich, editor. Property Testing: Current Research and Surveys. Springer, 2010. LNCS 6390.

[15]   Oded Goldreich: Highlights of the Bertinoro workshop on Sublinear Algorithms (unpublished comments). Available at author’s website, 2011.

[16]   Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. Preliminary version at FOCS’96. [doi:10.1145/285055.285060]

[17]   Piet Groeneboom: Estimating a monotone density. In Proc. of the Berkeley Conference in Honor of Jerzy Neyman and Jack Kiefer, pp. 539–555, 1985. Available at CWI.

[18]   Michael J. Kearns and Dana Ron: Testing problems with sublearning sample complexity. J. Comput. System Sci., 61(3):428–456, 2000. Preliminary version in COLT’98. [doi:10.1006/jcss.1999.1656]

[19]   Johannes H. B. Kemperman: Mixtures with a limited number of modal intervals. Annals of Statistics, 19(4):2120–2144, 1991. Available at JSTOR.

[20]   Edmond A. Murphy: One cause? many causes?: The argument from the bimodal distribution. J. Chronic Diseases, 17(4):301–324, 1964. [doi:10.1016/0021-9681(64)90073-6]

[21]   Roger B. Myerson: Optimal auction design. Mathematics of Operations Research, 6(1):58–73, 1981. [doi:10.1287/moor.6.1.58]

[22]   Donald J. Newman and Lawrence Shepp: The double dixie cup problem. American Mathematical Monthly, 67(1):58–61, 1960. [doi:10.2307/2308930]

[23]   B. L. S. Prakasa Rao: Estimation of a unimodal density. Sankhya Ser. A, 31(1):23–36, 1969. Available at JSTOR.

[24]   Dana Ron: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 1(3):307–402, 2008. [doi:10.1561/2200000004]

[25]   Dana Ron: Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5:73–205, 2010. [doi:10.1561/0400000029]

[26]   Edward J. Wegman: Maximum likelihood estimation of a unimodal density. I. and II. Ann. Math. Statist., 41:457–471, 2169–2174, 1970. Available at JSTOR.

[27]   Yannis G. Yatracos: Rates of convergence of minimum distance estimators and Kolmogorov’s entropy. Annals of Statistics, 13(2):768–774, 1985. Available at JSTOR.