TL;DR
This paper bridges the gap between choice modeling and matrix balancing by showing that estimating Luce choice models is equivalent to a matrix balancing problem. This connection allows the authors to provide the first quantitative global linear convergence results for Sinkhorn's algorithm on non-negative matrices, revealing the crucial role of graph connectivity in its performance.
What Problem Does This Paper Address?
Choice modeling, used to understand how people make decisions, and matrix balancing, a technique for adjusting data to meet certain constraints (like in transportation networks), have historically developed in parallel. Sinkhorn's algorithm, a popular method for matrix balancing, has recently gained traction for its efficiency in approximating optimal transport distances. However, its convergence behavior, especially for matrices with zero entries (common in network-based problems), remains not fully understood. This paper aims to unify these fields by demonstrating their deep connection and using this to resolve open questions about Sinkhorn's algorithm's convergence.
Methods
The core of the paper lies in establishing a formal equivalence between the maximum likelihood estimation of Luce choice models and the canonical matrix balancing problem. This involves reformulating the choice model's optimality conditions into a matrix balancing problem with a specific participation matrix derived from the choice data. Leveraging this equivalence, the authors analyze Sinkhorn's algorithm, a standard iterative method for matrix balancing. They introduce and utilize concepts from spectral graph theory, specifically algebraic connectivity, to characterize the global linear convergence rate of Sinkhorn's algorithm. They also derive the sharp asymptotic linear convergence rate, generalizing existing results.
Datasets
The paper uses real-world datasets for empirical evaluation:
- NASCAR dataset: Contains k-way rankings from the 2002 NASCAR season.
- SUSHI dataset: Consists of rankings of sushi items.
- Youtube dataset: Features pairwise comparisons of videos, rated for entertainment value.
- GIFGIF dataset: Similar to Youtube, uses pairwise comparisons of GIFs rated for sentiment.
The Youtube and GIFGIF datasets were subsampled due to memory constraints.
Key Insights and Ideas
- Unifying Choice Modeling and Matrix Balancing: The paper reveals that these two seemingly disparate fields are deeply interconnected, allowing for the transfer of tools and insights between them.
- Algebraic Connectivity as a Key to Convergence: The authors demonstrate that the algebraic connectivity of a graph derived from the data is a fundamental factor in quantifying the linear convergence rate of Sinkhorn's algorithm, particularly for sparse matrices.
- Sinkhorn's Algorithm as a General Framework: Many existing algorithms in choice modeling are shown to be special cases or analogs of Sinkhorn's algorithm, highlighting its broad applicability and unifying power.
- Understanding Convergence Regimes: The paper clarifies the conditions under which Sinkhorn's algorithm exhibits linear versus sub-linear convergence, linking these to the existence of direct or limit scalings in the matrix balancing problem.
Key Results
- Global Linear Convergence: The paper establishes the first quantitative global linear convergence bound for Sinkhorn's algorithm on general non-negative matrices, with the rate characterized by the algebraic connectivity of the associated bipartite graph.
- Sharp Asymptotic Rate: A new characterization of the asymptotic linear convergence rate is derived for general non-negative matrices and non-uniform marginals, extending previous work.
- Equivalence of Algorithms: Sinkhorn's algorithm is shown to be equivalent to various algorithms used in choice modeling, including those for pairwise comparisons and ranking data.
- Empirical Performance: Sinkhorn's algorithm consistently outperforms the iterative LSR algorithm in terms of convergence speed on real-world choice datasets, offering advantages in parallelization and robustness.
Limitations and Future Work
- Computational Complexity of Bounds: While theoretical bounds are provided, computing certain constants (like B, the diameter of the normalized sub-level set) can be challenging. Proposition 2 offers an iteration complexity bound that is independent of B, but further improvements in dependence on problem dimension are an open question.
- Extending Connections: The authors suggest future work on reconciling discrete choice models with covariate information and exploring further connections between choice modeling and matrix balancing.
- Regularization Benefits: The paper proposes regularized versions of Sinkhorn's algorithm that guarantee convergence even when standard methods might fail, suggesting their practical utility for real-world, noisy data.
Summary updated