nips nips2007 nips2007-209 nips2007-209-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Charles L. Isbell, Michael P. Holmes, Alexander G. Gray
Abstract: Machine learning contains many computational bottlenecks in the form of nested summations over datasets. Kernel estimators and other methods are burdened by these expensive computations. Exact evaluation is typically O(n2 ) or higher, which severely limits application to large datasets. We present a multi-stage stratified Monte Carlo method for approximating such summations with probabilistic relative error control. The essential idea is fast approximation by sampling in trees. This method differs from many previous scalability techniques (such as standard multi-tree methods) in that its error is stochastic, but we derive conditions for error control and demonstrate that they work. Further, we give a theoretical sample complexity for the method that is independent of dataset size, and show that this appears to hold in experiments, where speedups reach as high as 1014 , many orders of magnitude beyond the previous state of the art. 1
[1] Nicol N. Schraudolph and Thore Graepel. Combining conjugate direction methods with stochastic approximation of gradients. In Workshop on Artificial Intelligence and Statistics (AISTATS), 2003.
[2] Alexander G. Gray and Andrew W. Moore. N-body problems in statistical learning. In Advances in Neural Information Processing Systems (NIPS) 13, 2000.
[3] Mike Klaas, Mark Briers, Nando de Freitas, and Arnaud Doucet. Fast particle smoothing: If I had a million particles. In International Conference on Machine Learning (ICML), 2006.
[4] Ping Wang, Dongryeol Lee, Alexander Gray, and James M. Rehg. Fast mean shift with accurate and stable convergence. In Workshop on Artificial Intelligence and Statistics (AISTATS), 2007.
[5] Michael P. Holmes, Alexander G. Gray, and Charles Lee Isbell Jr. Fast nonparametric conditional density estimation. In Uncertainty in Artificial Intelligence (UAI), 2007.
[6] Reuven Y. Rubinstein. Simulation and the Monte Carlo Method. John Wiley & Sons, 1981.
[7] Paul Glasserman. Monte Carlo methods in financial engineering. Springer-Verlag, 2004. 8