TY - GEN

T1 - Near-minimax recursive density estimation on the binary hypercube

AU - Raginsky, Maxim

AU - Lazebnik, Svetlana

AU - Willett, Rebecca

AU - Silva, Jorge

PY - 2009

Y1 - 2009

N2 - This paper describes a recursive estimation procedure for multivariate binary densities using orthogonal expansions. For d covariates, there are 2 d 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.

AB - This paper describes a recursive estimation procedure for multivariate binary densities using orthogonal expansions. For d covariates, there are 2 d 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.

UR - http://www.scopus.com/inward/record.url?scp=84858784259&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858784259&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84858784259

SN - 9781605609492

T3 - Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference

SP - 1305

EP - 1312

BT - Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference

PB - Neural Information Processing Systems

T2 - 22nd Annual Conference on Neural Information Processing Systems, NIPS 2008

Y2 - 8 December 2008 through 11 December 2008

ER -