2026-09-08T02:22:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26452 2026-09-05T19:44:11Z ddc:004 open_access

Learning Multinomial Logits in O(n log n) Time Chierichetti, Flavio Giacchini, Mirko Kumar, Ravi Lattanzi, Silvio Panconesi, Alessandro Tani, Erasmo Tomkins, Andrew Multinomial Logits Conditional Samples Discrete Choice Models Recommender Systems A Multinomial Logit (MNL) model is composed of a finite universe of items [n] = {1,…,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 ε of the ground truth? This question is central to MNL learning and has direct implications for modern recommender system interfaces. We provide two algorithms for this task, one with adaptive queries and one with non‑adaptive queries. Each algorithm outputs an MNL M̂ that induces, for each slate S, a distribution M̂_S on S that is within ε total variation distance of the true distribution. Our adaptive algorithm makes O(n/ε³ log n) queries, while our non-adaptive algorithm makes O(n²/ε³ log n log(n/ε)) queries. Both algorithms query only slates of size two and run in time proportional to their query complexity. We complement these upper bounds with lower bounds of Ω(n/ε² log n) for adaptive queries and Ω(n²/ε² log n) for non‑adaptive queries, thus proving that our adaptive algorithm is optimal in its dependence on the support size n, while the non-adaptive one is tight within a log n factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Flavio Chierichetti and Mirko Giacchini and Ravi Kumar and Silvio Lattanzi and Alessandro Panconesi and Erasmo Tani and Andrew Tomkins 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.63 urn:nbn:de:0030-drops-264526 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.63 eng https://creativecommons.org/licenses/by/4.0/legalcode