# Optimal Learning of Mallows Block Model

arXiv: https://arxiv.org/abs/1906.01009 · HTML: https://mlsanity.com/paper/1906.01009/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 12 of 12)

- [Universalizing Weak Supervision](https://mlsanity.com/paper/2112.03865/) (2021)
- [On counterfactual inference with unobserved confounding](https://mlsanity.com/paper/2211.08209/) (2022)
- [Dissecting the Impact of Model Misspecification in Data-driven Optimization](https://mlsanity.com/paper/2503.00626/) (2025)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applications](https://mlsanity.com/paper/2201.08105/) (2022)
- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)
- [Fairness in Ranking: Robustness through Randomization without the Protected Attribute](https://mlsanity.com/paper/2403.19419/) (2024)
- [Federated Aggregation of Mallows Rankings: A Comparative Analysis of Borda and Lehmer Coding](https://mlsanity.com/paper/2409.00848/) (2024)
- [Private Statistical Estimation via Truncation](https://mlsanity.com/paper/2505.12541/) (2025)
- [Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation](https://mlsanity.com/paper/2507.08108/) (2025)

## Abstract (arXiv)

The Mallows model, introduced in the seminal paper of Mallows 1957, is one of the most fundamental ranking distribution over the symmetric group Sm. To analyze more complex ranking data, several studies considered the Generalized Mallows model defined by Fligner and Verducci 1986. Despite the significant research interest of ranking distributions, the exact sample complexity of estimating the parameters of a Mallows and a Generalized Mallows Model is not well-understood. The main result of the paper is a tight sample complexity bound for learning Mallows and Generalized Mallows Model. We approach the learning problem by analyzing a more general model which interpolates between the single parameter Mallows Model and the m parameter Mallows model. We call our model Mallows Block Model -- referring to the Block Models that are a popular model in theoretical statistics. Our sample complexity analysis gives tight bound for learning the Mallows Block Model for any number of blocks. We provide essentially matching lower bounds for our sample complexity results. As a corollary of our analysis, it turns out that, if the central ranking is known, one single sample from the Mallows Block Model is sufficient to estimate the spread parameters with error that goes to zero as the size of the permutations goes to infinity. In addition, we calculate the exact rate of the parameter estimation error.