# On Sinkhorn's Algorithm and Choice Modeling

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 93 references that are in the map.
- First posted on arXiv 30 Sep 2023.

## Builds on (most cited first, 10 of 10)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [OSQP: An Operator Splitting Solver for Quadratic Programs](https://mlsanity.com/paper/1711.08013/) (2017)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [Efficient computation of rankings from pairwise comparisons](https://mlsanity.com/paper/2207.00076/) (2022)
- [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014)
- [Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling](https://mlsanity.com/paper/1801.02790/) (2018)
- [Pairwise Choice Markov Chains](https://mlsanity.com/paper/1603.02740/) (2016)
- [SISTA: learning optimal transport costs under sparsity constraints](https://mlsanity.com/paper/2009.08564/) (2020)
- [ChoiceRank: Identifying Preferences from Node Traffic in Networks](https://mlsanity.com/paper/1610.06525/) (2016)
- [HDSDP: Software for Semidefinite Programming](https://mlsanity.com/paper/2207.13862/) (2022)

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

- [Statistical ranking with dynamic covariates](https://mlsanity.com/paper/2406.16507/) (2024)
- [Statistical inference for pairwise comparison models](https://mlsanity.com/paper/2401.08463/) (2024)
- [Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting](https://mlsanity.com/paper/2402.18697/) (2024)
- [Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model](https://mlsanity.com/paper/2607.22221/) (2026)
- [Optimal Transport under Group Fairness Constraints](https://mlsanity.com/paper/2601.07144/) (2026)
- [Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp](https://mlsanity.com/paper/2608.11760/) (2026)

## Abstract (arXiv)

For a broad class of models widely used in practice for choice and ranking data based on Luce's choice axiom, including the Bradley--Terry--Luce and Plackett--Luce models, we show that the associated maximum likelihood estimation problems are equivalent to a classic matrix balancing problem with target row and column sums. This perspective opens doors between two seemingly unrelated research areas, and allows us to unify existing algorithms in the choice modeling literature as special instances or analogs of Sinkhorn's celebrated algorithm for matrix balancing. We draw inspirations from these connections and resolve some open problems on the study of Sinkhorn's algorithm. We establish the global linear convergence of Sinkhorn's algorithm for non-negative matrices whenever finite scaling matrices exist, and characterize its linear convergence rate in terms of the algebraic connectivity of a weighted bipartite graph. We further derive the sharp asymptotic rate of linear convergence, which generalizes a classic result of Knight (2008). To our knowledge, these are the first quantitative linear convergence results for Sinkhorn's algorithm for general non-negative matrices and positive marginals. Our results highlight the importance of connectivity and orthogonality structures in matrix balancing and Sinkhorn's algorithm, which could be of independent interest. More broadly, the connections we establish in this paper between matrix balancing and choice modeling could also help motivate further transmission of ideas and lead to interesting results in both disciplines.