# Learning to Re-rank with Constrained Meta-Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 62 references that are in the map.
- First posted on arXiv 29 Apr 2023.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [FA*IR: A Fair Top-k Ranking Algorithm](https://mlsanity.com/paper/1706.06368/) (2017)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (2019)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [Designing Fair Ranking Schemes](https://mlsanity.com/paper/1712.09752/) (2017)
- [Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness](https://mlsanity.com/paper/2105.00855/) (2021)
- [Reducing Disparate Exposure in Ranking: A Learning To Rank Approach](https://mlsanity.com/paper/1805.08716/) (2018)
- [Fairness in Information Access Systems](https://mlsanity.com/paper/2105.05779/) (2021)
- [Meta Optimal Transport](https://mlsanity.com/paper/2206.05262/) (2022)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets](https://mlsanity.com/paper/2010.01470/) (2020)
- [Context-Aware Learning to Rank with Self-Attention](https://mlsanity.com/paper/2005.10084/) (2020)
- [Joint Multisided Exposure Fairness for Recommendation](https://mlsanity.com/paper/2205.00048/) (2022)
- [End-to-end Learning for Fair Ranking Systems](https://mlsanity.com/paper/2111.10723/) (2021)
- [Policy-Gradient Training of Fair and Unbiased Ranking Functions](https://mlsanity.com/paper/1911.08054/) (2019)
- [Optimizing generalized Gini indices for fairness in rankings](https://mlsanity.com/paper/2204.06521/) (2022)
- [Optimizing Rankings for Recommendation in Matching Markets](https://mlsanity.com/paper/2106.01941/) (2021)
- [Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings](https://mlsanity.com/paper/2202.03237/) (2022)
- [Fairness of Exposure in Light of Incomplete Exposure Estimation](https://mlsanity.com/paper/2205.12901/) (2022)

## Abstract (arXiv)

Many re-ranking strategies in search systems rely on stochastic ranking policies, encoded as Doubly-Stochastic (DS) matrices, that satisfy desired ranking constraints in expectation, e.g., Fairness of Exposure (FOE). These strategies are generally two-stage pipelines: i) an offline re-ranking policy construction step and ii) an online sampling of rankings step. Building a re-ranking policy requires repeatedly solving a constrained optimization problem, one for each issued query. Thus, it is necessary to recompute the optimization procedure for any new/unseen query. Regarding sampling, the Birkhoff-von-Neumann decomposition (BvND) is the favored approach to draw rankings from any DS-based policy. However, the BvND is too costly to compute online. Hence, the BvND as a sampling solution is memory-consuming as it can grow as gO(N, n2) for N queries and n documents. This paper offers a novel, fast, lightweight way to predict fair stochastic re-ranking policies: Constrained Meta-Optimal Transport (CoMOT). This method fits a neural network shared across queries like a learning-to-rank system. We also introduce Gumbel-Matching Sampling (GumMS), an online sampling approach from DS-based policies. Our proposed pipeline, CoMOT + GumMS, only needs to store the parameters of a single model, and it generalizes to unseen queries. We empirically evaluated our pipeline on the TREC 2019 and 2020 datasets under FOE constraints. Our experiments show that CoMOT rapidly predicts fair re-ranking policies on held-out data, with a speed-up proportional to the average number of documents per query. It also displays fairness and ranking performance similar to the original optimization-based policy. Furthermore, we empirically validate the effectiveness of GumMS to approximate DS-based policies in expectation.