Divide-and-Conquer Learning by Anchoring a Conical Hull
This provides a more interpretable and globally optimal solution for various ML problems, though it appears incremental as it builds on existing conical hull concepts.
The paper tackles the problem of reducing a broad class of machine learning problems, such as GMM and HMM, to finding extremal rays spanning a conical hull, resulting in a method that can outperform EM and sampling on generalization error with competitive performance and scalability on rich datasets.
We reduce a broad class of machine learning problems, usually addressed by EM or sampling, to the problem of finding the $k$ extremal rays spanning the conical hull of a 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-and-conquer learning scheme "DCA" that distributes the problem to $\mathcal O(k\log k)$ same-type sub-problems on different low-D random hyperplanes, each can be solved by any solver. For the 2D sub-problem, we 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 for other methods to check whether a point is covered in a conical hull, which improves algorithm design in multiple dimensions and brings significant speedup to learning. We apply our method to GMM, HMM, LDA, NMF and subspace clustering, then show its competitive performance and scalability over other methods on rich datasets.