January 2016, Vol. 28, No. 1, Pages 45-70
Posted Online December 22, 2015.
(doi:10.1162/NECO_a_00796)
© 2015 Massachusetts Institute of Technology
Sequential Tests for Large-Scale Learning
Anoop KorattikaraDepartment of Computer Science, University of California, Irvine, Irvine, CA 92697, U.S.A. akoratti@uci.edu
Yutian ChenDepartment of Engineering, University of Cambridge, Cambridge CB2 1PZ, U.K., and University of California, Irvine, Irvine, CA 92697, U.S.A. yutian.chen@eng.cam.ac.uk
Max WellingInformatics Institute, University of Amsterdam, 1098 XH Amsterdam, Netherlands m.welling@uva.nl
We argue that when faced with big data sets, learning and inference algorithms should compute updates using only subsets of data items. We introduce algorithms that use sequential hypothesis tests to adaptively select such a subset of data points. The statistical properties of this subsampling process can be used to control the efficiency and accuracy of learning or inference. In the context of learning by optimization, we test for the probability that the update direction is no more than 90 degrees in the wrong direction. In the context of posterior inference using Markov chain Monte Carlo, we test for the probability that our decision to accept or reject a sample is wrong. We experimentally evaluate our algorithms on a number of models and data sets.