Divide-and-Conquer Learning by Anchoring a Conical Hull
We reduce a broad class of fundamental machine learning problems, usually addressed by EM or sampling, to the problem of finding the k extreme rays spanning the conical hull of a1 data point set. These k "anchors" lead to a global solution and a more interpretable model that can even outperform EM and sampling on generalization error. To find the k anchors, we propose a novel divide-andconquer learning scheme "DCA" that distributes the problem to O(k log k) sametype sub-problems on different low-D random hyperplanes, each can be solved independently by any existing solver. For the 2D sub-problem, we instead present a non-iterative solver that only needs to compute an array of cosine values and its max/min entries. DCA also provides a faster subroutine inside other algorithms to check whether a point is covered in a conical hull, and thus improves these algorithms by providing significant speedups. We apply our method to GMM, HMM, LDA, NMF and subspace clustering, then show its competitive performance and scalability over other methods on large datasets.
Summary: This work proposes a new algorithm, "divide-and-conqueranchoring" (DCA), that solves the problem of selecting a subset A ofrows from a matrix Y such that those rows best model another matrix X:X = FY_A.  Previous work [29] addresses the simpler setting where X =Y and shows how this setting generalizes non-negative matrixfactorization (NMF).  The even more general X != Y setting that thiswork tackles is shown to generalize many core machine learningproblems: Gaussian mixture models (GMMs), hidden Markov models (HMMs),latent Dirichlet allocation (LDA), and subspace clustering (SC).  Thissetting relies on a "general separability assumption", which requiresthat there exist a subset A of Y's rows such that the rows of X arecontained in their cone.  Lemma 1 gives a very simple condition forthe identifiability of A, which allows DCA to be much more robust tovariance in the sample moments than spectral methods.  Experimentalresults on a large number of tasks indicate that DCA is almost alwaysmuch faster than traditional learning methods (including spectralones) without losing significant accuracy.Comments:Clarity, quality: The general idea and algorithm of the paper isclear, but the math in this work is pretty dense.  Additional small,illustrative examples and figures (similar to that of Figure 2) wouldbe helpful to make some of the concepts more concrete.Originality: The work of [29] seems to be the most closely related tothis paper.  The X != Y difference represents a large delta in termsof theoretical and experimental work though, so this paper iscertainly sufficiently original.Significance: Given the large number of practical machine learningtasks that this minimum conical hull problem encompasses, and itsclear performance advantages on them, this work seems verysignificant.Supplement: It's somewhat difficult to map back and forth between thedocument and the supplement, since the theorem/lemma/etc. numbersdon't match.  When referring to [3] (the supplement) from the mainpaper, it would be helpful if the authors could use the optionalargument of the cite command to indicate more precisely which part of[3] is being referenced: \cite[specific location]{supplement}.Additionally, there is a lot of information in the supplement thatisn't represented in the main body of the paper.  Perhaps this paperwould be better suited to a venue without page limits (such as ajournal).Experiments: Do the authors have plans to release the associated code?How were the s-values (50, 92, 133, 175) selected?  Often DCA, winsspeed-wise but loses slightly accuracy-wise.  Can the authors commentfurther on why this might be the case?  Are there knobs that can butturned on the DCA algorithm to alter the speed/accuracy balance?(Besides the s-knob, which doesn't seem to have a huge effect.)Organization: Since NMF is already covered by [29], it might makesense to leave its explanation and experiments out of the main body ofthe paper and focus on explaining the other tasks (or the theory) ingreater detail.The variable "c": The variable "c" in the definition of "s" on line268 is only really defined in the supplement.  Even there it'ssomewhat unclear what c's range is.  Can the authors provide amathematical statement describing the relationship between c and theflatness of the flattest anchor?  Is n the maximum value for c?Projection matrices: Proposition 1 indicates that projection matricesare drawn uniformly from the Grassmanian manifold, and the supplementindicates several other random matrix ensembles that could be drawnfrom.  It would be helpful if the authors could provide a fewreferences detailing how to draw from each of these.More minor notes:1) "although spectral method using" -> "although spectral methodsusing"2) "random drawn low-dimensional" -> "randomly drawn low-dimensional"3) Equation (1) and elsewhere: Use \left and \right to make bracketsand parentheses match the height of the math that they enclose.2) "general models such as matrix factorization and latent variablemodel" -> "general models such as matrix factorization and latentvariable models"4) "most popular models such as GMM and HMM" -> "most popular modelssuch as GMMs and HMMs"5) "the two D matrices in RHS of" -> "the two D matrices in the RHS of"6) "either matrix in LHS of" -> "either matrix in the LHS of"7) "each handled by a solver to minimum conical hull problem" -> "eachhandled by a solver to the minimum conical hull problem"8) "anchoring algorithm for sub-problem on 2D-plane" -> "anchoringalgorithm for a sub-problem on the 2D-plane"9) "Due to the convexity of cone" -> "Due to the convexity of cones"10) "For arbitrary point" -> "For an arbitrary point"11) "w.h.p.  solving" -> "w.h.p.\ solving"12) "given two sets of points(rows)" -> "given two sets of points(rows)"13) "under general separability assumption" -> "under the generalseparability assumption"14) Supplement, line 415: "Lemma ??" -> "Lemma 2"15) "each point on each curve is the result by averaging" -> "eachpoint on each curve is the result of averaging"16) "Because DCA uses separability assumption" -> "DCA uses theseparability assumption"17) There are many grammatical errors in the supplement besides theones listed above.  It could use a more careful proofreading.