Tight Bounds for Learning RUMs from Small Slates

Authors: flavio  chierichetti
mirko  giacchini
ravi  kumar
alessandro  panconesi
andrew  tomkins
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 16:52:22

Abstract: A Random Utility Model (RUM) is a classical model of user behavior defined by a distribution over $\mathbb{R}^n$. A user, presented with a subset of $\\{1,\ldots,n\\}$, will select the item of the subset with the highest utility, according to a utility vector drawn from the specified distribution. In practical settings, the subset is often of small size, as in the ``ten blue links'' of web search. 


In this paper, we consider a learning setting with complete information on user choices from subsets of size at most $k$. We show that $k=\Theta(\sqrt{n})$ is both necessary and sufficient to predict the distribution of all user choices with an arbitrarily small, constant error.


Based on the upper bound, we obtain new algorithms for approximate RUM learning and variations thereof. Furthermore, we employ our lower bound for approximate RUM learning to derive lower bounds to fractional extensions of the well-studied $k$-deck and trace reconstruction problems.

Main paper: 
 introduction: 
 In many common settings, both online and offline, users select from a set of available candidates: cars on a dealer's lot; songs on a streaming service; movies in a Netflix carousel of choices; and so forth. Often, it is unrealistic to offer the user the entire universe of items. No car dealership has every new and used car ever produced. Likewise, recommendation services have enormous catalogs of songs, products, movies, etc, and must carefully curate a more manageable subset of recommended items that will fit within the constraints of the user interface. Thus, user feedback often arrives as a choice from slates of items of a certain standard cardinality-think of "ten blue links" in web search as the classical example.Random Utility Models (commonly called RUMs) have been the standard mathematical model for studying user choices over subsets of a universe of items. RUMs are the subject of many decades of study, and the centerpiece of the 2000 Nobel prize in economics. The model family is straightforward: a RUM operates over a universe U of items, with |U | = n, and is characterized by a distribution over R n . A user draws from this distribution to generate a vector specifying the utility of each item of U . The user is offered a subset of U called a slate, and must select a single item from the slate; the user behaves rationally by selecting the available item of the highest utility. The winning distribution of the slate is a probability distribution over the items of the slate representing the likelihood (over draws from the utility distribution) that a particular item is selected. To learn a RUM, an algorithm is given a training set of examples of slates with their winning distributions, and must then guess the winning distributions of a new test set of slates.We are interested in learning RUMs when the example slates in the training set are constrained to have at most a certain cardinality. We will then deem an algorithm successful if exposure to these smaller slates allows it to approximate the winning distribution of all slates. In the extreme example, the algorithm should infer the winning distribution over the universal slate U itself, representing the likelihood that a particular item is a random user's favorite from the entire catalog.Our contributions. We present two main results representing paired upper and lower bounds for this question. The upper bound shows that, with knowledge of the winning distributions for slates of size at most O( √ n), one can approximate the winning probability for any item in any slate to within an arbitrarily small additive constant. Using this upper bound, we obtain an exponential improvement in the time to learn a RUM. The previous best-known algorithm, implicit in earlier work, requires time 2 O(n) . Our new algorithm learns any RUM to within an ℓ ∞ -error (resp., ℓ 1 -error) of ϵ > 0 in time nO √ n log 1 ϵ (resp., n O( √ n log n ϵ )). We also give a "simulation" result: the winning distribution of each slate T can be approximated within a constant ℓ ∞ -error by querying polynomially many sub-slates of T , each of size at most O |T | log |T | . Our near-matching lower bound shows that, with knowledge of the winning distributions for all slates up to size o( √ n), any algorithm must make error 1/2 -ϵ (almost the worst possible) in predicting a target item's probability in the universal slate, for arbitrarily small constant ϵ. Based on this lower bound, we also obtain lower bounds to fractional extensions of the well-studied k-deck and trace reconstruction problems.The bounds for RUM learning algorithms depend on the nature of the oracle used to present examples to the algorithm. For a given slate, the MAX-DIST oracle returns the exact winning distribution, while the MAX-SAMPLE oracle simply returns a draw from the winning distribution, as we would expect from a real-world setting. The algorithms we present work with both oracles, with asymptotically the same running time and the same sample complexity.Overview of techniques. Our results are proved by observing a series of connections between RUM learning and the approximation of the bitwise AND function via polynomials. Specifically, the two main quantities of interest in approximating Boolean functions with polynomials are (i) the degree of the polynomial, and (ii) the ℓ 1 -norm of the coefficients of the polynomial. We will show that these two quantities are related, respectively, to (i) the size of the slates required to approximate a RUM (Theorem 9 and Theorem 12), and (ii) the running time to approximate the winning distribution of a queried slate (Theorem 9 and Corollary 10).Related work. Discrete choice has been the subject of extensive research in machine learning and economics; see [Train, 2003] for an excellent introduction. RUMs are an important class of models in discrete choice-in particular, Multinomial Logits (MNLs) and their mixtures are special classes of RUMs. RUMs have been extensively studied from both active and passive learning perspectives [Soufiani et al., 2012 , Oh and Shah, 2014 , Chierichetti et al., 2018a ,b, Negahban et al., 2018 , Tang, 2020] and from an efficient representation point of view [Farias et al., 2009 , Chierichetti et al., 2021] .A number of papers have used linear programming (LP) for obtaining representation of RUMs that agree with an empirical distribution on small slates [Farias et al., 2009 , Almanza et al., 2022 , Chierichetti et al., 2023] . In particular, Farias et al. [2009] make strong assumptions on the underlying RUM, while in [Almanza et al., 2022 , Chierichetti et al., 2023] the algorithms are not required to generalize outside of the observed training set. Instead, we are asking what is the minimum k such that if one observes all the winning distributions of slates of size up to k, one can approximately reconstruct all the winning distributions of a RUM? Note that we do not make any assumption on the RUM and our algorithms must generalize to all the slates. The approximation of Boolean functions via polynomials has found applications in a disparate and apparently remote number of fields such as cryptography [Bogdanov et al., 2016] , differential privacy [Thaler et al., 2012] , quantum query complexity [Beals et al., 2001] , PAC learning [Klivans and Servedio, 2004] , and more. Our work draws connections between this field and RUM learning for the first time, showing yet another important application of such techniques.In this paper we also strengthen the relation, that was first observed in [Chierichetti et al., 2018a] , between RUM learning and the k-deck problem.Organization. In Section 2 we introduce the definitions and notation. In Section 3 we prove our upper bound, which we then use in Section 4 to obtain algorithms for learning RUMs. In Section 5, we present our lower bound. Finally, in Sections 6 and 7 we derive, as corollaries of our results, lower bounds for other learning problems. All the proofs missing from the main body of the paper can be found in Appendix A. A slate is a non-empty subset of [n] . For a slate ∅ ̸ = S ⊆ [n] and a permutation π ∈ S n , let π(S) be the item of S that wins, i.e., ranks the highest in π.The following definition of RUMs, based on probability distributions over permutations, is equivalent to the utility-vectors definition given in the Introduction [Chierichetti et al., 2018a] ; we adopt the distribution-over-permutations definition, since it makes it easier to present our algorithms.Definition 1 (Random Utility Model (RUM)). A random utility model (RUM) R on [n] is a distribution on S n . For a slate S, R S denotes the distribution of the random variable π(S) where π ∼ R, so R S (s) = Pr[s wins in S] is called the winning distribution on S induced by RUM R.We consider two types of oracle access to the RUM: the MAX-DIST oracle returns for a given slate the (exact) winning distribution for the slate and the MAX-SAMPLE oracle returns a draw from the winning distribution.x = x 1 . . . x n ∈ {0, 1} n and S ⊆ [n], let χ S (x) = i∈S x i . By convention, χ ∅ (x) = 1.The function AND n : {0, 1} n → {0, 1} is the bitwise-AND given by AND n (x) = χ [n] (x). We write only AND when n is clear from the context. A polynomial p : {0, 1} n → R is said to ϵ-approximate the AND function if for all x ∈ {0, 1} n it holds |AND(x) -p(x)| ≤ ϵ. The ϵ-approximate degree of AND is the smallest value deg ϵ (AND) such that there exists a polynomial of such degree that ϵ-approximates the AND function, and it is well known that the optimal value is deg ϵ (AND) = Θ( n log(1/ϵ)) [Bun and Thaler, 2022] . The general form of a degree-k polynomial is S⊆[n],|S|≤k a S • χ S (x), where the {a S } S⊆[n],|S|≤k are real coefficients. However, all the polynomials proposed in the literature have at most k + 1 distinct coefficients a 0 , a 1 , . . . , a k , such that a S = a |S| , therefore in this work we will focus only on polynomials of such form.1 While it is folklore that such coefficients can be computed in polynomial time, for completeness we provide in Appendix D an explicit algorithm for this task. We will use several results on the approximation of the AND function that we introduce as needed. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: section 4 and section 8 highlight the limitations of the algorithms. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
uniform approximation of a rum: 
 In this section we show that if two RUMs agree on small slates, then they nearly agree on all slates. Our result can be obtained as a consequence of a more general result of Sherstov [2008] , which is based on the approximate degree of the AND function and was originally stated only for sub-constant errors. The following is a restatement of Sherstov [2008, Theorem 4.8] , using the upper bound on the approximate degree of AND proved by [Buhrman et al., 1999] ; we also make the error term explicit.Theorem 2 (Sherstov [2008] ). There exists a constant c > 0 such that the following holds. Consider any two probability spaces P 1 and P 2 , and any events A 1 , . . . , A n in P 1 and B 1 , . . . , B n in P 2 such that, for any S ⊆[n], |S| ≤ c • n • ln 1/ϵ, it holds Pr P1 [∩ i∈S A i ] = Pr P2 [∩ i∈S B i ]. Then, it holds: Pr P1 ∩ i∈[n] A i -Pr P2 ∩ i∈[n] B i ≤ ϵ, where ϵ ∈ (2 -n , 1/3)Theorem 3 (RUMs Upper Bound). Let P and Q be two RUMs on [n] . There exists a constant c > 0 such that for a given s ∈[n], T ⊆ [n] ∖ {s}, if P S∪{s} (s) = Q S∪{s} (s) for each S ∈ T ′ | T ′ ⊆ T and |T ′ | ≤ c • |T | • ln 1 ϵ , then P T ∪{s} (s) -Q T ∪{s} (s) ≤ ϵ, where ϵ ∈ (2 -|T | , 1/3).Proof. Let c be the constant of Theorem 2 and define k = c • |T | • ln 1/ϵ. Consider the probability space P 1 (resp. P 2 ) having S n as sample space and RUM P (resp. Q) as the probability mass function. For t ∈ T , let A t be the event {π ∈ S n | s > π t}. Then, for any S ⊆ T , {π ∈ S n | π(S ∪ {s}) = s} = ∩ i∈S A i . Therefore, for any S ⊆ T , |S| ≤ k it holds:Pr P1 [∩ i∈S A i ] = Pr π∼P [π(S ∪ {s}) = s] = P S∪{s} (s) = Q S∪{s} (s) = Pr P2 [∩ i∈S A i ] ,where the third equality follows by hypothesis. Finally, by Theorem 2:P T ∪{s} (s) -Q T ∪{s} (s) = Pr P1 [∩ i∈T A i ] -Pr P2 [∩ i∈T A i ] ≤ ϵ.In light of Theorem 3, accessing slates of size up to O n • ln 1 ϵ is enough to predict the winning distribution of all the slates, within an additive ϵ. In the next section, we obtain a computational version of this result.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) Justification: the paper conforms with the NeurIPS Code of Ethics Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
reconstruction algorithms: 
 In this section we obtain two algorithms for reconstructing the winning distributions on large slates using the winning distribution on small slates. The goal of these algorithms is to obtain a computational version of Theorem 3. The first algorithm is a proper learning algorithm that outputs a RUM. Building the RUM takes time n O(n) but once built, querying this RUM to get the approximate winning distribution of any given slate takes only polynomial time. Moreover, using previous work [Chierichetti et al., 2021] , this RUM can actually be approximately represented using O(n 2 log n) bits. The second algorithm is an improper learning algorithm: while its output model allows uniformly approximating the winning distribution on each slate, this model might not be a RUM. Building the model takes time n O( √ n) and once built, querying this model to get the approximate winning distribution of any given slate takes time 2 O( n) . The total bit complexity of the second algorithm's model is n O( n) . This second algorithm has two nice properties: (i) if we are given access to slates larger than √ n, then querying the model becomes more efficient, and (ii) if we want to estimate the winning distribution of only M = poly(n) pre-determined slates, then building the model becomes more efficient. Putting these two properties together we are able to prove a "simulation" result: for any pre-determined slate EQUATION(i) -Q S (i)| ≤ ϵ.Using the result in [Chierichetti et al., 2021] , the RUM P can be subsampled in poly(n) time to a uniform RUM P with a multiset of O n/ϵ2 permutations as its support, and such that for (n) such that (i) P can be represented with O ϵ -2 • n 2 log n bits, and (ii) when P is queried on a slate S, it can return in poly(n) time adistribution P S such that P S -Q S ∞ ≤ ϵ (resp., P S -Q S 1 ≤ ϵ).By providing a version of Theorem 3 that holds when the small slates are approximately equal, this algorithm can also be made to work with MAX-SAMPLE oracle. More details are given in Appendix B.We mention that this algorithm can be made to run in time 2 O(n) by using the ellipsoid method and the separation oracle of Chierichetti et al. [2023] ; more details are given in Appendix C.In this section we obtain a learning algorithm whose data structure is not a RUM but can be built faster. As before, this is a restatement of Sherstov [2008, Theorem 4.8 ]: Theorem 6 (Sherstov [2008] ). Consider any probability space P, and any events A 1 , . . . , A n in P.For k ≥ Θ n • ln 1/ϵ , ϵ ∈ (2 -n , 1/3), let {a i } 0≤i≤k be the coefficients of a degree k polynomial approximating the AND function within ϵ (for any S ⊆[n], |S| ≤ k, the coefficient of the monomial χ S (x) is a |S| ). Then, Pr P ∩ i∈[n] A i -S⊆[n],|S|≤k a |S| • Pr P [∩ i∈S A i ] ≤ ϵ Given a RUM R over [n] and access to slates of size k ≥ Θ |T | log 1 ϵ , consider an element s ∈ [n] and a slate T ⊆ [n] ∖ {s}.Let {a i } 0≤i≤k-1 be the coefficients of a polynomial of degree k -1 that approximates the AND |T | function. Then, the following is a good approximation for R T ∪{s} (s):R T ∪{s} (s) = S⊆T,|S|≤k-1 a |S| • R S∪{s} (s).In fact, choosing the probability space and events as in Theorem 3 and applying Theorem 6, we get:Observation 7. R T ∪{s} (s) -R T ∪{s} (s) ≤ ϵ, where R is a RUM over [n], s ∈ [n], T ⊆ [n] ∖ {s}, and for k ≥ Θ |T | ln 1 ϵ , {a i } 0≤i≤k-1 are the coefficients of a polynomial of degree k -1 approximating the AND |T | function (the coefficient of the monomial χ S (x) is a |S| ).From the above observation and given MAX-DIST oracle access to slates of size k = Θ( n ln(1/ϵ)), we obtain a deterministic algorithm that first stores R S (s) for all s ∈ S ⊆ [n], |S| ≤ k, in time n O(k) and then, upon query (s, T ) returns the approximation R T ∪{s} (s) that can be computed in|T | O( √ |T | ln(1/ϵ)) ≤ n O(k) time 2 .Note that this result holds for any polynomial approximating the AND function. To get a better algorithm, which also works with MAX-SAMPLE oracle, we focus on a specific polynomial. (Observe also that the time to answer a query in the previous algorithm does not improve as k increases. This is counter-intuitive: given access to larger slates, it should become easier to approximate the target slate. The second algorithm that we provide gets faster as k increases, overcoming this limitation.)The polynomial that we use is the one proposed by Huang and Viola [2022, Corollary 1.5 ]:Theorem 8 (Huang and Viola [2022] ). For all ϵ ∈ (2 -n , 1/3), n ln(1/ϵ) ≤ d ≤ n, there exists a polynomial p : {0, 1} n → R of degree k = Θ(d) and real coefficients {a i } 0≤i≤k , where the coefficient of χ S (x) is a |S| , such that: (i) for each x ∈ {0, 1} n , |p(x) -AND n (x)| ≤ ϵ, and (ii)S⊆[n],|S|≤k |a |S| | = k c=0 n c |a c | ≤ 2 O( n ln(1/ϵ) k ) .Theorem 9 (Improper learning algorithm). Let R be a RUM over[n]. Let d ≥ n ln(1/ϵ), ϵ ∈ (0, 1/3), and δ ∈ (0, 1) such that ϵ, δ ≥ 1 n O(1). Then, there exists a randomized algorithm that accesses slates of size at most k = Θ(d) and such that:(i) it first makes n O(k) queries to MAX-SAMPLE oracle (or MAX-DIST oracle) and then, (ii) for any query s ∈ [n], T ⊆ [n] ∖ {s}, it returns, in time 2 O( |T | ln(1/ϵ) k ) • poly(|T |) and with probability at least 1 -δ, an estimate RT ∪{s} (s) such that | RT ∪{s} (s) -R T ∪{s} (s)| ≤ ϵ.For k = Θ( n ln(1/ϵ)), Theorem 9 gives an algorithm with a pre-processing time of n O(k) and that can answer any query k) . Note that the query-time of this algorithm gets better increasing k (although the pre-processing time gets worse since more slates must be queried).(s, T ) in time 2 O(|T | ln(1/ϵ)/k) |T | O(1) ≤ 2 O( √ |T | ln(1/ϵ)) ≤ 2 O(The pre-processing time of the improper learning algorithm increases with the slate size because the algorithm must be able to reply to every query after the pre-processing phase. Suppose, however, that the algorithm knows in advance which slates will be queried; in that case, it can perform the pre-processing phase to satisfy only such requests. In this setting where the queries are known offline (or where the oracles can be called lazily), we can get a faster algorithm. Corollary 10 (Simulation algorithm). Let R be a RUM over We can also interpret this algorithm in the more general setting of Sherstov [2008] . In such setting, Corollary 10 implies that, for any n events in a probability space, the probability of the intersection of all the events can be well-approximated by a linear combination of polynomially many probabilities of smaller intersections (specifically, each intersection is over at most O(n/ ln n) events).Our construction actually shows that, in this o( √ n)-slates setting, it is impossible to approximate the distribution of the full slate even within a constant ℓ ∞ -error. Specifically, for any constant ϵ > 0, it is not possible to learn whether a special item, n, has probability at least 1 -ϵ or at most ϵ in the full slate by accessing only slates of size o( √ n).We will make use of the following result, which is a consequence of the method of dual polynomials (see, e.g., [Bun and Thaler, 2022, Chapter 6] ), and was first proved for cryptographic applications in [Bogdanov et al., 2016, Theorem 1] . While the original result considers general Boolean functions, we state it only for the AND function, plugging in the lower bound on the ϵ-approximate degree of the AND proved in [Bun and Thaler, 2015, Proposition 14] .Theorem 11 (Bogdanov et al. [2016] ). For a sufficiently large n and constant ϵ ∈ (0, 1), there exists a constant c > 0 and two probability distributions µ, ψ over {0, 1} n such that: (i) for each polynomial p :{0, 1} n → R of degree at most c • √ n • ϵ, E x∼µ [p(x)] = E x∼ψ [p(x)], and (ii) |E x∼µ [AND(x)] -E x∼ψ [AND(x)]| > 1 -ϵWe are now ready to prove our lower bound for RUMs. Theorem 12 (RUMs Lower Bound). For a sufficiently large n and for constant ϵ ∈ (0, 1), there exists a constant c > 0 and two RUMs A, B on [n] such that:(i) for each S ⊆ [n] such that |S| ≤ c • (n -1) • ϵ = Θ( √ n), it holds A S = B S , and (ii) |A [n] (n) -B [n] (n)| > 1 -ϵProof. Consider the distributions µ, ψ over {0, 1} n-1 from Theorem 11, and letk = c • (n -1) • ϵ. We build RUM A on [n] as follows: sample x ∈ {0, 1} n-1 according to µ, then, let S x = {i ∈ [n -1] | x i = 1}and sample a uniform at random permutation among those where the set of elements ranked lower than n is S x . RUM B is defined similarly, but x is sampled from ψ. Note that forS ⊆ [n -1], A S∪{n} (n) = E x∼µ [χ S (x)],and similarly for B. Then, from property (ii) of Theorem 11 we have:|A [n] (n) -B [n] (n)| = E x∼µ [AND n-1 (x)] -E x∼ψ [AND n-1 (x)] > 1 -ϵ.Moreover, fix any S ⊆ [n -1], |S| ≤ k. We have:A S∪{n} (n) = E x∼µ [χ S (x)] = E x∼ψ [χ S (x)] = B S∪{n} (n),where the second equality follows by Theorem 11(ii) and since χ S (x) = i∈S x i is a polynomial of degree |S| ≤ k.It remains to show that the winning distributions for the elements different from n in the small slates also coincide. We show that for RUMs A and B, these probability distributions can be expressed in terms of winning distributions of n; below, we do the calculations only for A, the calculations for B are analogous.Let Π x be the uniform distribution over the set of permutations where the set of elements ranked lower than n is S x , for a string x ∈ {0, 1} n-1 . For convenience, for x ∈ {0, 1} n-1 , we setx n = 1. Choose any i ∈ S ⊆ [n], i ̸ = n, |S| ≤ k, then: A S (i) = Pr π∼A [π(S) = i] = T ⊆S Pr x∼µ,π∼Πx χ T (x) s∈S∖T (1 -x s ) = 1 ∩ π(S) = i = T ⊆S Pr x∼µ χ T (x) s∈S∖T (1 -x s ) = 1 Pr x∼µ,π∼Πx π(S) = i χ T (x) s∈S∖T (1 -x s ) = 1 .Here, the third equality follows by the law of total probabilities, partitioning on the possible values of bits {x i } i∈S . Since it always holds x n = 1, we assume without loss of generality that either n ∈ T or n / ∈ S. Given that Π x is uniform, we have:Pr x∼µ,π∼Πx π(S) = i χ T (x) s∈S∖T (1 -x s ) = 1 =          1 |T | if i ∈ T and |S ∖ T | = 0 and n / ∈ S 0 if i ∈ T and n ∈ T 0 if i ∈ T and |S ∖ T | > 0 1 |S∖T | if i ∈ S ∖ TTherefore, thanks to the conditioning, this first probability does not depend on A (the probability is the same if we sample x from ψ and then π from Π x ). Moreover:Pr x∼µ χ T (x) s∈S∖T (1 -x s ) = 1 = E x∼µ χ T (x) s∈S∖T (1 -x s ) = E x∼µ   P ⊆S∖T (-1) |P | • χ T ∪P (x)   = P ⊆S∖T (-1) |P | • A T ∪P ∪{n} (n). Since A T ∪P ∪{n} (n) = B T ∪P ∪{n} (n), we have A S (i) = B S (i) for any i ∈ S ⊆ [n], |S| ≤ k. 
lower bound when only slates of size k are given: 
 We know that accessing slates of size 2, . . . , k = Θ( √ n) is sufficient to approximate the full slate. It is natural to wonder if the slates smaller than k are needed, or if those of size exactly k are enough. A simple observation shows that accessing smaller slates is necessary. Observation 13. For any k ≤ n, there exists a RUM R on [n] such that: (i) R S (s) = 1/k for all s ∈ S ∈ [n] k , and (ii)R [n] (i) = 1/k for all i ∈ [k]Proof. Consider the RUM R that first samples a uniform at random element i ∈ [k], this element is placed at the top of the permutation, followed by elements [n] ∖ [k] permuted uniformly at random, and finally by the elements [k] ∖ {i} permuted uniformly at random. Consider any s ∈ S ∈[n] k . If s ∈ [k], then R S (s) = 1/k. If instead s ∈ [n] ∖ [k], let α = |S ∩ [k]| < k, we have, R S (s) = (1 -α/k) • 1/(k -α) = 1/k. Moreover, for any i ∈ [k], by construction, R [n] (i) = 1/k.Consider k = ϵ • n, for any ϵ ∈ (0, 1), and let R be the RUM of the previous construction. Consider now RUM Q that samples a uniform at random permutation over[n]. Clearly, R and Q coincide on slates of size k, but for all i ∈ [k], R [n] (i) = 1/k and Q [n] (i) = 1/n, and in particular the ℓ 1 -distance between R [n] and Q [n] is k • (1/k -1/n) + (n -k)/n = 2 -2ϵ.Therefore, any algorithm accessing only slates of size k = O(ϵ • n) will incur an ℓ 1 -error of 1 -ϵ on the full slate. By selecting k = O(n c ), for any c ∈ (0, 1), we have that any algorithm must incur an ℓ 1 -error of 1 -n c-1 (and also an ℓ ∞ -error of Ω( 1 n c )) on the full slate. On the other hand, accessing all the slates of size O √ n log n and smaller, one can obtain an ℓ 1 -error as small as 1/n d for any constant d > 0. Therefore, accessing smaller slates is necessary. 
fractional k-deck: 
 The k-deck problem [Kalashnik, 1973] is a well-studied problem at the intersection of combinatorics and computer science. Given a string s ∈ {0, 1} n and a set I = {i 1 , . . . , i k } ∈ [n] k , with i 1 < • • • < i k , the projection of s to I, denoted as s I , is the strings I = s i1 . . . s i k . The k-deck of s is the multiset D k (s) = s I | ∀I ∈ [n] k .The k-deck problem asks what is the smallest k = k(n) such that any n-bit string can be reconstructed from its k-deck? This problem has a long history. Manvel et al. [1991] originally showed that reconstruction is possible with k = n 2 ; they also showed that it is not possible with k = Θ(log n). Later, it was shown in [Krasikov and Roditty, 1997] (see also [Scott, 1997] ) that reconstruction is always possible with k = O( √ n); it is widely conjectured that this bound is tight. The best known lower bound, however, is no better than subpolynomial: in [Dudík and Schulman, 2003] it is shown that k = e Θ( √ log n) is insufficient for reconstruction. In [Chierichetti et al., 2018a] , lower bounds for the k-deck problem were used to obtain lower bounds on the maximum size of slates required for reconstructing a RUM.In this section we define a fractional version of the k-deck problem and show a reconstruction lower bound. Note that the k-deck of a string s is a function f s : {0, 1} k → Z ≥0 , where f s (s ′ ) is the multiplicity of s ′ in D k (s). Now, given a probability distribution P over n-bit strings, the fractional k-deck of P is a function fP : {0, 1} k → R ≥0 , where f P (s ′ ) = E s∼P [f s (s ′ )]. Also, for a distribution P over n-bit strings, we define its ith marginal to be the probability that the ith bit of a string sampled from P equals 1. The fractional k-deck problem seeks the minimum k = k(n, ϵ) such that the fractional k-deck of an unknown distribution P over n-bit strings is sufficient to approximate any marginal of P to within an additive ϵ. It is easy to see that the fractional k-deck problem generalizes the k-deck problem (by also setting ϵ < 1/2).Based on our RUM lower bound, we can construct two probability distributions over binary strings giving the same fractional Θ( √ n)-deck, but very different marginals for the first bit, obtaining: Theorem 14. For sufficiently large n, and for each constant ϵ > 0, there exists a constant c > 0 and two distributions X A and X B over n-bits strings of weight 1 that (i) give rise to the same fractional k-deck, for k = ⌊c • √ n⌋, (ii) the marginal of the first bit of X A is ≥ 1 -ϵ, and (iii) the marginal of the first bit of X B is ≤ ϵ. 
fractional trace reconstruction: 
 In the trace reconstruction problem, there is an unknown n-bit string x and a parameter d ∈ (0, 1). A sample is obtained by passing x through a d-deletion channel that erases each bit of x independently with probability d. In this setting, one asks for the minimum number of samples necessary to reconstruct x. Indeed, with probability (1 -d) n , x itself is returned as a sample and hence reconstruction is trivial with Ω ((1 -d) -n ) samples. This problem has been the subject of intense study [Chase, 2021a ,b, De et al., 2017 , Batu et al., 2004 , Holenstein et al., 2008 , Nazarov and Peres, 2017 , Peres and Zhai, 2017 , Viswanathan and Swaminathan, 2008] . It can be solved with e O( 3√ n 1-d ) samples in the so-called high deletion rate setting (1 2 ≤ d ≤ 1 -Ω 1 √ n ), and this bound is tight for a special class of "mean-based" algorithms [De et al., 2017] .In this section we prove an unconditional lower bound for the fractional trace reconstruction problem, which we define similarly to the fractional k-deck problem: given a distribution over the n-bit strings, sample a string from that distribution, pass the string through a d-deletion channel, and return the resulting subsequence as a sample. Note that, each time, a new fresh string is sampled before passing it through the deletion channel. The goal is to reconstruct the marginals of the distribution.Several variants of trace reconstruction have been studied in the literature [Chen et al., 2023 , Davies et al., 2021] . The variant closest to ours is perhaps the average-case trace reconstruction [Peres and Zhai, 2017] . However, average-case trace reconstruction is a computationally easier version of the problem since the single hidden string is sampled from a uniform distribution. Our fractional trace reconstruction is instead a true generalization of trace reconstruction.We will show that fractional trace reconstruction cannot be solved with fewer than e o( √ n) samples. Our lower bound is obtained as a corollary of our result for the fractional k-deck problem. Theorem 15. For each constant ϵ > 0, there exists a constant c > 0 and two distributions X A and X B over n-bits strings of weight n) samples, the probability of correctly distinguishing between X A and X B is at most 1 2 + o(1), (ii) the marginal of the first bit of X A is ≥ 1 -ϵ, and (iii) the marginal of the first bit of X B is < ϵ.1 such that if d = 1 -c 2 √ n + 1 2n , then (i) with fewer than e o((1-d)•n) = e o( √In this very high deletion rate setting (d = 1 -Θ 1 √ n ), the magnitude of our lower bound for fractional trace reconstruction is not larger than that of [De et al., 2017] for trace reconstruction; our lower bound, though, holds for any reconstruction algorithm, not just for mean-based ones. 
conclusions: 
 We considered the problem of learning RUMs looking only at slates of size at most k. We showed that to obtain a constant uniform approximation, k = Θ( √ n) is necessary and sufficient. Moreover, we provided two explicit algorithms that learn a RUM accessing the optimal maximum slate size of Θ( √ n). While optimal with respect to the slate-size, both our algorithms require time exponential in n: we leave open the problem of finding algorithms with better running times. We also provided a third algorithm that can approximate any given slate by accessing only polynomially many subslates of size at most Θ(n/ ln n). In this offline setting, we leave open the problem of decreasing the slate size, while maintaining a polynomial running time.Another interesting research direction would be considering a PAC-learning variant of the problem, where the slates of the testing phase and/or the training phase come from a probability distribution and the goal is to minimize the expected error in the testing phase. This variant might be easier with respect to both slate size and computational complexity. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: there are no foreseeable negative impacts; while on the positive side, the ideas introduced might potentially be used to improve recommender systems.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: the paper does not include experiments and we do not release any data nor model.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: the paper does not include experiments and does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Proof of Theorem 9. Fixed integer d ≥ n ln(1/ϵ), consider the polynomials given by Theorem 8 to approximate AND d , . . . , AND n . These polynomials will have degrees k d , . . . , k n and ℓ 1 -norm of the coefficients W d , . . . , W n . Let k -1 = max{k i } = Θ(d) be the maximum degree of these polynomials and let W = max{W i } ≤ 2 O( n ln(1/ϵ) k ) be the maximum ℓ 1 -norm of the coefficients of these polynomials. Note that these values can be computed in poly(n) time. The algorithm will access slates of size at most k.Let us start by describing the first phase. Using the MAX-DIST oracle, the algorithm simply stores the values {R S (s)} s∈S⊆[n],|S|≤k . Using the MAX-SAMPLE oracle, the algorithm must instead estimate such values. In particular, letH = k • k c=0 n c , α = ⌈max{1, log √ n 1 ϵ , log √ n 2 δ }⌉, and m = ⌈W ⌉ 4 • n 4α + H, note that α = O(1) given that ϵδ ≥ 1/n O(1) , therefore m = n O(k) . Fixed any s ∈ [n], S ⊆ [n] ∖ {s}, |S| ≤ k -1,the algorithm makes m queries to MAX-SAMPLE oracle for the slate S ∪ {s}. Upon such query the oracle samples π ∼ R and returns π(S ∪ {s}), let X i be the indicator variable that is 1 if the ith query returns s and 0 otherwise. Define the random variable R S∪{s} (s) = 1 m i∈[m] X i , and observe that E R S∪{s} (s) = R S∪{s} (s). A standard additive Chernoff bound (see, e.g., [Dubhashi and Panconesi, 2009, Theorem 1.1] ) ensures that:Pr |R S∪{s} (s) -R S∪{s} (s)| ≥ ln m m ≤ 2 m 2 .We repeat this process for each slate of size at most k and, given that m ≥ H, a simple union bound ensures that with probability at least 1 -2/m ≥ 1 -δ it holds that, for each s ∈[n], S ⊆ [n] ∖ {s}, |S| ≤ k -1, we have |R S∪{s} (s) -R S∪{s} (s)| ≤ ln m m ≤ m -1/4. This concludes the first phase of the algorithm, which makes n O(k) queries and is successful with probability 1 -δ. a |S| • R S∪{s} (s).By the triangle inequality and Observation 7, we have:|R T ∪{s} (s) -R T ∪{s} (s)| ≤ |R T ∪{s} (s) -R T ∪{s} (s)| + | R T ∪{s} (s) -R T ∪{s} (s)| ≤ S⊆T,|S|≤k-1 |a |S| | • |R S∪{s} (s) -R S∪{s} (s)| + ϵ ≤ W • m -1/4 + ϵ ≤ 2ϵ.Grouping terms with the same coefficient, we have:R T ∪{s} (s) = k-1 c=0   ac • S∈( T c ) R S∪{s} (s)    = k-1 c=0 a c |T | c E S∼( T c ) R S∪{s} (s) ,where the expectation is over a uniform at random S ∈ T c . To get a faster algorithm, we estimate this expectation via sampling. Pr |M c -E S∼( T c ) R S∪{s} (s) | ≥ ln m m ≤ 2 m 2 .Using that m ≥ |T | ≥ k and by applying a union bound, we obtain that with probability at least1 -2/m ≥ 1 -δ, for each c ∈ {0, 1, . . . , k -1} it holds |M c -E S∼( T c ) R S∪{s} (s) | ≤ ln m m ≤ m -1/4 ≤ W -1 |T | -α. Define finally our estimate for R T ∪{s} (s):RT ∪{s} (s) = k-1 c=0 a c |T | c • M c .With probability at least 1 -δ, we have:RT ∪{s} (s) -R T ∪{s} (s) ≤ k-1 c=0 |a c | |T | c M c -E S∈( T c ) R S∪{s} (s) ≤ W • W -1 • |T | -α ≤ ϵ.Therefore, a triangle inequality implies | RT ∪{s} (s) -R T ∪{s} (s)| ≤ 3ϵ. Since ϵ can be chosen arbitrarily, we can set ϵ := ϵ/3 and obtain the desired approximation guarantee.Finally, note that by Theorem 8,W ≤ 2 O( |T | ln(1/ϵ) k ) , therefore k • m = 2 O( |T | ln(1/ϵ) k ) • poly(|T |), and this is also the running time to answer a query. As a first step to proving a lower bound for the fractional k-deck problem, we show that, for the RUMs of our lower bound construction, the MAX-DIST oracle can be used to reconstruct, for each slate, the distribution over the permutations of the slate induced by the RUM.5 Lemma 16. Consider RUMs A and B over [n] given by Theorem 12. For each slate S, the distribution over the permutations of S induced by RUM A (resp. B) can be obtained from the values{A T ∪{n} (n)} T ⊆S (resp. {B T ∪{n} (n)} T ⊆S ).Proof. Fix any slate S ⊆ [n]. For a permutation π over [n], denote with S π the slate S sorted according to π. Let S be the set of all possible permutations of S. Note that S π ∈ S. We focus on RUM A, the proof is identical for B. We have to prove that for all p ∈ S, Pr π∼A [S π = p] can be written in terms of {A T ∪{n} (n)} T ⊆S . It holds:Pr π∼A [S π = p] = T ⊆S Pr x∼µ,π∼Πx χ T (x) s∈S∖T (1 -x s ) = 1 ∩ S π = p = T ⊆S Pr x∼µ χ T (x) s∈S∖T (1 -x s ) = 1 Pr x∼µ,π∼Πx S π = p χ T (x) s∈S∖T (1 -x s ) = 1 .As proved in Theorem 12, the first probability can be written in terms of {A P ∪{n} (n)} P ⊆S . It is also easy to see that, once the bits {x i } i∈S are fixed, one can write explicitly the probability that S π = p, and that such probability does not depend on RUM A.We can now prove the lower bound for fractional k-deck.Proof of Theorem 14. We use the RUMs A and B from the construction of Theorem 12 to obtain two distributions over n-bit strings of Hamming weight one.Given RUM A (resp., B) we define X A (resp., X B ) to return an n-bit string containing a 1 in position i, and 0's in all the other positions, whenever A (resp., B) returns a permutation where the "special" item n is in position i.Recall that if 0 < ϵ < 1 2 is a constant, Theorem 12 guarantees that for each slateS ⊆ [n] such that |S| ≤ c ϵ • √ n for some c ϵ > 0, it holds A S = B S .As a consequence, Lemma 16 guarantees that RUMs A and B give rise to the same distributions over projected permutations on slates of size at most k = ⌊c ϵ • √ n⌋. Thus, the fractional k-deck of X A equals the fractional k-deck of X B . Indeed, let S π be the binary string induced by slate S when sorted according to π, then, for any s ∈ {0, 1} k ,f X A (s) = S∈( [n] k ) Pr π∼A [S π = s] = S∈( [n] k ) Pr π∼B [S π = s] = f X B (s).Theorem 12 also entails thatA [n] (n) ≥ 1 -ϵ and B [n] (n) ≤ ϵ.Therefore, X A returns a bit string with a 1 in the first position with probability at least 1 -ϵ, whereas X B returns a bit string with a 1 in the first position with probability at most ϵ. This yields the desired lower bound.Proof of Theorem 15. Given a string x ∈ {0, 1} n , let D d,x be the random variable that represents the output of a deletion channel with erasure probability d on input x; let ξ α,d,x be the event that this output has at least α( 1 -d Proof. Let x be any string of length n. By a standard multiplicative Chernoff bound (see, e.g., [Dubhashi and Panconesi, 2009 , Theorem 1.1]), we get:Pr [|D d,x | ≥ 2(1 -d)n] = Pr [|D d,x | ≥ 2 E [|D d,x |]] ≤ e -E[|D d,x |]/3 = e -(1-d)n/3 .Thus, if we sample the deletion channel fewer than o e (1-d)•n/3 times, with probability 1 -o(1) we will never get a sample of length more than 2(1 -d)n. We can then apply Theorem 14, which gave the same fractional k-deck (hence the same fractional k ′ -deck, 6 for each 1) and therefore we have no sample of length more than c • √ n + O(1). Under this conditioning, the two distributions induced by the channel seeded by X A and the channel seeded by X B are the same. Indeed, call Ψ such event, then for any string y, |y| ≤ 2(1 -d)n,1 ≤ k ′ ≤ k) for k = ⌊c • √ n⌋ to its two distributions X A and X B , while guaranteeing very different marginals on their first bit. Selecting d = 1 -c 2 √ n + 1 2n , we get that 2(1 -d)n = c • √ n + O(Pr X∼X A [D d,X = y | Ψ] = Pr X∼X A [|D d,X | = |y| | Ψ] • Pr X∼X A [D d,X = y | |D d,X | = |y|] = Pr X∼X B [|D d,X | = |y| | Ψ] • x∈{0,1} n Pr X∼X A [X = x] • f x (y) n |y| = Pr X∼X B [|D d,X | = |y| | Ψ] n |y| • f X A (y) = Pr X∼X B [|D d,X | = |y| | Ψ] n |y| • f X B (y) = Pr X∼X B [D d,X = y | Ψ].We then get the desired lower bound.B Proper learning algorithm with MAX-SAMPLE oracle Theorem 18. Let P and Q be two RUMs on [n] . There exists constants c, c ′ > 0 such that for a given s ∈[n], T ⊆ [n] ∖ {s}, if |P S∪{s} (s) -Q S∪{s} (s)| ≤ 2 -c ′ • √ |T | ln(1/ϵ) for each S ∈ T ′ | T ′ ⊆ T and |T ′ | ≤ c • |T | • ln 1 ϵ , then P T ∪{s} (s) -Q T ∪{s} (s) ≤ ϵ, where ϵ ∈ (2 - √ |T |+2 , 1/3).Proof. Consider the polynomial given by Theorem 8 ford = |T | ln(1/ϵ), of degree k ≤ c • |T | ln(1/ϵ) = Θ( |T | ln(1/ϵ)), and with ℓ 1 -norm of the coefficients W ≤ 2 c ′′ • √ |T | ln(1/ϵ) = 2 O( √ |T | ln(1/ϵ))for some constants c, c ′′ > 0, that ϵ-approximates AND |T | . Set c ′ = c ′′ + 1. Then, by Observation 7,P T ∪{s} (s) -Q T ∪{s} (s) ≤|P T ∪{s} (s) -P T ∪{s} (s)| + | Q T ∪{s} (s) -Q T ∪{s} (s)|+ | P T ∪{s} (s) -Q T ∪{s} (s)| ≤3ϵ,where the last inequality uses| P T ∪{s} (s) -Q T ∪{s} (s)| ≤ W • 2 -c ′ √ |T | ln(1/ϵ) ≤ 2 - √ |T | ≤ ϵ. Setting ϵ := ϵ/3 completes the proof.A practical implication of this theorem is a proper learning algorithm using MAX-SAMPLE oracle. Indeed, using enough samples one can approximate the winning distributions within an exponentially small error, and then, fitting the approximate winning distributions with a RUM minimizing the maximum ℓ ∞ -error, the theorem guarantees that such RUM will approximate the original RUM on any slate.It is not difficult to see that an analogous theorem can be proved in the more general setting of Sherstov [2008] : taken any events A 1 , . . . , A n , and B 1 , . . . , B n such that the probabilities of the intersections up to size Θ( n ln(1/ϵ)) differ by at most an exponentially small error, we have that the probabilities of any intersection differ by at most ϵ.C Proper learning algorithm in time 2 O(n) In this section, we give more details on how to improve the running time of the proper learning algorithm from n O(n) to 2 O(n) , both for the MAX-DIST oracle and the MAX-SAMPLE oracle. The n O(n) algorithm for both oracles, can be obtained by solving directly the following LP with the ellipsoid method, for k = Θ( n ln(1/ϵ)).EQUATIONNeurIPS Paper Checklist 1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: upper bound and algorithms can be found in sections 3 and 4, while the lower bounds in section 5. Lower bounds for other problems are in sections 6 and 7.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.38th Conference on Neural Information Processing Systems (NeurIPS 2024).In the literature, other works focus on the coefficients of univariate polynomials q : [0, n] → R taking in input the number of bits set to one. We stress that this is not the case in this work, where we always consider coefficients of multivariate polynomials p : {0, 1} n → R unless otherwise specified.We assume |T | ≥ k otherwise computing R T ∪{s} (s) is trivial since we can just query the oracleLower boundsIn this section we present a lower bound showing that it is impossible to reconstruct the winning distribution of the full slate by only looking at slates of size o( √ n), i.e., our reconstruction (Theorem 3) is optimal. For simplicity, we consider the approximation of the winning distribution of the full slate [n], as opposed to any slate T as in Theorem 3.3 3 This is w.l.o.g., since we can build our construction for a given slate size t, by choosing n = t; later, one can add to the same construction as many new items as desired (placing them at the end of the sampled permutation), to get to a total of N ≥ t items in the RUM.When using MAX-DIST oracle we simply have R T ∪{s} (s) = R T ∪{s} (s)Incidentally, this is impossible in general RUMs.This is true for standard k-deck (see[Manvel et al., 1991]) and the argument directly generalizes to the fractional version. 


Decision: This paper has developed very strong results for the problem of learning RUMs. The improvement relative to previous work is enormous, improving the order of $n$ in the exponent itself, along with matching lower bounds. The analysis is technically sophisticated and interesting, connecting to boolean function analysis and polynomial approximation. This paper has very strong support from two reviewers and less support from two lower-confidence reviewers.  One criticism from several reviewers is the exponential complexity, but the authors have shown that this is unavoidable and hence I do not find that this should be viewed as a weakness. Another criticism that came out during the discussion period with the reviewers is that the paper uses an existing connection with boolean function analysis and polynomial approximation; however, I am not convinced that this is a valid criticism since (as noted by another reviewer) boolean function analysis and polynomial approximation are entire fields of study. It does seem that some heavy lifting is done by the prior work of Sherstov (2008), but finding these connections and the authors' own analysis looks impressive. This work is a welcome addition to the proceedings.

Reviews: review: paper_summary: paper_summary: The paper considers the Random Utility Model (RUM) problem and gives upper and lower bound on plate size.

RUM is a classic economic model that is used to understand user behavior by modeling choices from subsets of available items. In the RUM problem, there is a set of element $[n]$ and there is a probability distribution $P$ over the permutation of $[n]$. The algorithm could query a set of $k$ elements, and either observe the one with the highest rank (sampled from $P$) or the winning distribution on these $k$ elements. The paper seeks to understand the optimal value of $k$, such that the algorithm could figure out the permutation distribution (up to small error) given all plate of size $k$. The answer turns out to be $k = \Theta(\sqrt{n})$.

In particular, 
1.  The upper bound shows that knowledge of choices from slates of size$ O(\sqrt{n})$ allows approximating the choice distribution for any slate with high accuracy. Moreover, it gives an algorithm that learns RUMs efficiently: A proper learning algorithm with $n^{n}$ time and an improper learning algorithm with $n^{\sqrt{n}}$ time. 
2.  Lower bounds are derived, indicating that learning from slates smaller than $\sqrt{n}$ results in high prediction errors. These results also contribute to understanding the k-deck and trace reconstruction problems.

In terms of technique, the proofs rely on connections between RUM learning and the approximation of Boolean functions by polynomials. The paper leverages results from the approximation of the AND function to develop their bounds and algorithms.

Overall, the paper solves a meaningful problem and characterizes the optimal plater size. The drawback is that that query complexity and the runtime is exponential.
strength_weakness: strength_weakness: 1. Query complexity and the runtime is exponential; 
2. I think it needs some explanation on the query model. In particular, why the model can only see plate of size $k$. 
3. The writing could be improved: for example, Line 58, our results are proved *by* observing; Line 95, the citation appears at a wrong place.
questions: questions: .
limitations: limitations: .
paper_summary: paper_summary: A random utility model is defined by a distribution over permutations of $1,2,\dots,n$. Given a non-empty subset $S \subseteq \{1,2,\dots,n\}$, an oracle stochastically returns which one in $S$ is the highest according to this distribution. This paper considers the problem of estimating a random utility model from winning probabilities for small $S$.
- This paper first proposes an algorithm that queries all $S$ with $|S| = \tilde{O}(\sqrt{n})$ and then estimates a RUM by solving an LP. The authors shows that this estimated model has small error even for large $S$. This algorithm takes $n^{O(n)}$ time.
- Next the authors consider an approach of expressing RUMs by polynomials. The proposed algorithm again queries all $S$ with $|S| = \tilde{O}(\sqrt{n})$. However, as the expression of an estimated RUM does not require $n!$ dimensions, both the estimation and prediction takes $n^{\tilde{O}(\sqrt{n})}$ time.
- The authors also provide a lower bound. That is, if two RUMs coincide on all $S \subseteq [n]$ with $|S| = O(\sqrt{n})$, the error for $S = [n]$ can be very large.
- The last contributions are on the fractional versions of the $k$-deck and trace reconstruction problems. The authors give lower bounds on the sample complexity for these problems based on the RUM lower bound.
strength_weakness: strength_weakness: In my opinion, the largest weakness of this paper is the lack of practical insight. The main result claims that estimating a RUM requires $n^{\tilde{O}(\sqrt{n})}$ queries, which is unrealistically large for suggested applications such as web search results. Theoretically, this bound is meaningful; the upper and lower bounds coincide, so this order is tight. However, in practice, I do not know a realistic scenario in which we can query all size $\tilde{O}(\sqrt{n})$ subsets, and the proposed algorithm seems to be designed for the theoretical purpose. Actually, the authors do not provide any experimental result. I think there might be a more appropriate venue other than NeurIPS for this paper. The technical contribution of this paper is mainly to relate RUMs and the AND function, which seems to attract more audience in TCS conferences.
questions: questions: Is there any possible future direction to develop the results of this paper for more practical applications?
limitations: limitations: The contribution of this paper is only theoretical and does not seem to have a large practical impact for now.
paper_summary: paper_summary: This paper studies the problem of learning a Random Utility Model with limited information.  A RUM is a distribution on the symmetric group on $n$ letters and a slate is a nonempty subset of the universe of letters.  The paper studies the problem of learning the RUM given access to the probabilities that a given letter $s$ is most preferred by a sample from the RUM out of all of the elements in a given slate $S$.  The authors apply classical techniques to derive an information theoretic upper bound for the necessary size of a slate in order to learn the RUM to additive error $\epsilon$, which is complemented by a matching lower bound at the end of the paper.  They then provide two algorithms bounding the sample complexity of learning the RUM with such slates: one relying on solving a linear program requiring $n^{O(n)}$ samples and another algorithm relying on polynomial approximations for the Boolean AND.  The latter algorithm is then applied to demonstrate that large slates can be used to learn an RUM in polynomial time to constant accuracy.  The paper concludes with applications of their techniques to two other problems in the intersection of combinatorics and CS theory.
strength_weakness: strength_weakness: The main weakness in the paper is the exponentially large number of slates required by the algorithm in order to learn the RUM.  The simulation lemma is able to reduce this to polynomial at the cost of increasing the size of the slates, but the time is still exponential in the error.  It would be nice to have a clearer idea of the landscape with respect to if polynomially many slates are sufficient even in a polynomially smaller slate setting.  The authors also heavily use prior technical contributions and it might be useful to better delineate the core technical contributions of the present paper.
questions: questions: 1. Is there some middle ground in the size of the slates, say $\Theta(n^c)$ for $1/2 < c < 1$ that allows for poly algorithms in approximating the RUM?  As it stands there is quite a gap between the exponential algorithms in the case of $\Theta(\sqrt{n})$ and the poly algorithms in the case of $\Theta(n / \log n)$.

2. Are there weaker notions of learning the RUM that allow for either smaller slates or more sample-efficient algorithms?  For example, I could imagine that some of the sample complexity is coming from learning the precise order of very low-preference items in high probability according to the RUM.  If one were to only care about properties of the RUM relevant to some notion of the most preferred items, can the bounds be improved?

3.  It would be nice to rigorously demonstrate that the algorithm in Theorem 5 actually can be made to run with $2^{O(n)}$ slates as opposed to $n^{O(n)}$.  It is poor form to simply state this as a footnote, as future authors may wish to cite this result without being forced to rewrite your entire proof.
limitations: limitations: The limitations have been adequately discussed.
paper_summary: paper_summary: This paper studies the learning of Random Utility Models (RUMs). A RUM is a probability distribution $P$ over the set of permutations over $[n]$. Fix a permutation $\pi$ and consider any subset $T \subseteq [n]$, known as a *slate*. The winner of the slate (corresponding to $\pi$) is the highest ranked element in $T$ accordint to $\pi$. We can imagine fixing a slate $T$, and consider the distribution of the winner of the slate $T$ as we draw $\pi$ from $P$. In the problem of learning RUMs, one is given a set of slates, together with the corresponding distribution of the winner of that slate. The task is to reconstruct the distribution of the winner of every possible slate.

Specifically, this paper considers the problem when the example slates given to a learning algorithm are at most a size $k$. The main result of the paper is that having access to the winning distributions of all slates of size at most $O(k)$ is necessary and sufficient for the task of learning RUMs. The same result also holds if one has only sample access to the winning distributions of all slates of this size. The authors present two algorithms that achieve the upper bound: 1) a proper algorithm, that constructs a RUM in time $n^{O(n)}$, and thereafter, given any slate, returns an approximation to the winning distribution of that slate in polynomial time 2) an improper algorithm, that does not construct a RUM, but runs in time $n^{O(\sqrt{n})}$, and thereafter, given any slate, returns an approximation to the winning distribution of that slate in time $2^{O(\sqrt{n})}$. The latter algorithm thus, in time $n^{O(\sqrt{n})}$, approximates the winning distribution of the full slate $[n]$ in $l_\infty$, which is an improvement over the previous best running time of $2^{O(n)}$ for the same task, implicit in prior work. The latter algorithm can also be adapted to yield the following guarantee: given a prespecified slate $T \subseteq [n]$, one can approximate the winning distribution of $T$ in $l_\infty$ in time polynomial in $n$, by querying slates of size at most $O(|T|/\log|T|)$. The authors also show that any algorithm that only accesses slates of size $o(\sqrt{n})$ can not successfully learn the winning distribution of the full slate. This shows that their earlier two algorithms are optimal in the maximum size of the slates they access. Finally, the authors define fractional versions of two classic problems in the intersection of combinatorics and computer science: $k$-deck and trace reconstruction. Using their techniques for learning RUMs with small slates, they are able to obtain new results for the fractional versions of both these problems (similar quantitative results would be major breakthroughs for the original problems).

The upper bounds rely crucially on results by Sherstov in 2008, and on the state-of-the-art approximation of the AND function by low degree polynomials due to Huang and Viola, 2022. The lower bound is a reduction to a lower bound on the approximation of the AND function by low-degree polynomials, due to Bogdanov et al. 2016.
strength_weakness: strength_weakness: If I am to nitpick: while the technical narration of the problem of learning RUMs given by the authors is clear (I admit that I did not even know this problem before reading the paper, but could understand almost all of the paper), I would have liked to see a little more story-building and motivation around this problem in the introduction. I felt that the authors dived into their technical contributions rather too soon. I would also have liked to see the authors elaborate more on how their work compares to prior work by Chierichetti et al. 2021, 2023. As of now, these works, while seeming to be most relevant, are only cited in passing in the related work. Also, I feel that a few more references could be provided with respect to variations of the $k$-deck and trace reconstruction problems that have been considered in the literature.
questions: questions: 1) The authors do show in Observation 13 that having access to slates of size exactly $k=\Theta(\sqrt{n})$ is also not sufficient for learning the RUM. Might it however be possible that such a result holds for some $k > \Theta(\sqrt{n})$? Say I am given all the slates of size exactly $\Theta(n^{0.6})$?


2) Are similar fractional versions of the $k$-deck or trace reconstruction problems known? I suggest doing a literature survey to cite some works that have considered variants of these problems -- this might make these sections more complete and situate your definitions of the problems better within the literature. For example, here are two works I found with a preliminary google search: 1) Approximate Trace Reconstruction from a Single Trace. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha, 2022 2) Approximate Trace Reconstruction. Sami Davies, Miklos Z. Racz, Cyrus Rashtchian, Benjamin G. Schiffer, 2020.
limitations: limitations: The authors have satisfactorily addressed the limitations of their work.

Comments: title: Thank you for responding
Response to rebuttal
comment: Thanks for your reply. I acknowledge that i have read the rebuttal. I will read other reviewers' comments and have discussion with them.
The authors have done a good job of responding to my questions and I maintain my recommendation to accept.  The theoretical contribution and the new techniques used are of interest.
Thank you for the feedback. Although I understand that the improvement made by this paper accelerates the running time so much, but I am still not convinced that the running time $n^{\tilde{O}(\sqrt{n})}$ is practical. Those papers about RUMs published in ICML and NeurIPS mainly considered a more restricted model expressing RUMs and proposed practical algorithms, which is a more promising direction for developing practical algorithms in my opinion. I keep the current borderline accept score for evaluating this paper's theoretical contribution.
Thank you for the response. Please do include the discussion from your response, along with the references, in the updated version. I maintain my score of 8, and believe this work should be accepted. Great work!