Summary
arXiv:2601.04423v2 Announce Type: replace-cross Abstract: A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=\{1,\dots,n\}$, each assigned a positive weight. A query specifies an admissible subset---called a slate---and the model chooses one item from that slate with probability proportional to its weight. This query model is also known as the Plackett--Luce model or conditional sampling oracle in the literature. Although MNLs have been studied extensively, a basic computational question remains open: given query access to slates, how efficiently can we learn weights so that, for every slate, the induced choice distribution is within total variation distance $\varepsilon$ of the ground truth? This question is central to MNL learning and has direct implications for modern recommender system interfaces. We provide both adaptive and non-adaptive algorithms for this task. Our first adaptive algorithm makes $O(\frac{n\log n}{\varepsilon^2})$ queries and learns ev…
Original text(via arXiv stat.ML)
Computer Science > Data Structures and Algorithms
Title:Learning Multinomial Logits in $O(n \log n)$ time
Abstract:A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=\{1,\dots,n\}$, each assigned a positive weight. A query specifies an admissible subset---called a slate---and the model chooses one item from that slate with probability proportional to its weight. This query model is also known as the Plackett--Luce model or conditional sampling oracle in the literature. Although MNLs have been studied extensively, a basic computational question remains open: given query access to slates, how efficiently can we learn weights so that, for every slate, the induced choice distribution is within total variation distance $\varepsilon$ of the ground truth? This question is central to MNL learning and has direct implications for modern recommender system interfaces. We provide both adaptive and non-adaptive algorithms for this task. Our first adaptive algorithm makes $O(\frac{n\log n}{\varepsilon^2})$ queries and learns every choice distribution in total variation distance $\varepsilon$. We also provide a second adaptive algorithm that with $O(\frac{n \log n}{\varepsilon^3})$ queries provides a stronger guarantee: each choice distribution is approximated to a multiplicative $1\pm\varepsilon$ error (except for subsets of mass smaller than $\varepsilon$). We complement these algorithms with lower bounds of $\Omega(\frac{n\log n}{\varepsilon^2})$ for total variation distance and $\Omega(\frac{n \log n}{\varepsilon^3})$ for the multiplicative error guarantee, showing the optimality of our adaptive algorithms. Our non-adaptive algorithm makes $O\left(\frac{n^{2}}{\varepsilon^{3}}\log n \log\frac{n}{\varepsilon}\right)$ queries to obtain guarantees under the multiplicative error notion. We complement this result with an $\Omega(\frac{n^2 \log n}{\varepsilon^2})$ lower bound for any non-adaptive algorithm, showing that our algorithm is almost tight in $n$ (within a $\log n$ factor).
| Comments: | We prove two new results. In particular, we provide a $O(n \log n / \varepsilon^2)$ algorithm for learning in $d_1$ error, which closes one of the main questions left open in the previous versions of the paper |
|---|
| Subjects: | Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML) |
| Cite as: | arXiv:2601.04423 [cs.DS] |
| (or arXiv:2601.04423v2 [cs.DS] for this version) |
| https://doi.org/10.48550/arXiv.2601.04423 arXiv-issued DOI via DataCite |
| Journal reference: | ICALP 2026 |
Submission history
The text above was extracted automatically from the source page and may miss images, tables or code blocks. The original is authoritative.
Published by arXiv stat.ML
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗