nips nips2008 nips2008-149 nips2008-149-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Maxim Raginsky, Svetlana Lazebnik, Rebecca Willett, Jorge Silva
Abstract: This paper describes a recursive estimation procedure for multivariate binary densities using orthogonal expansions. For d covariates, there are 2d basis coefficients to estimate, which renders conventional approaches computationally prohibitive when d is large. However, for a wide class of densities that satisfy a certain sparsity condition, our estimator runs in probabilistic polynomial time and adapts to the unknown sparsity of the underlying density in two key ways: (1) it attains near-minimax mean-squared error, and (2) the computational complexity is lower for sparser densities. Our method also allows for flexible control of the trade-off between mean-squared error and computational complexity.
[1] I. Shmulevich and W. Zhang. Binary analysis and optimization-based normalization of gene expression data. Bioinformatics 18(4):555–565, 2002.
[2] J.M. Carro. Estimating dynamic panel data discrete choice models with fixed effects. J. Econometrics 140:503–528, 2007.
[3] Z. Ghahramani and K. Heller. Bayesian sets. NIPS 18:435–442, 2006.
[4] J. Aitchison and C.G.G. Aitken. Multivariate binary discrimination by the kernel method. Biometrika 63(3):413–420, 1976.
[5] J. Ott and R.A. Kronmal. Some classification procedures for multivariate binary data using orthogonal functions. J. Amer. Stat. Assoc. 71(354):391–399, 1976.
[6] W.-Q. Liang and P.R. Krishnaiah. Nonparametric iterative estimation of multivariate binary density. J. Multivariate Anal. 16:162–172, 1985.
[7] J.S. Simonoff. Smoothing categorical data. J. Statist. Planning and Inference 47:41–60, 1995.
[8] M. Talagrand. On Russo’s approximate zero-one law. Ann. Probab. 22:1576–1587, 1994.
[9] I. Dinur, E. Friedgut, G. Kindler and R. O’Donnell. On the Fourier tails of bounded functions over the discrete cube. Israel J. Math. 160:389–421, 2007.
[10] I.M. Johnstone. Minimax Bayes, asymptotic minimax and sparse wavelet priors. In S.S. Gupta and J.O. Berger, eds., Statistical Decision Theory and Related Topics V, pp. 303–326, Springer, 1994.
[11] E.J. Cand` s and T. Tao. Near-optimal signal recovery from random projections: universal encoding stratee gies? IEEE Trans. Inf. Theory 52(12):5406–5425, 2006.
[12] O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. STOC, pp. 25–32, 1989.
[13] E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. SIAM J. Comput. 22(6):1331-1348, 1993.
[14] W. H¨ rdle, G. Kerkyacharian, D. Picard and A.B. Tsybakov. Wavelets, Approximation, and Statistical a Applications, Springer, 1998.
[15] S.A. van de Geer. Empirical Processes in M-Estimation, Cambridge Univ. Press, 2000.
[16] M. Talagrand. Sharper bounds for Gaussian and empirical processes. Ann. Probab. 22:28–76, 1994.