跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2601.04423 · v2

Learning Multinomial Logits in $O(n \log n)$ time

首次提交 2026-01-08 06:07
版本更新 2026-11-19 22:59
雷达观测 2026-11-20 14:52
arXiv ↗PDF ↗

摘要

A Multinomial Logit (MNL) model is composed of a finite universe of items [n]={1,…,n}[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(nlog⁡nε2)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(nlog⁡nε3)O(\frac{n \log n}{\varepsilon^3}) queries provides a stronger guarantee: each choice distribution is approximated to a multiplicative 1±ε1\pm\varepsilon error (except for subsets of mass smaller than ε\varepsilon). We complement these algorithms with lower bounds of Ω(nlog⁡nε2)Ω(\frac{n\log n}{\varepsilon^2}) for total variation distance and Ω(nlog⁡nε3)Ω(\frac{n \log n}{\varepsilon^3}) for the multiplicative error guarantee, showing the optimality of our adaptive algorithms. Our non-adaptive algorithm makes O(n2ε3log⁡nlog⁡nε)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 Ω(n2log⁡nε2)Ω(\frac{n^2 \log n}{\varepsilon^2}) lower bound for any non-adaptive algorithm, showing that our algorithm is almost tight in nn (within a log⁡n\log n factor).

作者备注: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

期刊信息:ICALP 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-19 22:59 · 最新观测版本

Learning Multinomial Logits in $O(n \log n)$ time

A Multinomial Logit (MNL) model is composed of a finite universe of items [n]={1,…,n}[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(nlog⁡nε2)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(nlog⁡nε3)O(\frac{n \log n}{\varepsilon^3}) queries provides a stronger guarantee: each choice distribution is approximated to a multiplicative 1±ε1\pm\varepsilon error (except for subsets of mass smaller than ε\varepsilon). We complement these algorithms with lower bounds of Ω(nlog⁡nε2)Ω(\frac{n\log n}{\varepsilon^2}) for total variation distance and Ω(nlog⁡nε3)Ω(\frac{n \log n}{\varepsilon^3}) for the multiplicative error guarantee, showing the optimality of our adaptive algorithms. Our non-adaptive algorithm makes O(n2ε3log⁡nlog⁡nε)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 Ω(n2log⁡nε2)Ω(\frac{n^2 \log n}{\varepsilon^2}) lower bound for any non-adaptive algorithm, showing that our algorithm is almost tight in nn (within a log⁡n\log n factor).

查看此版本解读 →查看此版本原文 ↗