Finding a latent k-simplex in O* (k · nnz(data)) time via Subset Smoothing

In this paper we show that the learning problem for a large class of Latent variable models, such as Mixed Membership Stochastic Block Models, Topic Models, and Adversarial Clustering can be posed geometrically as follows: find a latent k— vertex simplex, K in Rd, given n data points, each obtained by perturbing a latent point in K. This problem does not seem to have been addressed. Our main contribution is an efficient algorithm for the geometric problem under deterministic assumptions which naturally hold for the models considered here. We observe that for a suitable r ≤ n, K is close to a data-determined polytope K’ (the subset smoothed, polytope) which is the convex hull of the points, each obtained by averaging an r subset of data points. Our algorithm is simply stated: it optimizes k carefully chosen linear functions over K’ to find the k vertices of the latent simplex. The proof of correctness is more involved, drawing on existing and new tools from Numerical Analysis. Our overall runtime of O* (k nnz) is as good as the best times of existing algorithms (modulo O* (1) factor) for the special cases and is better for sparse data which is the norm in Topic Modelling and Mixed Membership models. Some consequences of our algorithm are: Mixed Membership Models and Topic Models: We give the first quasi-input-sparsity time algorithm for parameter estimation for k ϵ O* (1) Adversarial Clustering: In k–means, an adversary is allowed to move many data points from each cluster towards the convex hull of other cluster centers. Our algorithm still estimates cluster centers well.