Using multiple samples to learn mixture models
In the mixture models problem it is assumed that there are K distributions θ 1 , . . . , θ K and one gets to observe a sample from a mixture of these distributions with unknown coefficients. The goal is to associate instances with their generating distributions, or to identify the parameters of the hidden distributions. In this work we make the assumption that we have access to several samples drawn from the same K underlying distributions, but with different mixing weights. As with topic modeling, having multiple samples is often a reasonable assumption. Instead of pooling the data into one sample, we prove that it is possible to use the differences between the samples to better recover the underlying structure. We present algorithms that recover the underlying structure under milder assumptions than the current state of art when either the dimensionality or the separation is high. The methods, when applied to topic modeling, allow generalization to words not present in the training data.
The problem of mixture model learning is considered, 
      assuming the availability of samples from the same mixture components, but 
      with different mixing weights. Two algorithms are described and analyzed. 
      The first, Multi Sample Projection (MSP), is a dimensionality 
      reduction algorithm that seeks to find the subspace spanned by the means 
      of the mixture components. MSP projects the data on the subspace spanned 
      by the overall means of each of the available sets of samples. The 
      theoretical analysis shows that the resulting procedure will maintain the 
      separation between the components assuming the dimension isn't too large, 
      and that there is sufficient variation in the mixing weight of each 
      mixture component between the samples. The second, Double Sample 
      Clustering (DSC), assumes that exactly two sets of samples are available, 
      that the mixture components have disjoint support, and that the 
      (appropriately normalized) mixture weights for any subset of the 
      components differs by some minimal amount between the two mixtures. The 
      algorithm iteratively trains binary classifiers on reweighted subsets of 
      the data sets, the intuition being that the support sets of the mixture 
      components are regions where the sign of the difference of the densities 
      of the two mixtures are constant. The general idea of taking 
      advantage of the "multiple sample" setting for clustering (there has to be 
      a less ambiguous name for that by the way, but I can't think of one...) is 
      interesting, and this paper may lead to further development of algorithms 
      and theory on the topic. The theoretical analysis of MSP and DSC 
      are not much stronger than showing conditions for consistency, which is 
      all that can be expected without further assumptions. As the authors point 
      out, sharper rates could be proven for the preservation of distances in 
      MSP if, for instance, a Gaussian mixture was assumed. The 
      numerical experiments provide encouraging evidence for the practical 
      benefit of MSP and DSC in the multiple sample setting. Small 
      issues: It is not clear to the reviewer why there is an exact 
      equality in part 2 of Lemma 1, as opposed to a \leq. Definition 1 
      is a bit confusing. My understanding is that here L refers to a base 
      classifier that will be used in the iterations of the algorithm, but the 
      conditions of the definition seem to be overly general (it allows any 
      measure over X and +/-1, for one thing, which doesn't have anything to do 
      with C_1,..., C_K; also condition 3 brings in C_I, even though, again, the 
      input to the algorithm may have nothing to do with the clusters). Perhaps 
      it would be clearer if Assumption 4 from section A.3 was used instead. 
      Also, there is no mention of what delta is; I'm guessing there should be a 
      "with probability 1-delta" somewhere, as well as an explanation that n is 
      the number of samples to be used by the algorithm L (n was used for the 
      number of dimensions earlier in the paper).