Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments

• URL: http://arxiv.org/abs/2009.06784v2
• Date: Fri, 4 Mar 2022 18:56:19 GMT
• Title: Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments
• Authors: Cheng Mao and Yihong Wu
• Abstract summary: We study the widely used Mallows mixture model. In the high-dimensional setting, we propose an optimal-time algorithm that learns a Mallows mixture of permutations on $n$ elements.
• Score: 8.691957530860675
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In applications such as rank aggregation, mixture models for permutations are frequently used when the population exhibits heterogeneity. In this work, we study the widely used Mallows mixture model. In the high-dimensional setting, we propose a polynomial-time algorithm that learns a Mallows mixture of permutations on $n$ elements with the optimal sample complexity that is proportional to $\log n$, improving upon previous results that scale polynomially with $n$. In the high-noise regime, we characterize the optimal dependency of the sample complexity on the noise parameter. Both objectives are accomplished by first studying demixing permutations under a noiseless query model using groups of pairwise comparisons, which can be viewed as moments of the mixing distribution, and then extending these results to the noisy Mallows model by simulating the noiseless oracle.

Related papers

• Mixup Augmentation with Multiple Interpolations [26.46413903248954]
  We propose a simple yet effective extension called multi-mix, which generates multiple gradients from a sample pair. With an ordered sequence of generated samples, multi-mix can better guide the training process than standard mixup.
  arXiv  Detail & Related papers  (2024-06-03T15:16:09Z)
• Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models [8.097200145973389]
  We first establish a universal lower bound for the error rate in clustering any mixture model. We then demonstrate that iterative algorithms attain this lower bound in mixture models with sub-exponential tails. For datasets better modelled by Poisson or Negative Binomial mixtures, we study mixture models whose distributions belong to an exponential family. In such mixtures, we establish that Bregman hard clustering, a variant of Lloyd's algorithm employing a Bregman divergence, is rate optimal.
  arXiv  Detail & Related papers  (2024-02-23T16:51:17Z)
• A Generalized Multiscale Bundle-Based Hyperspectral Sparse Unmixing Algorithm [8.616208042031877]
  In hyperspectral sparse unmixing, a successful approach employs spectral bundles to address the variability of the endmembers in the spatial domain. We generalize a multiscale spatial regularization approach to solve the unmixing problem by incorporating group sparsity-inducing mixed norms.
  arXiv  Detail & Related papers  (2024-01-24T00:37:14Z)
• Fast Semisupervised Unmixing Using Nonconvex Optimization [80.11512905623417]
  We introduce a novel convex convex model for semi/library-based unmixing. We demonstrate the efficacy of Alternating Methods of sparse unsupervised unmixing.
  arXiv  Detail & Related papers  (2024-01-23T10:07:41Z)
• Improving Gradient-guided Nested Sampling for Posterior Inference [47.08481529384556]
  We present a performant, general-purpose gradient-guided nested sampling algorithm, $tt GGNS$. We show the potential of combining nested sampling with generative flow networks to obtain large amounts of high-quality samples from the posterior distribution.
  arXiv  Detail & Related papers  (2023-12-06T21:09:18Z)
• Fitting large mixture models using stochastic component selection [0.0]
  We propose a combination of the expectation of the computational and the Metropolis-Hastings algorithm to evaluate only a small number of components. The Markov chain of component assignments is sequentially generated across the algorithm's iterations. We put emphasis on generality of our method, equipping it with the ability to train both shallow and deep mixture models.
  arXiv  Detail & Related papers  (2021-10-10T12:39:53Z)
• Maximum Entropy Reinforcement Learning with Mixture Policies [54.291331971813364]
  We construct a tractable approximation of the mixture entropy using MaxEnt algorithms. We show that it is closely related to the sum of marginal entropies. We derive an algorithmic variant of Soft Actor-Critic (SAC) to the mixture policy case and evaluate it on a series of continuous control tasks.
  arXiv  Detail & Related papers  (2021-03-18T11:23:39Z)
• Estimating the Number of Components in Finite Mixture Models via the Group-Sort-Fuse Procedure [0.974672460306765]
  Group-Sort-Fuse (GSF) is a new penalized likelihood approach for simultaneous estimation of the order and mixing measure in finite mixture models. We show that the GSF is consistent in estimating the true mixture order and the $n-1/2$ convergence rate for parameter estimation up to polylogarithmic factors.
  arXiv  Detail & Related papers  (2020-05-24T02:38:12Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Algebraic and Analytic Approaches for Parameter Learning in Mixture Models [66.96778152993858]
  We present two different approaches for parameter learning in several mixture models in one dimension. For some of these distributions, our results represent the first guarantees for parameter estimation.
  arXiv  Detail & Related papers  (2020-01-19T05:10:56Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters. Five new and original methods are introduced, using neighborhoods and population behavior optimization metaheuristics. From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM.
  arXiv  Detail & Related papers  (2020-01-06T23:33:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.