Ultrafast Monte Carlo for Kernel Estimators and Generalized Statistical Summations

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 strat-ied 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 sam-ple 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.