← 研踪 PaperTrailarXiv: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
摘要
A Multinomial Logit (MNL) model is composed of a finite universe of items , 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 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 queries and learns every choice distribution in total variation distance . We also provide a second adaptive algorithm that with queries provides a stronger guarantee: each choice distribution is approximated to a multiplicative error (except for subsets of mass smaller than ). We complement these algorithms with lower bounds of for total variation distance and for the multiplicative error guarantee, showing the optimality of our adaptive algorithms. Our non-adaptive algorithm makes queries to obtain guarantees under the multiplicative error notion. We complement this result with an lower bound for any non-adaptive algorithm, showing that our algorithm is almost tight in (within a 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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 , 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 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 queries and learns every choice distribution in total variation distance . We also provide a second adaptive algorithm that with queries provides a stronger guarantee: each choice distribution is approximated to a multiplicative error (except for subsets of mass smaller than ). We complement these algorithms with lower bounds of for total variation distance and for the multiplicative error guarantee, showing the optimality of our adaptive algorithms. Our non-adaptive algorithm makes queries to obtain guarantees under the multiplicative error notion. We complement this result with an lower bound for any non-adaptive algorithm, showing that our algorithm is almost tight in (within a factor).
查看此版本解读 →查看此版本原文 ↗