AI & ML
Learning Multinomial Logits in $O(n \log n)$ time
arXiv stat.ML0 views
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 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).
Source:https://arxiv.org/abs/2601.04423PreviousA Bayesian latent class reinforcement learning framework to capture adaptive, feedback-driven travel behaviourNextOn the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage
Related posts
Trying to get our Arms around AI efficiency
0Stack Overflow Blog
Why an Embedded Game Fails on Some Phones, and How to Debug It
0dev.to
Microsoft 365 vs Office 2024: The Break-Even Math
0dev.to
Master AI Evals: Build Reliable, Scalable Model Evaluation Pipelines
0dev.to
What to give someone who misses a place
0dev.to
Google is pushing OEMs against GrapheneOS and bootloader unlocking
0Hacker News