Multiple pass streaming algorithms for learning mixtures of distributions in Rd

AbstractWe present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles in Rd, for any d>0. Our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. Our algorithm makes 2ℓ+2 passes, for any ℓ>0, and requires memory at most Õ(ϵ−2/ℓk2d4+(4k)d), where ϵ is the tolerable error of the algorithm. This exhibits a strong memory-pass tradeoff in terms of ϵ: a few more passes significantly lower its memory requirements, thus trading one of the two most important resources in streaming computation for the other. Chang and Kannan first considered this problem for d=1,2.Our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but computation with such large inputs requires very restricted models of computation