Timezone: »
Poster
Near-minimax recursive density estimation on the binary hypercube
Maxim Raginsky · Svetlana Lazebnik · Rebecca Willett · Jorge G Silva
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.
Author Information
Maxim Raginsky (University of Illinois at Urbana-Champaign)
Svetlana Lazebnik (UIUC)
Rebecca Willett (Duke University)
Jorge G Silva (Duke University)
Related Events (a corresponding poster, oral, or spotlight)
-
2008 Spotlight: Near-minimax recursive density estimation on the binary hypercube »
Tue. Dec 9th 11:24 -- 11:25 PM Room
More from the Same Authors
-
2021 Poster: Information-theoretic generalization bounds for black-box learning algorithms »
Hrayr Harutyunyan · Maxim Raginsky · Greg Ver Steeg · Aram Galstyan -
2019 Poster: Universal Approximation of Input-Output Maps by Temporal Convolutional Nets »
Joshua Hanson · Maxim Raginsky -
2018 Poster: Minimax Statistical Learning with Wasserstein distances »
Jaeho Lee · Maxim Raginsky -
2018 Spotlight: Minimax Statistical Learning with Wasserstein distances »
Jaeho Lee · Maxim Raginsky -
2017 Poster: Information-theoretic analysis of generalization capability of learning algorithms »
Aolin Xu · Maxim Raginsky -
2017 Spotlight: Information-theoretic analysis of generalization capability of learning algorithms »
Aolin Xu · Maxim Raginsky -
2012 Poster: Angular Quantization based Binary Codes for Fast Similarity Search »
Yunchao Gong · Sanjiv Kumar · Vishal Verma · Svetlana Lazebnik -
2011 Poster: Lower Bounds for Passive and Active Learning »
Maxim Raginsky · Sasha Rakhlin -
2011 Spotlight: Lower Bounds for Passive and Active Learning »
Maxim Raginsky · Sasha Rakhlin -
2010 Workshop: Beyond classification: Machine Learning for next generation Computer Vision challenges »
Craig Saunders · Jakob Verbeek · Svetlana Lazebnik -
2010 Poster: Joint Analysis of Time-Evolving Binary Matrices and Associated Documents »
Eric X Wang · Dehong Liu · Jorge G Silva · David B Dunson · Lawrence Carin -
2009 Poster: Locality-sensitive binary codes from shift-invariant kernels »
Maxim Raginsky · Svetlana Lazebnik -
2009 Oral: Locality-Sensitive Binary Codes from Shift-Invariant Kernels »
Maxim Raginsky · Svetlana Lazebnik